Computer Science 210

Data Structures

Fall 2016, Siena College

Agenda

- Announcements
- Don't forget that the delayed Lecture 09 Assignment will be due at the start of lab on Wednesday. This is in addition to the new assignment posted below.

- Exam 1 back and brief recap
- more detailed recap if there is interest can be during lab time next week

- Recursive methods
- Searching
- visual demo with highway data
- using
`Comparable`objects (refer to the notes if necessary while doing the lecture 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 `Factorial.java`. 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*.

- Write a
`main`method of your`Factorial`class that prompts for and reads in a positive integer. You need not worry about error checking the input for this assignment. (2 points) - Write an iterative method
`loopFactorial`that takes a single`int`as its parameter and returns the factorial of that value. Recall that an iterative method uses loop structures like`for`and`while`loops to do its work. Also update your`main`method to call the`loopFactorial`method on the number entered by the user, and print out the value returned. (6 points) - Write a recursive mathematical formulation, along the lines of
the second power formula in the notes, for computing
*n!*. (3 points) - Write a recursive method
`recFactorial`that uses that formulation to compute factorials. Also update your`main`method to call the`recFactorial`method on the number entered by the user, and print out the value returned. (9 points)

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.

- Make a new copy of
`Ratio.java`from the Ratios example. - 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. - 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

`Ratio.java`again. - 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 calls1.compareTo(s2)

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 callr1.compareTo(r2)

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.

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

Terminology

- stack variables
- heap variables
- searching
- linear search
- binary search
- divide and conquer

Examples