Programming Assignment:
Warm Up and Stretching

Objectives

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. 

Strategy Suggestions

Check-out Instructions

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-201330-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.

 

 

Five Small Programming Tasks for this Assignment

Anagrams

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.

SortedLinkedList

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.

PriorityQueue

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:

  1. If we were naïve, we might write the 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?

  2. Study the current compareTo code. Then explain how you could easily use this priority queue class as a standard (FIFO) queue.

Hardy's Taxi

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.

Adding Calculator

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.

A picture of the calculator

Turn-in Instructions

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).

Grading

For the general guidelines that the graders will use, see this page.