Lab 4: Recursion with Your Linked List (100 pts)
Due Monday, October 22 at 11:59pm on Canvas


Pair Programming Extra Credit Opportunity (5 pts)

  • Both partners fill in, sign and date the pair programming contract and BOTH partners submit.
  • Only ONE partner submits the lab assignment on Canvas. Please make sure both your names are on ALL the files.

Part 1: Revise your List.java file from Lab 2
  • Look back over my comments on your Lab 2.
  • Make any changes to your code that I suggested.
  • Also, look over your own code as it is possible that I missed something the first time, but will not miss it when I look at your code again for this assignment.
  • Including other errors that might have been made in Lab 2, please make sure you check for the following:
  • Did you provide a complete comment for all of your methods in your List.h?
  • Do you have the correct preconditions for all methods with a precondition?
  • Are you testing for the correct preconditions in your iterator methods (Hint: these should ALL be iterator != NULL or !offEnd()) and are you throwing the correct exception (NullPointerException) in this case?
  • Did you remove the loop from removeLast and update the method to utilize the last.prev reference?
  • Did you move the iterator when your wrote printNumberedList?
  • I will again be looking over your List class and deducing points for any method that are not correctly implemented.
  • Please ask me if you are uncertain about something.

Part 2: Add New Methods to Your List.java Class
  • Note: don't erase any of your methods from Lab 2. Just add more methods to this file.
Recursive Print (20 pts)

  • Please write the recursive List printReverse method, whose iterative version we wrote in class.
  • Below are the method signatures for the methods you are going to need:

   
    /**Additional Operations*/

    /**
     * Prints a linked list to the console
     * in reverse by calling the private
     * recursive helper method printReverse
     */
    public void printReverse() {
       return;
    }
   
    /**
     * Prints a linked list to the console
     * recursively (no loop)
     * in reverse order from last to first
     * Each element separated by a space
     * Should print a new line after all
     * elements have been displayed
     */   

    private void printReverse(Node n) {
        return;
    }
   

  • Why do we need the private helper method here?
    • Since we are going to be reversing the List Node-by-Node, in a recursive fashion, we want to pass one Node at a time to the reversePrint method.
    • However, since Nodes are private, we cannot access them outside of the List class.
    • Therefore, we write the public printReverse method whose main task is to call the private printReverse method.
    • It is the private printReverse method that does most of the work.
    • However, we can call the public printReverse method in ListTest.java without provoking an error.
  • Add the above method signatures to List.java under the additional operations section.
  • Important: Test each method carefully inside of your ListTest.java to make sure that it is working properly.
  • Then, write a JUnit test class for printReverse called PrintReverseTest.java.


Recursive Method to Determine if a List is in Sorted Order (20 pts)


  • Write a recursive method to determine whether or not a Linked List is in sorted order (smallest value to largest value).
  • First, update your class signature as follows to extend Comparable.
public class List<T extends Comparable<T>> {
  • Because we want to call compareTo to compare data of type T in the below isSorted method, we need to make sure our class extends Comparable
  • Add the following method signatures to List.java class under the section for accessor methods.

    /**Accessor Methods*/     

    /**
     * Determines whether a List is sorted
     * by calling the recursive helper method
     * isSorted
     * Note: A List that is empty can be
     * considered to be (trivially) sorted
     * @return whether this List is sorted
     */
    public boolean isSorted() {
        return false;
    }
   
    /**
     * Recursively determines whether
     * a List is sorted in ascending order
     * @return whether this List is sorted
     */
    public boolean isSorted(Node n) {
        return false;
    }

  • Test your method in ListTest.java and also in IsSortedTest.java - the unit test class for isSorted wrapper and helper
Adding an Index to Your List Nodes (20 pts)
  • Next, add the following methods to List.java.
  • The purpose of these methods will be to simulate adding an index to each node in the List, without updating the Node class to store an index.
  • Note that no other changes will be necessary to create an indexing system other than implementing these two methods.
  • Please do not add an additional field to your node struct for a node's index or an additional field in your List class.
  • These two methods will create the effect of an index without the need for an additional field in the Node class.


/**Accessor Methods*/


/**
     * Returns the index of the iterator
     * from 1 to n. Note that there is
     * no index 0.
     * @precondition
     * @return the index of the iterator
     * @throws NullPointerException when
     * the precondition is violated
     */
    public int getIndex() throws NullPointerException{
        return -1;
    }


/**Manipulation Procedures*/

/**
     * Points the iterator at first
     * and then iteratively advances
     * it to the specified index
     * @param index the index where
     * the iterator should be placed
     * @precondition 1 <= index <= length
     * @throws IndexOutOfBoundsException
     * when precondition is violated
     */
    public void moveToIndex(int index) throws IndexOutOfBoundsException{
       
    }

  • You can visualize the idea of the index with the below diagram
depiction of a list with 3 nodes, indices 1, 2 and 3

  • Note that in the above diagram, the a call to the getIndex method would return 2, as the iterator is pointing at the second node in the List.
  • Note that your List should be doubly-linked, although the above image depicts a singly-linked list.
  • Test your methods in ListTest.java and also in GetIndexTest.java and MoveToIndexTest.java - the unit test classes for these two methods.

Implementing Search as Part of Your List (40 pts)

  • Now, we are going to add two search methods to the List class - linear and binary search
  • The first of these methods is going to be a simple linear search method. 
  • Note that the pseudocode for the two methods is given in the class notes.
  • If you are uncertain how to begin, the best approach would be to look at the notes from the Lesson 7 and 8.
  • You will need to add the following method signature to your List.java:
/**Accessor Methods*/

/**
     * Searches the List for the specified
     * value using the iterative linear
     * search algorithm
     * @param value the value to search for
     * @return the location of value in the
     * List or -1 to indicate not found
     * Note that if the List is empty we will
     * consider the element to be not found
     * @postcondition: position of the iterator remains
     * unchanged!
     */
    public int linearSearch(T value) {
        return -1;
    }
  • Next, add a method to perform recursive binary search on the List.
  • Please note that you will receive no credit for your binarySearch method if it is not implemented recursively.
  • You will need to add the following method signature to List.java:

/**Accessor Methods*/

/**
     * Returns the index from 1 to length
     * where value is located in the List
     * by calling the private helper method
     * binarySearch
     * @param value the value to search for
     * @return the index where value is
     * stored from 1 to length, or -1 to
     * indicate not found
     * @precondition isSorted()
     * @postcondition the position of the
     * iterator must remain unchanged!
     * @throws IllegalStateException when the
     * precondition is violated.
     */
    public int binarySearch(T value) throws IllegalStateException {
        return -1;
    }
   
    /**
     * Searches for the specified value in
     * the List by implementing the recursive
     * binarySearch algorithm
     * @param low the lowest bounds of the search
     * @param high the highest bounds of the search
     * @param value the value to search for
     * @return the index at which value is located
     * or -1 to indicate not found
     * @postcondition the location of the iterator
     * must remain unchanged
     */
    private int binarySearch(int low, int high, T value) {
        return -1;
    }

  • Important: For credit, you must implement the recursive version of binary search.
  • Note: for these two methods, do not change the position of the iterator (side effect).
  • Thus, you will not be able to call your index methods from the section above.
  • To implement binarySearch, you can adapt the pseudocode provided below for binarySearch on an array.
  • Test your methods in ListTest.java and also in LinearSearchTest.java and BinarySearchTest.java - the unit test class for linearSearch and binarySearch wrapper and helper

Recursive Binary Search Pseudocode

Pre: A[] is sorted in increasing order
method binarySearch(A[1 ... n], value, low, high)
    if high < low
        return not found
    mid := low + (high-low)/2; //the midpoint formula
    if a[mid] := value
        return mid
    else if value < A[mid] //search the left half
        return binarySearch(A, value, low, mid-1)
    else //search the right half
        return binarySearch(A, value, mid+1, high)

Linear Search Pseudocode:

For each item in the list:
     if that item has the desired value
         stop the search and return the item's location.
 return -1.


What to Submit

  • Please submit your List.java file, your ListTest.java file and your 6 unit test classes (3 calls to assertEquals() per class) to Canvas when you are finished.
  • Note that you should have tested all preconditions, edge cases and "normal" cases of the methods that you have added to List.java in this Lab to receive full credit. 
  • Optional: Submit your pair programming worksheet to Canvas (both partners)

How You Will Be Graded

  • 15 points for a fully operational printReverse() wrapper and helper method and 5 points for fully testing these methods
    (2 calls to method inside of ListTest.java)
  • 15 points for a fully operational isSorted() wrapper and helper method and 5 points for fully testing these methods
    (JUnit test with 3 assertEquals and 2 calls to method inside of ListTest.java)
  • 7 points for a fully operational getIndex() method and 3 points for fully testing this method (JUnit test with 3 assertEquals and 2 calls to method inside of ListTest.java)
  • 7 points for a fully operational moveToIndex() method and 3 points for fully testing this method (JUnit test with 3 assertEquals and 2 calls to method inside of ListTest.java)
  • 15 points for a fully operational linearSearch() method and 5 points for fully testing this method (JUnit test with 3 assertEquals and 2 calls to method inside of ListTest.java)
  • 15 points for a fully operational binarySearch() wrapper and helper method and 5 points for fully testing these methods (JUnit test with 3 assertEquals and 2 calls to method inside of ListTest.java)
  • No credit for the binary search method if you do not implement recursive binary search using the above pseudocode as a guide..
  • Be careful! Each of these methods is worth a lot of points for this lab. If you get one wrong, you will miss a lot of points for just one method.
  • Please get help if you are uncertain and test your code thoroughly (consider edge cases - especially with the search methods - think searching for the first or last element in the List)!
  • The #1 mistake I see in this lab is to forget that the List is indexed from 1 to the length (not starting at 0)
  • Optional: 5 points extra credit for pair programming