Computer Science 210
Data Structures

Fall 2016, Siena College

Lecture 14: More Recursion; Searching
Date: Friday, October 7, 2016


Lecture 14 Assignment

Due at the start of class, Wednesday, October 12.

Please submit answers to these questions in Blackboard under "Lecture 14 Assignment" by the start of class. We will discuss these questions at the start of class, so no late submissions can be accepted. In addition to finishing up the Lecture 09 Assignment, you will need to complete the following tasks.

For the first part of this lecture assignment, you will be writing a Java application similar in structure to the Powers example. Write your program in As in that example, you will need to create a keyboard Scanner to read in a number from the terminal and use System.out.println to issue a prompt and report your answer.

The problem we are going to solve is that of computing factorials. From math, you know that the factorial of a positive integer n, denoted n!, is the product of all the numbers from 1 up to n.

For the second part of the lecture assignment, you will be seeing how we can create our own Comparable objects that could be used with generic code like the search methods in the BinSearch example. Follow the steps below. The entire exercise is worth 15 points, with 5 additional bonus points available to you for completing the last step.

  1. Make a new copy of from the Ratios example.
  2. Have the Ratio class implement the Comparable interface. So the class header would become:
    public class Ratio implements Comparable<Ratio>

    This tells Java that this class can be treated as a "comparable" object like Integer, Double, String, and many others.

    If you try to compile now (do it), you should get an error message something like

    Ratio is not abstract and does not override abstract method
    compareTo(Ratio) in Comparable

    This means that you said Ratio objects are comparable but didn't tell Java how to do that comparison. We do it in the same way that we compare other objects: by providing a compareTo method.

  3. Write a compareTo method in the Ratio class. It will need to have a method header like this:
        public int compareTo(Ratio other)

    For now, have your method simply return 0 in all cases. You should now be able to compile again.

  4. Now, make the compareTo method work properly.

    Your only experience so far with compareTo methods is probably the one built in to the String class. Recall that for String references s1 and s2, the call


    will return 0 if s1.equals(s2); a value less than 0 if this s1 is lexicographically less than s2; and a value greater than 0 if s1 is lexicographically greater than s2.

    For Ratio objects, we want to do the same thing: if we have two Ratio objects r1 and r2, the call


    should return 0 if r1.equals(r2) (keep in mind this means that the 1/2 should be equal to 3/6); a value less than 0 if this r1 is less than r2; and a value greater than 0 if r1 is greater than r2.

    It doesn't matter what positive or negative value you return, as long as it's positive when it should be, negative when it should be, and 0 when they're equal.

  5. Write a short main method in your modified Ratio class to test your new compareTo method. Be sure all three possible return values are tested.
  6. For 5 bonus points, copy in the BinSearch example and add code to the main method there that creates an array of several Ratio objects and peforms a variety of successful and unsuccessful searches. Be sure to test all important cases.