CS 112 Spring, 2017 -- Homework Six

Due Thursday, July 27th at midnight

Introduction

This consists of several programming problems. In addition to the requirements for the Java problems, you must observe the following requirements (for all homework submitted in this course):

Part A: Analytical Problems (10 points)

The questions below are designed to reinforce the material exposed to you at lecture and from assigned readings. Please submit your answers as a file hw04.txt.

Before getting started on the remaining problems, review the lecture and textbook materials on binary search trees and recursion. The following problems have to do with the BST in this diagram:

1. (5 parts): For this tree, give the (a) size, (b) depth of the node 31, (c) height, (d) length of the path from 11 to 49, and (e) list of all leaf nodes.

2. (2 parts) (a) Draw the result of inserting the keys 15, 7, 16, 12, & 13 into this tree; (b) assuming we can only insert integers, and no duplicates, into the original tree, what keys could possibly be inserted to the left of 31?

3. (2 parts) (a) Draw the result of taking the tree in the diagram and deleting the root three times using the deletion algorithm from lecture (Wed 7/26); (b) suppose we do not wish to unbalance the tree by deleting from the same side each time, and we decide that we will alternately delete from the right, left, right, left, etc. (starting with the right); delete the root of the tree in the diagram 4 times using this new strategy and show the resulting tree.

4. (2 parts) Let us call a tree "perfect" if it is a perfect triangle, i.e.,

Suppose H is the height of a perfect binary tree, and N the number of nodes; (a) express H as a function of N, and (b) N as a function of H.

5. (2 parts): Suppose we are going to insert the letters A, B, C, and D, into an initially empty BST. If we insert them in order, we get a pathological tree which is really just a linked list (and whose worst case time to find a node is linear, i.e., O(N)). But there are many different worst cases! (a) List 5 more of the the possible worst cases (hint: there are 8 in all!). Now suppose we have the letters A, B, C, D, E, F, and G. We would like to have a perfect tree which has the shape of a perfect triangle: for example, we could insert in the order D, B, F, A, C, E, G. (b) List 5 more of the possible insertion orders that would give you a complete binary search tree.

Part B: Programming Problems (90 points)

Problem 1 (Lab Problems) (10 points)

Hand in your two files from lab on Tuesday and Wednesday.

Problem 2 (40 points)

For this problem you will write a number of methods for manipulating linked lists recursively. You must implement each of the following methods as specified, and also must test each method thoroughly. For the first time, I will be expecting you to test some of these methods yourself. In general, to thoroughly test your code, you will need to exercise your methods on linked list examples which try all possible cases. A template, with an example of what you should do is here: RecursiveLinkedLists.java. Fill in the rest of the file with your code for each method below, and fill in the unit tests (you may simply use the examples shown below as appropriate).

You may not use loops anywhere in this problem, as it is practice in using recursion on linked lists. Some of these methods will seem familiar, as you implemented them in the last homework as well, but this time you must do them recursively! In some of the functions, you will need to write a non-recursive "wrapper method" which sets up the recursive "helper method" which does most of the work!

The examples given are intended to illustrate the basic idea of the method, and are not intended to be an exhaustive set of test cases.

You may write any helper methods you wish as long as they do not use loops. The starred problems are identical to problems from the last homework, except now you must implement them recursively. See the example of put(...) and putHelper(....) in the next problem for an example of how to do this.

A. Write a method Node arrayToLinkedList(int[] A) which takes an array A of integers and creates a linked list with the same numbers in the same order (that is, the integer in A[0] would be the first node in the list. For example:

int[] B = { 2, 5, 4 };

Node p = arrayToLinkedList(B);
System.out.println(p);

// this would produce:
 
-> 2 -> 5 -> 4 -> .

B. Write a method int count(int n, Node p) which returns the number of times that n occurs in the linked list p. For example:

p -> 2 -> 5 -> 4 -> 6 -> 2 -> 9 -> .

q -> . 

count(2,p)  => 2                      //  recall that "=>" means "returns the value"

count(2,q) => 0

count(7,p)  => 0

C*. Write a method double mean(Node p) which returns the mean of the integers in the list. You may NOT call any other other method (e.g., length(...)) for this, and you MUST do it with ONE recursive pass down and back up the list. Thus, you will have to use the technique illustrated in example 2 in the section Doing a Running Calculation... in the notes on Recursion and Linked Lists (hint: your helper function will have three arguments: the list, an accumulator holding the count of the number of nodes, and an accumulator holding the sum of the integers--the base case will calculate the mean and pass it back up.) The mean of the empty list is 0. For example:

p -> 2 -> 5 -> 4 -> 3 -> 2 -> 5 -> .

q -> 1 -> .

mean(p)     =>  3.5    

mean(q)     =>  1                    

mean(null)  =>  0.0

D. Write a method Node deleteNth(Node p,int n) which takes a linked list p and deletes the nth node, where we start to count at 0, so calling the function with n=0 would delete the node containing 2 in the list p below, with n=2, would delete 4, etc. You will change the original list p, so no need to make a copy inside the method; HOWEVER, in the tests, you want to reuse the list p unchanged each time, so design your test so that it makes a copy and leaves p unchanged for the next test:

         System.out.println("\nTest 09  deleteNth:  should print out:\n -> 2 -> 5 -> 6 -> 2 -> 9 -> .");
         System.out.println(deleteNth(copy(p),2));

If n > length of the list, do nothing. You may assume that n >= 0. For example:

p -> 2 -> 5 -> 4 -> 6 -> 2 -> 9 -> .

p = deleteNth(p,2)                      // but remember in the actual tests to make a copy of p

This would produce:
 
p ->2 -> 5 -> 6 -> 2 -> 9 -> .

----------------------------------------------

p -> 2 -> 5 -> 4 -> 6 -> 2 -> 9 -> .

p = deleteNth(p,0)

This would produce:
 
p -> 5 -> 4 -> 6 -> 2 -> 9 -> .

----------------------------------------------

p -> 2 -> 5 -> 4 -> 6 -> 2 -> 9 -> .

p = deleteNth(p,13)

This would produce:
 
p -> 2 -> 5 -> 4 -> 6 -> 2 -> 9 -> .

----------------------------------------------

a -> .

a = deleteNth(a,0)

This would produce:
 
a -> .

----------------------------------------------

E. Write a Java function Node everyOther(Node p) which takes a list p and returns a list consisting of the 0th, 2nd, 4th, etc. nodes, starting to count with 0 at the head of the list (you will destroy the original list to do this). Your method should work with empty lists, lists with an odd number of elements, and those with an even number of elements. (Hint: Write a helper function which takes as arguments a list and a count of the number of nodes encountered so far.)

For example:

head -> .

Node q = everyOther(head); 

results in:

q -> .

----------------------------------------------

head -> 4 -> 5 -> 7 ->  .

Node q = everyOther(head); 

results in:

q -> 4 -> 7 -> .

----------------------------------------------

head -> 4 -> 5 -> 7 -> 2 -> 8 -> 1.

Node q = everyOther(head); 

results in:

q -> 4 -> 7 -> 8 -> .

F*. Write a Java function boolean equalLists(Node p, Node q) which takes two lists and returns true if and only if they have the same elements in the same order. They do not have to be the same pointer, just structurally identical (similar to how equals(...) works on Strings).

For example:

p -> 5 -> 9 -> 1 -> .

q -> 5 -> 9 -> 1 -> .

r -> 5 -> 9 -> .

s -> 5 -> .

t -> .


equalLists(p,p)  =>   true

equalLists(q,p)  =>   true

equalLists(q,r)  =>   false

equalLists(r,s)  =>   false

equalLists(p,t)  =>   false

equalLists(t,null)  =>   true  

G. Write a method boolean prefix(Node p, Node q) which takes two lists and returns true if the list p is a prefix of the list q, that is, has the same exact elements as the initial part of q.

For example:

p -> 5 -> 9 -> 1 -> .

q -> 5 -> 9 -> 1 -> .

r -> 5 -> 9 -> .

s -> 1 -> 6 -> 6 -> .

t -> .


prefix(p,q)  =>   true

prefix(r,q)  =>   true

prefix(p,r)  =>   false

prefix(t,s)  =>   true          // Note: the empty list is a prefix of any list!

prefix(s,t)  =>   false

prefix(t,null)  =>   true  

H. Write a method boolean sublist(Node p, Node q) which takes two lists and returns true if the list p is a contiguous sublist of the list q, that is, has the same exact elements, next to each other in the same order, as a part of the list q (as if you took q and possibly added some elements at the beginning and the end to get p). You may assume there are no duplicates in the lists, which are unordered. (Hint: use the previous method to check as you recurse down the list q.)

For example:

p -> 4 -> 2 -> 5 -> 9 -> 1 -> 6 ->.

q -> 5 -> 9 -> 1 -> .

r -> 1 -> .

s -> 5 -> 1 -> .

t -> .

u -> 5 -> .

sublist(p,p)  =>   true

sublist(q,p)  =>   true

sublist(s,p)  =>   false         // all elements of s occur in p, in same order, but not as a contiguous sublist!

sublist(r,p)  =>   true

sublist(r,q)  =>   true

sublist(u,q)  =>   true

sublist(t,null)  =>   true

sublist(t,p)  =>   true             // Note: empty list is a sublist of any list!

sublist(q,s)  =>   false

sublist(p,q)  =>   false

sublist(r,t)  =>   false

I. Write a method Node splice(int n, Node p, Node q) which takes two lists and inserts the list q into the middle of list p, right before the nth node in list p (the first node in the list would be at n = 0). if n >= number of nodes in list, then just add at the end. It will modify both lists (i.e., no need to make copies). In terms of the previous problem, you are putting p into q so that p is a sublist of the result.

head -> 1 -> 2 -> 3 -> .

other -> 5 -> 6 -> 7 -> .

Here is an example of various calls to splice (these are NOT sequential, that is, each one shows what splice would do
when called individually on the lists above, NOT in the context of the previous calls to splice):

Node q = splice(1,head,other); 

      q -> 1 -> 5 -> 6 -> 7 -> 2 -> 3 -> .

----------------------------------------------

Node q = splice(3,head,other); 

      q -> 1 -> 2 -> 3 -> 5 -> 6 -> 7 -> .

----------------------------------------------

Node q = splice(0,head,other); 

      q -> 5 -> 6 -> 7 -> 1 -> 2 -> 3 -> .

----------------------------------------------

Node q = splice(10,head,other); 

      q -> 1 -> 2 -> 3 -> 5 -> 6 -> 7 -> .            // if n > number of nodes in list, then just add at the end

----------------------------------------------

r -> .

Node q = splice(0,head,r); 

      q -> 1 -> 2 -> 3 -> .                  // splicing the empty list into a list head just returns head, no matter
                                             // what n is

----------------------------------------------

r -> .

Node q = splice(2,r,head); 

      q -> 1 -> 2 -> 3 -> .                  // splicing a list into an empty list just returns the list, no matter
                                             // what n is

----------------------------------------------


You may use append(...), from the Notes, as a helper method if you wish. 

J. Write a method Node intersection(Node p, Node q) which takes two ordered lists of integers, and returns a new list of all the numbers which occur in both lists; that is, do not destroy the original lists, but create new nodes for all numbers which are common to both lists. You may assume that the original lists have no duplicates, and of course no duplicates should appear in the result (think if this as intersection on sets, where sets are represented by ordered lists.) The list returned should also be in order.


Here is an example of various calls to intersection(...) (as in the last problems, these are independent of each other):

----------------------------------------------

a -> 2 -> 3 -> 4 -> 5 -> 6 -> .          
b -> 1 -> 2 -> 4 -> 5 -> . 

r = intersection(a,b)

r -> 2 -> 4 -> 5 -> .                      // this is a new list, the original lists are unchanged. 

----------------------------------------------

a -> 2 -> 3 -> .          
b -> 1 -> 4 -> 5 -> . 

r = intersection(a,b)

r -> .

----------------------------------------------

a -> 2 -> 3 -> 4 -> 5 -> 6 -> .          
b -> . 

r = intersection(a,b)

r -> .

----------------------------------------------
   

[Hint: There are various approaches. You could make a copy of one of the lists, then delete those elements which don't occur in the other; or modify the merge(...) algorithm so that it creates a new node when it finds two of the same integer at the head of the two lists. ]

NOTE 1: For this problem, it will again be YOUR TURN to write the performance tests in the main method. You may reuse tests from the previous homework, but for some (those not starred above), you will need to write your own tests. You may use the examples above as a model for your tests. Follow the way we have written tests in previous homeworks (numbering them "Test 1" and so on). Remember that errors most often occur in the "boundary conditions": when one of the lists is null, or when the interesting activity occurs at the beginning or end of the list. I will be writing my own tests in the grading clients, and so be sure to test your methods thoroughly!

NOTE 2: Please be sure to read the caveat in case D above. To repeat: for any method which modifies its input, be careful about whether you are changing a list that will be used again in a later test. Thus, for splice(...), if you created lists head and other to use in the tests, you should call splice like this in the tests:

Node q = splice(1,copy(head),copy(other)); 

Do NOT make a copy of the list inside the methods, but simply make a copy for the purposes of testing your code.

NOTE 3: Making linked lists can be a pain, which is why I asked you to write the method to turn arrays into linked lists. Here is a nice way to create linked lists using this technique, plus the constructor for arrays:

Node p = arrayToLinkedList( new int[] { 4,2,5 } );

// Now the list is  p -> 4 -> 2 -> 5 -> .

Problem 3: Symbol Table ADT -- 40 pts

For this problem, you are going to write a program SymbolTable.java which stores variables (just Strings) and associated values (of a generic type); such a data structure is used in all programming languages during compilation (e.g., Java) or interpretation (e.g., Python) to store information associated with variables. The SymbolTable class will be generic in that it can store any kind of object as values (in the unit test, we will create two different symbol tables, one holding Integers and one holding Strings). The data structure used to store the variables and values will be a linked list created from the following Node class:

  private class Node {                 // Node class for LLs
    String variable;
    Value value;
    Node next;
    
    public Node(String k, Value v, Node p) {   // Constructor
      variable = k; value = v; next = p;
    }
  }

  Node head = null; 

This class will be an "inner class" of the SymbolTable class, that is, a class defined inside another class, and all the information about the linked list will be private. Here is a template to get you started: SymbolTable.java. The linked list will be kept in ascending lexicographic order, (you will use compareTo(...) to compare the Strings when doing insertion). Note that the ordering used is the same as in a dictionary, and in fact, a symbol table IS a dictionary, where the "meaning" of a symbol is the value associated with each variable name.

You may NOT use loops to process the linked lists, and hence you will have to write recursive algorithms for those methods that require moving down the linked list. The only loops that will occur in your program will be those that I wrote in the Unit Tests.

NOTE: Please review carefully the Notes on Recursion and Linked Lists before starting this. This page contains a "cookbook" of common algorithms for manipulating LLs recursively; most of what you need to do in this problem can be found there.

Interface

The interface for the symbol table is as follows (cut and paste into a new interface in your hw6 src directory):

/*
 * File: Dictionary.java 
 * Author: Wayne Snyder 
 * Date: July 24th, 2017 
 * Purpose: interface for dictionary in hw06, CS 112, Summer 2, 2017.
 */

package hw6;

import java.util.Iterator;

public interface Dictionary {

  // NOTE: comments precede the method stub they specify  -- You do not need to make any changes to this file

  /*
   * If the variable var is not in the symbol table, insert a new node containing var and val into
   * the linked list in ascending order (do NOT sort the list, but insert in order of the variable
   * field); if var is already in the table, then simply replace the existing value with the new
   * value val. The type Value is a generic type.
   */

  public void put(String var, Value val);

  /*
   * Return the value associated with the variable var, or throw the exception if var is not in the table.
   */

  public Value get(String var) throws KeyNotFoundException ;

  /*
   * Return true or false, depending on whether var is in the table or not.
   */

  public boolean contains(String var);

  /*
   * Remove the node containing var from the table; if var is not in the table, do nothing.
   */

  void delete(String var);

  /*
   * Return the smallest variable in the lexicographic ordering (this will be in the first node in
   * the list); if the table is empty, throw the exception. 
   */

  public String min() throws KeyNotFoundException ;

  /*
   * Similar to the previous, but return the largest entry, which will be in the last node in the
   * linked list.
   */

  public String max() throws KeyNotFoundException ;

  /*
   * If the table is empty or if var is smaller than the smallest entry, throw the exception; if var is in
   * the table, return var; otherwise, return the largest variable which is less than var (the entry
   * just before where var would be inserted into the table). If var is larger than the maximum key
   * in the table, return that maximum key. Do NOT insert var into the table if it is not there.
   * This is comparable to the mathematical function floor(...). [Hint: During the recursion, if
   * your current key equals var, then return it; else you should "look ahead" to see what
   * the next key is (checking first whether it is null!), and if the next key is larger than var,
   * or if there is no next key, your current key should be returned.]
   */

  public String floor(String var) throws KeyNotFoundException ;

  /*
   * If the table is empty or if var is larger than the largest entry, throw the exception; if var is in the
   * table, return var; otherwise, return the smallest variable which is larger than var (the entry
   * just after where var would be inserted into the table). (Do NOT insert var into the table!)
   * This is comparable to the mathematical function ceiling(...).
   */

  public String ceiling(String var) throws KeyNotFoundException ;

  /*
   * Return the "rank" of var, i.e., the number of entries in the table which are smaller
   * than var; the rank of variables which are in the table is calculated by counting 0, 1, 2,
   * starting at the first node (as if it were an array); if var is not in the table, then it is the
   * rank where var would be if it were inserted (do NOT insert var into the table).
   */

  public int rank(String var);

  /*
   * Return the variable which is at rank n in the linked list (starting the count at 0 with the
   * first node, as in an array). If the table is empty, or if n is not the rank of any element, i.e., it is negative or is
   * equal to or larger than the length of the linked list, throw the exception. You are essentially just
   * returning the variable at location n in the list, but starting the count with 0 at the first
   * node. 
   */

  public String select(int n) throws KeyNotFoundException ;

  /* Remove the smallest (i.e., first) entry in the table; if the table is empty, do nothing. */

  public void deleteMin();

  /*
   * Remove the largest (i.e., last) entry in the table; if the table is empty do nothing. Hint: you
   * can directly use a method from the Notes.....
   */

  public void deleteMax();

  /*
   * Return the number of entries in the table (the length of the linked list); you should keep
   * track of this with a private variable size, which is updated when you remove
   * or add an entry.
   */

  public int size();

  /*
   * Return the number of entries in the table whose variables are in the range [lo .. hi], that is,
   * that are >= lo and <= hi (using the appropriate String comparison operators). (Hint: use
   * the same "example 2" method as suggested in the case of mean(...) in problem B.2: go
   * down the list and keep a count of the number of variables which are in the range.)
   */

  public int size(String lo, String hi);

  /* Return true if the table has no entries, and false otherwise. */

  public boolean isEmpty();
  
  /*   This is an iterator for the variables in the table, as discussed in lab this week, 
   *   and this will be sufficient for the class SymbolTable to satisfy the Iterable interface.
   */

  public Iterator iterator();

  /*   This is similar to the previous, but the iterator should only enumerate keys in the 
   *   range [lo .. hi]. Hint: Initialize the iterator at the node containing the variable 
   *   ceiling(lo), and have hasNext() return false when you are at a variables larger than hi. 
   *   Note that each of these iterators is separate and requires a separate cursor.
   */

  public Iterator iterator(String lo, String hi);


}


    

These are the basic methods of the interface, implementing the most important symbol table operations. You may NOT use loops to process the linked list, and so recursion will play a central role in many of these. In this case, you may need to write the interface method as a "wrapper method" which calls a private recursive method, for example,

public void put(String var, Value val) {
      head = putHelper(var, val, head);           // set up the call to the helper method
 }
 
private Node putHelper( String var, Value val, Node p ) {
    if(p == null) 
       return new Node(var, val);
    else 
    
    ...   etc.   .....

    else {
       p.next = putHelper( var, val, p.next ); 
       return p;
    }
}
       

You can create any other methods you want, but if they are not in the interface make them private. For example, you may find it useful to create a method:

    // Helper method, returns pointer to node containing k, or null if not found 

    private Node find(String s) {
        return find(s,head);
    }
      
    private Node find(String k, Node p) { .... }

which can be used in various places, for example, once find(...) has been implemented, then contains(...) is easy:

    public boolean contains(String k) {
        return (find(k) != null);  
    }

Unit Test:

The template code SymbolTable.java contains the class, the basic Node definition, a toString() method, stubs for all the methods, and also a unit test which will be used to grade your submission. Please read carefully my comments about the iterator code. In order to make this compile, so you could use step-wise refinement, I have had to comment out various parts of the class. It should be clear what to do.

This assignment was inspired by a discussion of ordered symbol tables from the book Algorithms by Robert Sedgewick and Bruce Wayne, which may be found here: PDF. You may want to read through this section of the text, but I have changed several things about the assignment (in particular, the keys are Strings, not generic, and we are using null values to report errors. As long as you understand the differences, you may find it profitable to read through this section; the following figure shows some of the operations that are implemented in the second part of the unit test:

Note: The function which we call iterator(...) is shown here as keys(...). Also note that the keys and values are Strings, but these are shown without quote marks around them.

Submission:

Files to submit:

Make sure that all programs are properly commented, neat and readable, all debugging trace statements are turned off or removed, and verify that you correctly pass all the performance tests in the unit tests.

You will need to follow the style guidelines about comments, especially a header comment, described in the Java Style Guidelines linked at the top of this document. Also, you MUST format your code using the Eclipse Format command. Make sure your program is neat and readable by humans!!!

You will receive a grading penalty if you do not follow these requirements.