HW6: Recursion Practice

HW6: Recursion Practice [INDIVIDUAL]
This assignment is due by 1 PM on Wednesday, February 14 and is worth 15 points. This
is a solo assignment--you must turn in your own code for the assignment, and cannot
turn in code that someone else has written. You may discuss ideas for the problems at a
high level with classmates, but cannot write code together.
Goals
The goal of this assignment is to get more practice with recursion. (Hooray!) You will also
get to cement your knowledge of linked lists and interfaces.
The Comparable Interface
The Comparable Interface is an interface in Java that allows for there to be a total ordering
of the objects in each class that implements it. In particular, any class that implements
the Comparable interface, must implement a compareTo method. Here is a description of
how the compareTo method should work.
Method return type description
compareTo(E obj) int
This method will compare the
object calling the method to the
object passed as a parameter.
Returns a negative integer, zero,
or a positive integer if this
object is less than, equal to, or
greater than the given object.
A few examples of classes we have seen that implement the comparable interface
are: String, Integer, and Double. Consider the following snippet of code:
Integer one = new Integer(1);
Integer two = new Integer(2);
int comp = one.compareTo(two);
System.out.println(comp);
This would print a negative number (-1) since 1 is less than 2. Similarly, consider the
following snippet of code:
String one = "one";
String two = "two"
int comp = two.compareTo(one);
System.out.println(comp);
This will print a positive number (5) since "two" comes later alphabetically (hence
is greater) than "one".
Code provided for you
I've provided you with a class called RecursiveLinkedList.java that implements the
List ADT using a LinkedList structure. This code only works with items that implement
that Comparable interface. You should spend some time just looking through this code. In
addition to public methods, there are a number of private helper methods included. Take
note of how these helper methods can make some of the code for other methods
(e.g. public E remove(int index)) much cleaner and easier to understand. Much of
this code is taken straight from your textbook, but it's nice to see it all in once place.
Your Task
Your task with this assignment will be to write the code to add the following three methods
to this class. To receive full credit, you must implement each of these methods using
recursion and your implementation of each must run in O(n) time, where n is the number
of elements in the list.
/**
* Return the maximum element in the list using
* compareTo() method of Comparable.
*
* @return maximum element of the list
**/
public E max(){
// YOUR CODE WILL GO HERE
// You will likely want to use a helper method
return null;
}
/**
* Remove all elements that match element using the
* equals() operator to determine a match.
* (Don't use ==).
*
* @param element The element that should be removed
**/
public void removeAll(E element){
// YOUR CODE WILL GO HERE
// You will likely want to use a helper method
}
/**
* Duplicate each element of the list
*
* For example, the list [ 0 1 2 ] duplicated becomes
* [ 0 0 1 1 2 2 ]
**/
public void duplicate(){
// YOUR CODE WILL GO HERE
// You will likely want to use a helper method!
}
You should also be sure to include a main() method that tests out the methods you
have written. Be sure to consider difficult cases!
Hints
• I suggest you take my suggestion about using a helper method seriously. The key
thing here will be to think about how to define the signature of that method.
• You will likely want to define helper methods that either take a Node object as a
parameter or return a Node object. If you do this, you should make sure that your
method declaration (the first line that says what you return and the parameter types)
always uses Node<E. For example, you might define the following method that
returns a Node and takes in a Node as a parameter:
public Node<E helperFunction(Node<E aNode)
• It's totally fine if all the recursion is done in your helper methods, rather than the
specific methods I am asking you to implement.
Submission and Grading
Submit your modified version of RecursiveLinkedList.java. This assignment is worth
15 points. Each of the three functions you will implement is worth 4 points. To get the full
points, it needs to be implemented recursively (no loops!) and it needs to run in O(n). The
more elegant your code, the better. Your code will also be evaluated for general style
guideline (are you using good variable names, using proper indentation, etc). This will be
worth 2 points. Finally, implementing a main() method that properly tests your methods
will be worth 1 point.
Start early, ask lots of questions, and have fun! Eric, the lab assistants, and the prefect are
all here to help you succeed - don't hesitate to ask for help if you're struggling!