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;  writing a more efficient solution is sometimes a later problem in the course. 

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

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

ComparingShapes

As you know, the Arrays.sort() method that is part of the Java API can only sort an array of objects if they are Comparable, that is, they implement the Comparable interface. Run ShapeTest.java to sort an array of Circle objects and notice that it fails. Make circles Comparable to one another. (The best syntax is to write, class Circle implements Comparable<Circle>.) Then sort an array of triangles both by perimeter and by area. Wait, you say, if I make them Comparable using perimeter, I can't also make them Comparable using area! True. You will need to write and use Comparators to do this. Make changes both to ShapeTest.java and Triangle.java to do this, following the TODOs and noting that we did perimeter for you. (The TODOs give a hint if you don't know how to find the area of an arbitrary triangle from its side lengths.) We'll be using Comparable and Comparators often this term, so this quick review exercise is worth your time. Then, you'll repeat the exercise using a TreeSet, so you won't even have to call sort()!

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. Priority queues were not discussed directly in 220, but the idea behind them is simple. The files for this task are in the priorityQueue package. As described on page 275, 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.

A common theme in this course is to use one data structure as the basis for implementing another one. Here, you will implement a PriorityQueue by using a TreeSet. The PQ class (partially) does this; you are to complete the task. (Later in the course, 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 :

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 a³ + b³ = s = c³ + d³. 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.

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

1. Good comments: Javadoc for public fields and methods. Internal comments to tell WHY you did something (not what you did) for long methods and anything that is not obvious.
2. Good variable and method names: Eclipse has name completion (ALT /), so the “typing cost” of using long names is small
3. Defensive programming: Use local variables (instead of fields) anywhere you can’t explicitly justify creating instance fields.
4. No super-long lines of code
5. No super-long methods: use top down design
6. Consistent indentation (ctrl-shift f)
7. Blank lines between methods, space after punctuation
8. Don't compare boolean operations to true. Thus, use if (empty(tree)) instead of if (empty(tree) == true).
9. Also, return booleans, so write

    return x > 0;

   rather than

    if (x > 0) {
    return true;
    } else {
    return false;
    }