To get you programming in Java again if it has been a while. To have you think about using basic data structures. To have you think about how linked lists are implemented. To implement a simple numeric algorithm in a way that fits into a provided framework. To recall how to do event-driven programming using Java Swing.
There are also some basic infrastructure issues to review, such as checking projects out of SVN, committing them back to SVN, and running JUnit tests. We have included notes to help you get up to speed on these things. Be sure to ask for help if you’re having trouble with those details. The main challenge on this assignment is supposed to be solving the programming problems, not wrestling with the tools. Please don’t waste your time on something that we’re more than happy to show you how to do.
All of the problems except Hardy's Taxi have appeared on timed CSSE 220 exams in the past, so we know that they can be done quickly if you are up-to-speed on Java programming. Hardy's Taxi may take a little more thought. Do not worry too much about coming up with an efficient solution for that one; a later problem will ask you to do that.
This assignment is due in 7 days. Here is a suggested schedule:
Your work for this assignment should be done in the
WarmUpAndStretching
project inside Eclipse. Check out this project from your
personal
SVN repository for this course.
Your personal SVN repository URL is:
http://svn.csse.rose-hulman.edu/repos/csse230-201410-username
where
username
is your Rose-Hulman username. Recall that your SVN password may be
different than
your Rose-Hulman network password. Your SVN password should be unchanged from previous terms. If this is your first term with an SVN account at Rose-Hulman, then you should have received an email from root with your password.
If you are unable to remember or find your SVN password, please let your instructor know and he/she will run a script to reset it to a new random string of characters or to a string that you specify.
Be sure to commit your work often as you make progress on these programs. This will help you recover from mistakes, power failures, and freak accidents. What will be graded is what is in your repository, so do not forget to commit.
See the Using Subclipse instructions at the end of this page for more information on using your SVN repository.
Two strings are
anagrams
if the characters in one string are an exact rearrangement (permutation) of the characters in the other string. In this problem, we extend the definition to allow for different cases of letters, so that "Data Structure" and "Saturated Curt" should be considered to be anagrams.
Spaces are included in the "permuted characters." In the
anagram.Anagram
class, we provided the stub for a method,
isAnagram(), which takes two
Strings and determines whether they are anagrams. You should complete this method. When it is working, it should pass all of the unit tests in
anagram.AnagramTests.
To run a particular set of unit tests: right click the test file in Eclipse’s Package Explorer, then choose Run As → JUnit Test. You can right click a package to run all the tests in a package or right click a project to run all of its tests. Once you’ve run a set of tests, you can run the same tests again by using the green “play” button in the JUnit view's tool bar. Talk to an assistant or your instructor if you need help getting up-to-speed on writing/using JUnit tests.
The
list
package
contains the
DoublyLinkedList class. This class implements a doubly linked list of
Comparable
objects. Study this code. In particular, note how it uses polymorphism for the nodes of the list.
In particular, a DoublyLinkedList has a special head node and tail
node that do not contain actual list data but make it easier to do
the list's operations.
Also in the
list
package is a skeletal definition of a new class called
SortedLinkedList. As the name implies, the elements of such a list are kept in increasing order. Comments in the
SortedLinkedList
code briefly explain what each method is supposed to do and/or return. Looking at the unit tests in
SortedLinkedListTests
may also help clarify what the methods are supposed to do.
You are to finish the implementation of
SortedLinkedList
by completing each
TODO
item. When it is working, it should pass all of the unit tests in
SortedLinkedListTests.
You can view a listing of
TODO
items in Eclipse by turning on the
Task
view. Choose
Window → Show View → Tasks.
Chapter 6 of Weiss is part of this week's reading assignment, and
most of it should be a review of things discussed in 220/221.
Priority queues were not discussed directly in 220, but the idea behind them
is simple. This problem asks you to use one of Java's built-in
data structures (TreeSet) as the basis for implementing another
common data structure (PriorityQueue).
The files for this task are in the
priorityQueue
package. As described on page 275 [241 in the 3rd edition] of Weiss, one possible interface to a PriorityQueue is
via the three methods
insert,
findMin, and
deleteMin. The method call
insert(pri, element)
inserts
element
into this priority queue with priority
pri. Calling
findMin()
returns the element with minimum priority, and
deleteMin()
deletes that lowest-priority element. If two elements have the same priority, the ordering of the elements themselves is used to "break the tie" when determining which is the minimum element of the priority queue.
One fairly straightforward way to implement a Priority Queue is by using a
TreeSet (Treeset is part of the standard Java library). The
PQ
class (partially) does this, oyu are to complete the task. (Later, we’ll learn about a more efficient approach, the Binary Heap). In order to facilitate your work,
we have provided a class called
PQElement. A
PQ’s
treeSet
field will contain objects of type
PQElement. Your job is to fill in the details of the constructor and the three methods of the
PQ
class. Your code must pass the unit tests in
PQTests.java.
You can read more about priority queues and TreeSets in Weiss, pages 274-276 [239-243] (Section 6.9) and 261-264 [228-231] (Sections 6.7 and 6.7.1).
After you get the code working (or even if you don't get it working), consider the question below. You do not need to write out the answers, but be sure that you could answer them if asked to do so:
compareTo
method of the PQElement class as
public int compareTo(PQElement<T> other) {
return this.priority - other.priority;
}
What would go wrong if we did this?
compareTo code. Then explain how you could easily use
this priority queue class as a standard (FIFO) queue.
This background description for the Hardy's Taxi problem was adapted from http://cs.bilgi.edu.tr/pages/curiosity_corner/challenges/ramanujans_number.html :
|
G H Hardy, the famous British mathematician, brought Ramanujan, a poor man from India who
was a natural mathematical genius, to work with him at Cambridge University. They had a
very important and creative mathematical partnership. The British climate was bad for
Ramanujan. He got tuberculosis. As he lay dying in hospital, Hardy went to visit him.
As he entered the room he said, "The number of my taxi was 1729. It seemed to me rather
a dull number." To which Ramanujan replied, "No, Hardy! No, Hardy! It is a very interesting
number. It is the smallest number expressible as the sum of two cubes in two different ways."
Is the number in the story correct? Is 1729 the smallest number expressible as the sum of two positive cubes in two different ways? It is fairly easy to show that it is expressible as the sum of two cubes in two different ways, but is it really the smallest such number? |
The files for this part are in the hardysTaxi
package. You are to complete the definition of a method
hardySolutionsLessThan that, given a positive integer N, finds
all integers s < N such that there are positive integers a, b, c, and d
with a ≤ b, c ≤ d, a ≠ c, b ≠ d, and a3 + b3 = s = c3 + d3.
The method returns the answer as a list of TaxicabNumber objects, as
defined in the provided code.
You can learn a lot about how those objects work by examining the
various JUnit tests in the two test classes in the hardysTaxi
package. You can find the stub for the hardySolutionsLessThan method in the Hardy.java file;
you should not modify any other code in the hardysTaxi
package.
In the package adder is code for a GUI framework for a very simple calculator that adds non-negative integers. You need to write the event-handling code and any other code that is necessary to make it behave like an adding calculator. In the code’s comments, I show examples of what should be displayed when various buttons are pressed. The C (clear) button sets the display to 0 and begins a new calculation.
Turn in your work by committing it to your SVN repository. We recommend committing often, whenever you have made some progress toward a solution to one of the problems. Your last commit date will determine the status of your submission as on-time, early, or late (See the Late Days policy in the course syllabus).