CSC300 / CSC402: Homework (MyDeque, MyDequeUsingStacks): Homework (MyDeque, MyDequeUsingStacks)

CSC300 / CSC402: Homework (MyDeque, MyDequeUsingStacks) [1/1]

Study for the Midterm!
Read Algorithms 1.1, pp 46-47 (Binary Search).
Read Algorithms 1.4 and 1.5 (updated!).
Note: Homework and quiz deadlines are changing from what you're used to.

The next due date for homework and quizzes is after the Midterm.
- CSC 300 (undergrad): Your homework and quiz deadlines will be on Sundays at 5:45pm.
- CSC 402 (graduate): Your homework and quiz deadlines will be on Mondays at 5:45pm.
- Students may use up to one flex day at a time (if you have any remaining). Flex days will expire at 5:45pm on the day of the live class so we can go over the material when we meet.
You have about 1.5 weeks for this homework so you can focus on the Midterm for next week.

My rationale for this change is to still allow you to use flex days, or submit late for partial credit, but ensure that all submissions are complete by the time the in-person class meets. That way, we can go over the material in class shortly after it is due.
Look for a quiz on D2L.
Complete MyDeque.java and MyDequeUsingStacks.java. Do MyDeque.java first!

Here are some pictures showing the expected results for MyDeque.java (Note that the Professor Version is YDeque.java.)
- My main method, with line numbers.
- A PDF showing the state of each line. This is best viewed in single page view, rather than continuous
- A ZIP file containing the same images as PNGs. You can view them with other software on your computer
- The same PNGs, online

file:MyDeque.java [source]

package algs13;
import stdlib.*;
import java.text.DecimalFormat;
import java.util.NoSuchElementException;

/**
 * This is a skeleton file for your homework.
 * Complete the functions below. 
 * You may also edit the function "main" to test your code.
 * 
 * You should not use any loops or recursions, except in "delete"
 * Delete may use one loop or recursive helper.
 *
 * You must not add fields or static variables.
 * As always, you must not change the declaration of any method.
 * Do not change any of the methods I have provided, such as "toString" and "check".
 */

public class MyDeque {
  Node first = null;
  Node last = null;
  int N = 0;

  static class Node {
    public Node (double item) { this.item = item; }
    public double item;
    public Node next;
    public Node prev;
  }

  public MyDeque ()         { };
  public boolean isEmpty () { return N == 0; }
  public int size ()        { return N; }

  public void pushLeft (double item) {
    // TODO
  }

  public double popLeft () {
    if (N == 0) throw new NoSuchElementException ();
    return StdRandom.uniform ();
    // TODO
  }

  public void pushRight (double item) {
    // TODO
  }
  
  public double popRight () {
    if (N == 0) throw new NoSuchElementException ();
    return StdRandom.uniform ();
    // TODO
  }

  /* The concat method should take the Nodes from "that" and add them to "this"
   * After execution, "that" should be empty.
   * See the tests in the main program.
   *
   * Do not use a loop or a recursive definition.
   * This method can declare Node variables, but may not create new node objects (using "new").
   * Therefore the method should not call pushLeft or pushRight (which use create new objects).
   */
  public void concat (MyDeque that) {
    // TODO
  }

  /* Delete should delete and return the kth element from the left (where k is between 0 and N-1).
   * See the tests in the main program.
   *
   * You may use a loop or a recursive definition here.
   * This method can declare Node variables, but may not create new node objects (using "new").
   * Therefore the method should not call pushLeft or pushRight (which use create new objects).
   */
  public double delete (int k) {
    if (k < 0 || k >= N) throw new IllegalArgumentException ();
    return StdRandom.uniform ();
    // TODO 
  }


  public static void main (String args[]) {
    // TODO: Uncomment these lines to use the visual debugger
    // Note, however, that this will substantially slow things down
    // So you should leave these commented unless you are using the debugger
    //
    // Trace.drawStepsOfMethod ("main");
    // Trace.drawStepsOfMethod ("pushLeft");
    // Trace.run ();

    // Here are some tests to get you started.
    // You can edit this all you like.
    MyDeque d1, d2, d3;
    double k;

    ////////////////////////////////////////////////////////////////////
    // push/pop tests
    ////////////////////////////////////////////////////////////////////
    d1 = new MyDeque ();
    d1.pushLeft (11);
    check ("left1", d1, "[ 11 ]");
    d1.pushLeft (12);
    check ("left2", d1, "[ 12 11 ]");
    d1.pushLeft (13);
    check ("left3", d1, "[ 13 12 11 ]");
    k = d1.popLeft ();
    check ("left4", d1, "[ 12 11 ]", k, 13);
    k = d1.popLeft ();
    check ("left5", d1, "[ 11 ]", k, 12);
    k = d1.popLeft ();
    check ("left6", d1, "[ ]", k, 11);

    d1 = new MyDeque ();
    d1.pushRight (11);
    check ("right1", d1, "[ 11 ]");
    d1.pushRight (12);
    check ("right2", d1, "[ 11 12 ]");
    d1.pushRight (13);
    check ("right3", d1, "[ 11 12 13 ]");
    k = d1.popRight ();
    check ("right4", d1, "[ 11 12 ]", k, 13);
    k = d1.popRight ();
    check ("right5", d1, "[ 11 ]", k, 12);
    k = d1.popRight ();
    check ("right6", d1, "[ ]", k, 11);

    d1 = new MyDeque ();
    d1.pushLeft (11);
    check ("left/right1", d1, "[ 11 ]");
    d1.pushRight (21);
    check ("left/right2", d1, "[ 11 21 ]");
    d1.pushLeft (12);
    check ("left/right3", d1, "[ 12 11 21 ]");
    d1.pushRight (22);
    check ("left/right4", d1, "[ 12 11 21 22 ]");
    k = d1.popLeft ();
    check ("left/right5", d1, "[ 11 21 22 ]", k, 12);
    k = d1.popLeft ();
    check ("left/right6", d1, "[ 21 22 ]", k, 11);
    k = d1.popLeft ();
    check ("left/right7", d1, "[ 22 ]", k, 21);
    k = d1.popLeft ();
    check ("left/right8", d1, "[ ]", k, 22);

    d1 = new MyDeque ();
    d1.pushLeft (11);
    check ("left/right10", d1, "[ 11 ]");
    d1.pushRight (21);
    check ("left/right11", d1, "[ 11 21 ]");
    d1.pushLeft (12);
    check ("left/right12", d1, "[ 12 11 21 ]");
    d1.pushRight (22);
    check ("left/right13", d1, "[ 12 11 21 22 ]");
    k = d1.popRight ();
    check ("left/right14", d1, "[ 12 11 21 ]", k, 22);
    k = d1.popRight ();
    check ("left/right15", d1, "[ 12 11 ]", k, 21);
    k = d1.popRight ();
    check ("left/right16", d1, "[ 12 ]", k, 11);
    k = d1.popRight ();
    check ("left/right17", d1, "[ ]", k, 12);

    ////////////////////////////////////////////////////////////////////
    //  test exceptions
    ////////////////////////////////////////////////////////////////////
    try {
      d1.popLeft ();
      showError ("Expected exception1");
    } catch (NoSuchElementException e) {}
    try {
      d1.popRight ();
      showError ("Expected exception2");
    } catch (NoSuchElementException e) {}

    ////////////////////////////////////////////////////////////////////
    // concat tests (and more push/pop tests)
    ////////////////////////////////////////////////////////////////////
    d1 = new MyDeque ();
    d1.concat (new MyDeque ());
    check ("concat1", d1, "[ ]");
    d1.pushLeft (11);
    d1.concat (new MyDeque ());
    check ("concat2", d1, "[ 11 ]");

    d1 = new MyDeque ();
    d2 = new MyDeque ();
    d2.pushLeft (11);
    d1.concat (d2);
    check ("concat3a", d1, "[ 11 ]");
    check ("concat3b", d2, "[ ]");

    d1 = new MyDeque ();
    d2 = new MyDeque ();
    d1.pushLeft (11);
    d1.pushLeft (12);
    d2.pushLeft (21);
    d2.pushLeft (22);
    d1.concat (d2);
    check ("concat4a", d1, "[ 12 11 22 21 ]");
    check ("concat4b", d2, "[ ]");
    d2.concat (d1);
    check ("concat5a", d2, "[ 12 11 22 21 ]");
    check ("concat5b", d1, "[ ]");

    d1 = new MyDeque ();
    for (int i = 10; i < 13; i++) { d1.pushLeft (i); checkInvariants ("left1", d1); }
    for (int i = 20; i < 23; i++) { d1.pushRight (i); checkInvariants ("right2", d1); }
    check ("concat6", d1, "[ 12 11 10 20 21 22 ]");
    d2 = new MyDeque ();
    d1.concat (d2);
    check ("concat7a", d1, "[ 12 11 10 20 21 22 ]");
    check ("concat7b", d2, "[ ]");

    for (int i = 30; i < 33; i++) { d2.pushLeft (i); checkInvariants ("left3", d2); }
    for (int i = 40; i < 43; i++) { d2.pushRight (i); checkInvariants ("right4", d2); }
    check ("concat9", d2, "[ 32 31 30 40 41 42 ]");

    d3 = new MyDeque ();
    d2.concat (d3);
    check ("concat10", d2, "[ 32 31 30 40 41 42 ]");
    check ("concat11", d3, "[ ]");

    d1.concat (d2);
    check ("concat12", d1, "[ 12 11 10 20 21 22 32 31 30 40 41 42 ]");
    check ("concat13", d2, "[ ]");
    for (int i = 0; i < 12; i++) { d1.popLeft (); checkInvariants ("left5", d1); }
    ////////////////////////////////////////////////////////////////////
    // delete tests
    ////////////////////////////////////////////////////////////////////
    d1 = new MyDeque ();
    d1.pushLeft (11);
    k = d1.delete (0);
    check ("delete1", d1, "[ ]", k, 11);
    for (int i = 10; i < 20; i++) { d1.pushRight (i); checkInvariants ("right6", d1); }
    k = d1.delete (0);
    check ("delete2", d1, "[ 11 12 13 14 15 16 17 18 19 ]", k, 10);
    k = d1.delete (8);
    check ("delete3", d1, "[ 11 12 13 14 15 16 17 18 ]", k, 19);
    k = d1.delete (4);
    check ("delete4", d1, "[ 11 12 13 14 16 17 18 ]", k, 15);
    k = d1.delete (3);
    check ("delete5", d1, "[ 11 12 13 16 17 18 ]", k, 14);
    k = d1.delete (0);
    check ("delete6", d1, "[ 12 13 16 17 18 ]", k, 11);
    k = d1.delete (4);
    check ("delete7", d1, "[ 12 13 16 17 ]", k, 18);
    k = d1.delete (3);
    check ("delete8", d1, "[ 12 13 16 ]", k, 17);
    k = d1.delete (1);
    check ("delete9", d1, "[ 12 16 ]", k, 13);
    k = d1.delete (1);
    check ("delete10", d1, "[ 12 ]", k, 16);
    k = d1.delete (0);
    check ("delete10", d1, "[ ]", k, 12);
    
    ////////////////////////////////////////////////////////////////////
    // More push/pop
    ////////////////////////////////////////////////////////////////////
    d1 = new MyDeque();
    d1.pushRight(21);
    check("left/right20", d1, "[ 21 ]");
    d1.pushLeft(11);
    check("left/right21", d1, "[ 11 21 ]");
    k = d1.popLeft();
    check("left/right22", d1, "[ 21 ]", k, 11);
    d1.pushRight(22);
    check("left/right23", d1, "[ 21 22 ]");

    d1 = new MyDeque();
    d1.pushRight(21);
    check("left/right30", d1, "[ 21 ]");
    d1.pushRight(22);
    check("left/right31", d1, "[ 21 22 ]");
    d1.pushLeft(11);
    check("left/right32", d1, "[ 11 21 22 ]");
    k = d1.popLeft();
    check("left/right33", d1, "[ 21 22 ]", k, 11);
    k = d1.popLeft();
    check("left/right34", d1, "[ 22 ]", k, 21);
    d1.pushLeft(12);
    check("left/right35", d1, "[ 12 22 ]");
    StdOut.println ("Finished tests");
  }
  
  public MyDeque (String s) {
    String[] nums = s.split (" ");
    for (int i = nums.length-1; i >= 0; i--) {
      try { 
        pushLeft (Double.parseDouble (nums[i]));      
      } catch (NumberFormatException e) { }
    }
  }
  public String toString () { 
    DecimalFormat format = new DecimalFormat ("#.###");
    StringBuilder result = new StringBuilder ("[ ");
    for (Node x = first; x != null; x = x.next) {
      result.append (format.format (x.item));
      result.append (" ");
    }
    result.append ("]");
    return result.toString ();
  }


  private static void checkInvariants (String message, MyDeque that) {
    int N = that.N;
    MyDeque.Node first = that.first;
    MyDeque.Node last = that.last;

    if (N < 0) throw new Error ();
    if (N == 0) {
      if (first != null) {
        showError (String.format ("%s: N==0, Expected first == null.", message));
      }
      if (last != null) {
        showError (String.format ("%s: N==0, Expected last == null.", message));
      }
    } else {
      if (first == null) {
        showError (String.format ("%s: N!=0, Expected first != null.", message));
      }
      if (last == null) {
        showError (String.format ("%s: N!=0, Expected last != null.", message));
      }
    }
    if (N > 0) {
      MyDeque.Node prev = null;
      MyDeque.Node current = first;
      for (int i = 0; i < N; i++) {
        if (current == null) {
          showError (String.format ("%s: N==%d, Expected %d next nodes, but got less.", message, N, N));
          return;
        }
        if (current.prev != prev) { 
          showError (String.format ("%s: i=%d, Broken prev link.", message, i));
          return;
        }
        prev = current;
        current = current.next;
      }
      if (current != null) {
        showError (String.format ("%s: N==%d, Expected %d next nodes, but got more.", message, N, N));
        return;
      }
      MyDeque.Node next = null;
      current = last;
      for (int i = 0; i < N; i++) {
        if (current == null) {
          showError (String.format ("%s: N==%d, Expected %d prev nodes, but got less.", message, N, N));
          return;
        }
        if (current.next != next) {
          showError (String.format ("%s: i=%d, Broken next link.", message, i));
          return;
        }
        next = current;
        current = current.prev;
      }
      if (current != null) {
        showError (String.format ("%s: N==%d, Expected %d prev nodes, but got more.", message, N, N));
        return;
      }
    }
  }
  private static void check (String message, MyDeque actual, String expected) {
    checkInvariants (message, actual);
    if (expected != null) {
      if (!expected.equals (actual.toString ())) {
        showError ("Expected \"" + expected + "\", got \"" + actual + "\"");
        return;
      }
    }
  }
  private static void check (String message, MyDeque actual, String expected, double dActual, double dExpected) {
    if (dExpected != dActual) {
      showError ("Expected \"" + dExpected + "\", got \"" + dActual + "\"");
      return;
    }
    check (message, actual, expected);
  }

  private static void showError (String message) {
    Trace.draw ();
    StdOut.println (message);
    throw new Error (); // stops execution
  }
}

file:MyDequeUsingStacks.java [source]

// Exercise 1.4.31
package algs14;
import stdlib.*;
import java.util.NoSuchElementException;
import algs13.ResizingArrayStack;

/*
Here is the kind of output I get before fixing the move method.

    4000     0.4   3.1
    8000     1.5   4.1
   16000     4.9   3.2
   32000    21.6   4.4

Here is the kind of output I get after fixing the move method.
You can see that it is much faster, but not very consistent.
This is due to garbage collection and other system effects.

    4000     0.0   0.7
    8000     0.0   1.2
   16000     0.0   2.2
   32000     0.0   0.2
   64000     0.0   1.5
  128000     0.0   5.7
  256000     0.1   5.3
  512000     0.2   2.1
 1024000     0.4   1.9
 2048000     0.7   2.0
 4096000     2.5   3.6

    4000     0.0   0.8
    8000     0.0   1.6
   16000     0.0   1.8
   32000     0.0   0.1
   64000     0.0   2.0
  128000     0.0   4.5
  256000     0.1   5.7
  512000     0.2   1.8
 1024000     0.3   1.8
 2048000     0.7   2.1
 4096000     3.7   5.1


    4000     0.0   0.7
    8000     0.0   2.0
   16000     0.0   1.9
   32000     0.0   0.2
   64000     0.0   1.7
  128000     0.0   4.4
  256000     0.0   1.6
  512000     0.1   2.3
 1024000     0.1   0.6
 2048000     0.1   2.0
 4096000     0.2   2.4
 */

public class MyDequeUsingStacks<T> {
  ResizingArrayStack<T> sl  = new ResizingArrayStack<>();
  ResizingArrayStack<T> sr  = new ResizingArrayStack<>();
  public boolean isEmpty ()      { return sl.isEmpty() && sr.isEmpty(); }
  public int size ()             { return sl.size() + sr.size(); }
  public void pushLeft (T item)  { sl.push (item); }
  public void pushRight (T item) { sr.push (item); }

  private void move (ResizingArrayStack<T> from, ResizingArrayStack<T> to) {
    if (!to.isEmpty ()) throw new IllegalArgumentException();
    if (from.isEmpty ()) throw new IllegalArgumentException();
    ResizingArrayStack<T> tmp = new ResizingArrayStack<>();
    while (!from.isEmpty ()) {
      to.push(from.pop()); 
    }
    // TODO: 
    // Run the main method below.  
    // Note that the execution is correct (that's the first part of the test).
    // Note also that performance is terrible (that's the second part of the test).
    // In particular, for N pops, the running time increases proportionally to N^2.
    // So the amortized time for each pop is linear (proportional to N).
    // 
    // Your goal is to change this method so that overall performance of 
    // the main method improves, by altering the number of elements moved 
    // from "from" to "to".
    //
    // Your solution must continue to pass the correctness tests below.
    // It must also have amortized constant time per pop.
    // So for N pops, the running time should increase proportionally to N.
    //
    // You can use one temporary stack to help you:
    //   ResizingArrayStack<T> tmp = new ResizingArrayStack<>();
    // You may find it helpful to print the sizes while debugging:
    //   StdOut.println ("from: " + from.size () + " to: " + to.size ());
    // You can print out the content of the stacks by uncommenting the 
    // lines in popLeft and popRight, below.
  }

  public T popLeft () {
    if (isEmpty()) { throw new NoSuchElementException(); }
    if (sl.isEmpty ()) { 
      //StdOut.println("r2l before: " + sl + ": " + sr);
      move (sr, sl); 
      //StdOut.println("r2l after:  " + sl + ": " + sr);
    }
    return sl.pop ();
  }

  public T popRight () {
    if (isEmpty()) { throw new NoSuchElementException(); }
    if (sr.isEmpty ()) { 
      //StdOut.println("l2r before: " + sl + ": " + sr);
      move (sl, sr); 
      //StdOut.println("l2r after:  " + sl + ": " + sr);
    }
    return sr.pop ();
  }

  public String toString () {
    if (isEmpty ()) return "[ ]";

    ResizingArrayStack<T> srBackwards = new ResizingArrayStack<>();
    for (T item : sr)
      srBackwards.push (item);

    StringBuilder sb = new StringBuilder ("[ ");
    for (T item : sl) {
      sb.append (item);
      sb.append (" ");
    }
    for (T item : srBackwards) {
      sb.append (item);
      sb.append (" ");
    }

    sb.append ("]");
    return sb.toString ();
  }
  private void check (String expected) {
    if (expected != null) {
      if (!expected.equals (this.toString ())) throw new Error ("Expected \"" + expected + "\", got \"" + this + "\"");
    }
    //StdOut.println (this);
  }
  private void check (T iExpected, T iActual, String expected) {
    if (!iExpected.equals (iActual)) throw new Error ("Expected \"" + iExpected + "\", got \"" + iActual + "\"");
    check (expected);
  }
  private void check (T iExpected, T iActual) {
    if (!iExpected.equals (iActual)) throw new Error ("Expected \"" + iExpected + "\", got \"" + iActual + "\"");
  }
  private static void correctnessTest () {
    MyDequeUsingStacks<Integer> d1 = new MyDequeUsingStacks<> ();
    d1.pushLeft(0);
    d1.pushLeft(1);
    d1.pushLeft(2);
    d1.pushLeft(3);
    d1.check(0,d1.popRight());
    d1.check(3,d1.popLeft());
    d1.check(1,d1.popRight());
    d1.check(2,d1.popLeft());
    d1.pushRight(0);
    d1.pushRight(1);
    d1.pushRight(2);
    d1.pushRight(3);
    d1.check(0,d1.popLeft());
    d1.check(3,d1.popRight());
    d1.check(1,d1.popLeft());
    d1.check(2,d1.popRight());

    Integer k;

    if (!d1.isEmpty ()) throw new Error();
    d1.pushLeft (11);
    d1.check ("[ 11 ]");
    d1.pushLeft (12);
    d1.check ("[ 12 11 ]");
    k = d1.popLeft ();
    d1.check (12, k, "[ 11 ]");
    k = d1.popLeft ();
    d1.check (11, k, "[ ]");

    try {
      d1.popLeft ();
      throw new Error ("Expected exception");
    } catch (NoSuchElementException e) {}

    if (!d1.isEmpty ()) throw new Error();
    for (int i = 0; i < 20; i++) { d1.pushLeft (i); }
    for (int i = 0; i < 20; i++) { d1.check (19-i, d1.popLeft ()); }

    if (!d1.isEmpty ()) throw new Error();
    for (int i = 0; i < 20; i++) { d1.pushLeft (i); }
    for (int i = 0; i < 20; i++) { d1.check (i, d1.popRight ()); }

    if (!d1.isEmpty ()) throw new Error();
    for (int i = 0; i < 20; i++) { d1.pushLeft (i); }
    for (int i = 0; i < 10; i++) { d1.check (i, d1.popRight ()); }
    for (int i = 0; i < 10; i++) { d1.check (19-i, d1.popLeft ()); }

    if (!d1.isEmpty ()) throw new Error();
    for (int i = 0; i < 20; i++) { d1.pushLeft (i); }
    for (int i = 0; i < 10; i++) { d1.check (19-i, d1.popLeft ()); }
    for (int i = 0; i < 10; i++) { d1.check (i, d1.popRight ()); }

    if (!d1.isEmpty ()) throw new Error();
    d1.pushRight (11);
    d1.check ("[ 11 ]");
    d1.pushRight (12);
    d1.check ("[ 11 12 ]");
    k = d1.popRight ();
    d1.check (12, k, "[ 11 ]");
    k = d1.popRight ();
    d1.check (11, k, "[ ]");

    if (!d1.isEmpty ()) throw new Error();
    for (int i = 0; i < 20; i++) { d1.pushRight (i); }
    for (int i = 0; i < 20; i++) { d1.check (19-i, d1.popRight ()); }

    if (!d1.isEmpty ()) throw new Error();
    for (int i = 0; i < 20; i++) { d1.pushRight (i); }
    for (int i = 0; i < 20; i++) { d1.check (i, d1.popLeft ()); }

    if (!d1.isEmpty ()) throw new Error();
    for (int i = 0; i < 20; i++) { d1.pushRight (i); }
    for (int i = 0; i < 10; i++) { d1.check (i, d1.popLeft ()); }
    for (int i = 0; i < 10; i++) { d1.check (19-i, d1.popRight ()); }

    if (!d1.isEmpty ()) throw new Error();
    for (int i = 0; i < 20; i++) { d1.pushRight (i); }
    for (int i = 0; i < 10; i++) { d1.check (19-i, d1.popRight ()); }
    for (int i = 0; i < 10; i++) { d1.check (i, d1.popLeft ()); }

    try {
      d1.popRight ();
      throw new Error ("Expected exception");
    } catch (NoSuchElementException e) {}
    
    StdOut.println("Finished correctness test.");
  }

  private static void performanceTest() {
    int MIN = 2000;
    int MAX = 4096000;    
    double prev = timeTrial(MIN);
    for (int N = MIN*2; N<=MAX; N += N) {
      double time = timeTrial(N);
      StdOut.format("%8d %9.3f %5.1f\n", N, time, time/prev);
      prev = time;
    }
  }
  private static double timeTrial(int N) {
    int NUM_TRIALS = 1;
    MyDequeUsingStacks<Integer> d1 = new MyDequeUsingStacks<> ();
    Stopwatch sw = new Stopwatch ();
    for (int trial=0; trial < NUM_TRIALS; trial++) {
      for (int i=0; i<2*N; i++) {
        d1.pushLeft (i);
      }
      for (int i=0; i<N; i++) {
        d1.popRight();
        d1.popLeft();
      }
    }
    return sw.elapsedTime ();
  }


  public static void main (String args[]) {
    //Trace.drawStepsOfMethod ("correctnessTest");
    //Trace.drawStepsOfMethod ("move");
    //Trace.run ();
    correctnessTest ();
    performanceTest ();
  }
}