CSC300: Homework (MyDequeUsingStacks, UF Problems)

Contents [0/4]

Video [1/4]
Homework (MyDequeUsingStacks, UF Problems) [2/4]
HW Answers [3/4]
Quiz Answers [4/4]

(Click here for one slide per page)


Video [1/4]

Open Playlist

Homework (MyDequeUsingStacks, UF Problems) [2/4]

file:MyDequeUsingStacks.java [source] [doc-public] [doc-private]
001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
// 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 ();
  }
}

HW Answers [3/4]

You can check your answer in TestUF.java.
Uncomment the correct line in getUF to return the correct type of UF.
Put the following in main:

  show(10, "9 0, 3 4, 5 8, 7 2, 2 1, 5 7, 0 3, 4 2");

After running you should see pictures in Desktop/GraphvizOutput
For this problem I get:
  
       10[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 9  0:  9[0, 1, 2, 3, 4, 5, 6, 7, 8, 0]
 3  4:  8[0, 1, 2, 4, 4, 5, 6, 7, 8, 0]
 5  8:  7[0, 1, 2, 4, 4, 8, 6, 7, 8, 0]
 7  2:  6[0, 1, 2, 4, 4, 8, 6, 2, 8, 0]
 2  1:  5[0, 1, 1, 4, 4, 8, 6, 1, 8, 0]
 5  7:  4[0, 1, 1, 4, 4, 1, 6, 1, 1, 0]
 0  3:  3[4, 1, 1, 4, 4, 1, 6, 1, 1, 4]
 4  2:  2[1, 1, 1, 1, 1, 1, 6, 1, 1, 1]  
       10[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 9  0:  9[0, 1, 2, 3, 4, 5, 6, 7, 8, 0]
 3  4:  8[0, 1, 2, 4, 4, 5, 6, 7, 8, 0]
 5  8:  7[0, 1, 2, 4, 4, 8, 6, 7, 8, 0]
 7  2:  6[0, 1, 2, 4, 4, 8, 6, 2, 8, 0]
 2  1:  5[0, 1, 1, 4, 4, 8, 6, 2, 8, 0]
 5  7:  4[0, 1, 1, 4, 4, 8, 6, 2, 1, 0]
 0  3:  3[4, 1, 1, 4, 4, 8, 6, 2, 1, 0]
 4  2:  2[4, 1, 1, 4, 1, 8, 6, 2, 1, 0]
       10[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 9  0:  9[9, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 3  4:  8[9, 1, 2, 3, 3, 5, 6, 7, 8, 9]
 5  8:  7[9, 1, 2, 3, 3, 5, 6, 7, 5, 9]
 7  2:  6[9, 1, 7, 3, 3, 5, 6, 7, 5, 9]
 2  1:  5[9, 7, 7, 3, 3, 5, 6, 7, 5, 9]
 5  7:  4[9, 7, 7, 3, 3, 7, 6, 7, 5, 9]
 0  3:  3[9, 7, 7, 9, 3, 7, 6, 7, 5, 9]
 4  2:  2[9, 7, 7, 9, 3, 7, 6, 7, 5, 7]
Here's an example:

  show(3, "1 0, 0 2");

Correct answer:  

        3[0, 1, 2]
 1  0:  2[0, 0, 2]
 0  2:  1[2, 2, 2]

With the broken code above: 

        3[0, 1, 2]
 1  0:  2[0, 0, 2]
 0  2:  1[2, 0, 2]

The problem is that id[p] is changes!
To correct this, it is sufficient to use:
   
   int pid = id[p];
   for (int i = 0; i < id.length; i++)
       if (id[i] == pid) id[i] = id[q];

The book also uses a variable for qid.
But this change does not affect correctness, since id[q] does not change.
Yes, the algorithm would be correct.  However, it would be increase the tree
height, so the performance guarantee would be invalid.  As an example,

Suppose we have three elements that we union together.
Then weighted union should not produce a tree of depth 2.
Here is the correct alorgithm:

        3[0, 1, 2]
 0  1:  2[0, 0, 2]
 1  2:  1[0, 0, 0]

The final forest looks like this:

    0
   / \
  1   2

It is depth 1.  
Here is the badly performing version:

        3[0, 1, 2]
 0  1:  2[0, 0, 2]
 1  2:  1[0, 0, 1]

 The final forest looks like this:

    0
     \
      1
       \
        2

It has depth 2.

Here is the code for the badly performing version:
01
02
03
04
05
06
07
08
09
10
11
12
13
14
  public void union(int p, int q) {
    int pid = find(p);
    int qid = find(q);
    if (pid == qid) return;

    if   (sz[pid] < sz[qid]) {
      id[pid] = q;        // should be qid, not q.
      sz[qid] += sz[pid];
    } else {
      id[qid] = p;        // should be pid, not p.
      sz[pid] += sz[qid];
    }
    count--;
  }

Quiz Answers [4/4]

You can check your answer in TestUF.java.
Uncomment the correct line in getUF to return the correct type of UF.
Put the following in main:

  show(10, "9 0, 3 4, 5 8, 7 2, 2 1, 5 7, 0 3, 4 2");

Using QuickFindUF:  

       10[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 9  0:  9[0, 1, 2, 3, 4, 5, 6, 7, 8, 0]
 3  4:  8[0, 1, 2, 4, 4, 5, 6, 7, 8, 0]
 5  8:  7[0, 1, 2, 4, 4, 8, 6, 7, 8, 0]
 7  2:  6[0, 1, 2, 4, 4, 8, 6, 2, 8, 0]
 2  1:  5[0, 1, 1, 4, 4, 8, 6, 1, 8, 0]
 5  7:  4[0, 1, 1, 4, 4, 1, 6, 1, 1, 0]
 0  3:  3[4, 1, 1, 4, 4, 1, 6, 1, 1, 4]
 4  2:  2[1, 1, 1, 1, 1, 1, 6, 1, 1, 1]

Using QuickUnionUF:  
 
       10[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 9  0:  9[0, 1, 2, 3, 4, 5, 6, 7, 8, 0]
 3  4:  8[0, 1, 2, 4, 4, 5, 6, 7, 8, 0]
 5  8:  7[0, 1, 2, 4, 4, 8, 6, 7, 8, 0]
 7  2:  6[0, 1, 2, 4, 4, 8, 6, 2, 8, 0]
 2  1:  5[0, 1, 1, 4, 4, 8, 6, 2, 8, 0]
 5  7:  4[0, 1, 1, 4, 4, 8, 6, 2, 1, 0]
 0  3:  3[4, 1, 1, 4, 4, 8, 6, 2, 1, 0]
 4  2:  2[4, 1, 1, 4, 1, 8, 6, 2, 1, 0]

Using WeightedUF:

       10[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 9  0:  9[9, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 3  4:  8[9, 1, 2, 3, 3, 5, 6, 7, 8, 9]
 5  8:  7[9, 1, 2, 3, 3, 5, 6, 7, 5, 9]
 7  2:  6[9, 1, 7, 3, 3, 5, 6, 7, 5, 9]
 2  1:  5[9, 7, 7, 3, 3, 5, 6, 7, 5, 9]
 5  7:  4[9, 7, 7, 3, 3, 7, 6, 7, 5, 9]
 0  3:  3[9, 7, 7, 9, 3, 7, 6, 7, 5, 9]
 4  2:  2[9, 7, 7, 9, 3, 7, 6, 7, 5, 7]

Revised: 2024-03-12 10:14