2 problems, 30 points for #1 and 20 points for #2 (+ extra credit possible)
For this problem, you'll be implementing a menu of options
similar to those in previous assignments. No classes other than
CS5App will be needed. Each menu option will
require its own method, however, and all of these methods
must be recursive.
The menu of options
Your program should offer the following menu (in a while loop) to the user:
The Recursive Roster:
(1) factorial
(2) power
(3) harmonic series
(4) palindrome checker
(5) string reverser
(6) min mover
(7) list sorter
(8) longest common subsequence [Extra]
(9) quit
Which option would you like?
The recursive methods
All of these should be in the CS5App class:
public static double factorial(int n)
n as a double.
If the input is zero or negative, this method should return 1.0.
public static double power(double b, int n)
b to the n power.
If n is zero or negative, this method should return 1.0.
Remember that taking a power is NOT repeated squaring -- it's
repeated multiplication by the base, b.
public static double harmonic(int n)
n terms of the harmonic
sequence, i.e., the sum of the reciprocals of the first n
positive integers. For example,
harmonic(1) = 1/1 = 1.0
harmonic(2) = 1/1 + 1/2 = 1.5
harmonic(5) = 1/1 + 1/2 + 1/3 + 1/4 + 1/5 = 2.28333
n is one or less, this method should return 1.0.
Watch out for type casting here -- remember that in java, 1/2 is
equal to 0, but 1.0/2 is equal to 0.5!
public static boolean isPalindrome(String s)
true if s is a palindrome, i.e.,
if s is the same either forwards or backwards. It should
return false otherwise. Note that any word of
one letter is a palindrome and any word
of zero letters is also a palindrome. After all, one-letter and zero-letter
words do read the same forwards and backwards.
public static String reverse(String s)
String whose characters are the
same as the characters of s, but in the reverse order.
isPalindrome
quite easily with reverse, the intent of this
assignment is to write each method recursively -- so do not
use this method to help the previous one!)
public static void moveMinToLeft(double[] A, int L, int U)
Note that for this moveMinToLeft option and the sort one below, your code (in main somewhere) will have to ask the user for, first, the number of elements to have in the array, and then the elements in the array, and THEN it should ask for the low and high indices that will be used for L and U when calling moveMinToLeft. It will also need to print the array after the method is called. See the example below for a guide to input and output.
public static void sort(double[] A, int L, int U)
sort is called,
the elements between index L and U,
inclusive, in the input array A should be sorted in ascending
order. Hint: Use the above moveMinToLeft
method, as well as recursion.
substring
The built-in method substring will be helpful for the
fourth and fifth options of this problem. substring
takes in two integers as input and returns the piece of this
between those two indices. Here are a couple of
examples of how substring works. Note that the
substring is taken from the first index up to and not including
the second index:
String s = "hamburger";
String t = "";
t = s.substring(4,8); // t is now the String "urge"
t = s.substring(0,1); // t is now the String "h"
t = s.substring(1,s.length()); // t is now the String "amburger"
Sample Run
Here is an exmple run -- the text
the user types is in blue. Remember that all of the prompting
for inputs and printing of outputs should be done in main:
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
Choose a recursive function to test:
1 factorial
2 power
3 harmonic series
4 palindrome checker
5 reverser
6 min mover
7 list sorter
9 quit
Choose an option: 1
Type a nonegative integer to take the factorial of: 6
The factorial of 6 is 720.0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
< Recursive Roster menu >
Choose an option: 2
Type a base (a double) and a power (a nonnegative int): 5.5 3
5.5 to the 3 power is 166.375
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
< Recursive Roster menu >
Choose an option: 3
Type a positive number of terms: 1000
The sum of 1000 terms is 7.485470860550343
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
< Recursive Roster menu >
Choose an option: 3
Type a positive number of terms: 5
The sum of 5 terms is 2.283333333333333
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
< Recursive Roster menu >
Choose an option: 4
Type a possible palindrome: racecar
racecar is a palindrome
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
< Recursive Roster menu >
Choose an option: 4
Type a possible palindrome: racecars
racecars is NOT a palindrome
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
< Recursive Roster menu >
Choose an option: 5
Type any word: forward
The reverse of forward is drawrof
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
< Recursive Roster menu >
Choose an option: 6
How many numbers would you like to handle? 5
Type the 5 numbers:
#0: 67.8
#1: 54.01
#2: 1.10
#3: 100
#4: -65
Type the low index (L): 1
Type the low index (U): 3
The new list is
67.8
1.1
54.01
100.0
-65.0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
< Recursive Roster menu >
Choose an option: 7
How many numbers would you like to sort? 5
Type the 5 numbers:
67.8
54.01
1.10
100
-65
Type the low index (L): 0
Type the low index (U): 4
The sorted list from 0 to 4 (inclusive) is
-65.0
1.1
54.01
67.8
100.0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
< Recursive Roster menu >
Choose an option: 9
Submission Be sure to submit your CS5App.java
file under homework 12,
problem 1.
Extra Credit An important problem in biology and bioinformatics is that of gene-sequence comparison and alignment. One common measure of similarity between two sequences of characters is the length of their longest common subsequence. For example, the two DNA-like sequences
GATTTCAAGTGAC
CTTAGACATAGGT
Note that the length of the longest common subsequence is unique, but there may be more than one in-common subsequence of that length.
For extra credit, write a recursive method public static String LCS(String s1, String s2) that returns a longest common subsequence of s1 and s2. It is OK if your algorithm runs slowly on large inputs: we will test in on sequences with 15 characters or fewer. It is possible, however, to write very fast algorithms that can handle the millions of characters in real DNA sequences. Feel free to improve your algorithm, if you'd like!
Hint: A reasonable base case is to check if either input String has length 0. For the recursive step, check if the first two characters match. If they do, what should happen to that char? If they don't, what are two recursive possibilities for the LCS?
The final project (linked here) is a large program that implements a movie database. (The full description will be handed out in the next CS 5 class.) Because it is by far the largest software project in CS 5, this problem intends to be sure that everyone has at least a skeleton prepared a week in advance. (Trying to write the movie database a few hours before the deadline would not be a good idea!)
Thus, for this problem, you will need to write all of the classes and data members needed for the movie database. In addition, you will need to write stubs (empty methods) for all of the functions -- with the correct signature and return value for each; you do not need to actually implement them until next week. You should also comment them this week (that way you'll have a sense of what each does!)
What do I return?
You may return anything of the correct type, but you do
need to return something in order for your code to compile (which
we will check!) So, you may return 0 for an int,
0.0 for a double, and true for a
boolean. For objects, the value you should
return is null, which is a reference that doesn't
refer to anything! Though it's not too useful in and of
itself, it is a legal value for any variable of some class type.
Thus, the stub for your "getFilmDB" method in the Director
class should look like this:
public FilmDB getFilmDB()
{
return null;
}
Finally, your code should compile and run -- it needs to implement the initial question (the capacity of the database) and the main menu of user options. Of course, the individual options do not have to work until next week.
Commenting
Also, your code should have the usual comments for each method (this
will help considerably when writing the actual methods for the final
assignment!) That is, they should have a brief note of purpose, and
should explain their inputs and outputs. Here's a complete example for
the above getFilmDB method in the Director
class:
/* method: getFilmDB, used to obtain all of a director's films
*
* inputs: none
* return: an object of class FilmDB holding "this" director's films
*/
public FilmDB getFilmDB()
{
return null;
}
Here is a list of the classes, their data members, and method signatures to include. A short description for each is here so that you'll be able to write comments on what each method does. You may include more methods (either this week or next week), but you should have at least these:
private static FilmDB F private static DirectorDB D public static void main(String[] args) public static void printMenu() public static void saveDB(String fileName) (saves the
film database to a file)public static void readDB(String fileName) (loads a
film and director database from a file)public static void readFilm() private String title private int year private String rating private double review private Director dir public Film(String title, int year, String rating, double review, Director dir) public String getTitle() public int getYear() public String getRating() public double getReview() public void save() (saves all of a film's data to
file)public void display() (prints all of a film's data)private Film[] films private int count public FilmDB(int capacity) public boolean isFull() public int getCount() (returns the number of films in
the film database)public void addFilm(Film f) (adds a film to this film
database)public Film findFilmByName(String fulltitle) (returns
null or the film already present by that title)
public void saveAllFilms() public void displayAllFilms() public void displayFilmsByTitle(String titlepiece) public void displayFilmsByYear(int year) public void displayFilmsByRating(String rating) public void displayFilmsByReview(double minreview) private String fname private String lname private FilmDB filmDB public Director(String fname, String lname, int capacity) public String getFullName() public String getFirstName() public String getLastName() public FilmDB getFilmDB() private Director[] dirs private int count public DirectorDB(int capacity) public boolean isFull() public int getCount() (returns the number of dirs in
this director DB)public void addDirector(Director dir) (adds a dir to
this director DB)public void displayAllDirectors() public Director findDirectorByName(String lname, String
fname) (returns null or the dir already present
with the input name)In addition, your code should ask the user for the initial capacity of the film and director databases. It should then proceed to offer the menu of options to the user, as shown below. Only the "Quit" option needs to work for this week's assignment, however.
Sample Run:
Welcome to the bottomless CS 5 film database!
Please choose from the following list:
0 Display all directors
1 Display all films
2 Display all films by Title
3 Display films by Director
4 Display films by Year
5 Display films by Rating (G, PG, ...)
6 Display films by Review (0-10)
7 Add a new film
8 Save database to a file
9 Load database from a file
42 Quit
Enter a choice: 42
Until next time, the gallery is closed.
Submission
For this problem, submit your CS5App.java file
under Homework 12, Problem 2.
The extra credit (up to 20%) is to implement the "longest common subsequence" item on the recursive roster menu. See the end of problem 1's description for full details.