CSC300: Homework (Percolation, Sorting Problems)

Contents [0/4]

Video [1/4]
Homework (Percolation) [2/4]
HW Answers [3/4]
Quiz Answers [4/4]

(Click here for one slide per page)


Video [1/4]

Open Playlist

In this video I will use some notes from the textbook:

Homework (Percolation) [2/4]

file:Percolation.java [source] [doc-public] [doc-private]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
package algs15.perc;

//import stdlib.*;
//import algs15.*;

// Uncomment the import statements above.

// You can test this using InteractivePercolationVisualizer and PercolationVisualizer
// All methods should make at most a constant number of calls to a UF data structure.
// You can use more than one UF data structure.
// You can assume that N>1
//
// Note that you can print out a UF structure using its toString method.
// You can also use the toGraphviz method to draw the UF.
// These may be useful for debugging.
// Try calling them whenever you open a new square.
public class Percolation {
  int N;
  boolean[] open;
  // TODO: more fields to add here
  public Percolation(int N) {
    if (N < 2) throw new IllegalArgumentException();
    this.N = N;
    this.open = new boolean[N*N];
    // TODO: more to do here
  }
  // open site (row i, column j) if it is not already
  public void open(int i, int j) {
    int x = i*N+j;
    if (!open[x]) {
      open[x] = true;
      // TODO: more to do here.
    }
  }
  // is site (row i, column j) open?
  public boolean isOpen(int i, int j) {
    return open[i*N+j];
  }
  // is site (row i, column j) full?
  public boolean isFull(int i, int j) {
    // TODO
    return false;
  }
  // does the system percolate?
  public boolean percolates() {
    // TODO
    return false;
  }
}

HW Answers [3/4] 

 2.1.1
  Show, in the style of the example trace with Algorithm 2.1,
  how selection sort sorts the array
  E A S Y Q U E S T I O N
  ^ * 
  A E S Y Q U E S T I O N
    ^
  A E S Y Q U E S T I O N
      ^       *   
  A E E Y Q U S S T I O N
        ^           *
  A E E I Q U S S T Y O N
          ^             *
  A E E I N U S S T Y O Q
            ^         *
  A E E I N O S S T Y U Q
              ^         *
  A E E I N O Q S T Y U S
                ^      
  A E E I N O Q S T Y U S
                  ^     *
  A E E I N O Q S S Y U T
                    ^   *
  A E E I N O Q S S T U Y
                      ^
  A E E I N O Q S S T U Y
                        ^
  A E E I N O Q S S T U Y
                          ^

2.1.2*
  What is the maximum number of exchanges involving any particular item
  during selection sort? What is the average number of exchanges
  involving an item?

  
  max # of exchanges for selection sort for a particular element: N
  An example:
  501234
  051234
  015234
  012534
  012354
  012345

  total # of exchanges <= N
  total # of elements = N
  average <= 1

2.1.1
  Show, in the style of the example trace with Algorithm 2.1,
  how insertion sort sorts the array
  E A S Y Q U E S T I O N
  ^
  E A S Y Q U E S T I O N
  * ^
  A E S Y Q U E S T I O N
      ^
  A E S Y Q U E S T I O N
        ^
  A E S Y Q U E S T I O N
        * ^
  A E S Q Y U E S T I O N
      *   ^
  A E Q S Y U E S T I O N
          * ^
  A E Q S U Y E S T I O N
            * ^
  A E Q S U E Y S T I O N
          *   ^
  A E Q S E U Y S T I O N
        *     ^
  A E Q E S U Y S T I O N
      *       ^
  A E E Q S U Y S T I O N
              * ^
  A E E Q S U S Y T I O N
            *   ^
  A E E Q S S U Y T I O N
                * ^
  A E E Q S S U T Y I O N
              *   ^
  A E E Q S S T U Y I O N
                  * ^
  A E E Q S S T U I Y O N
                *   ^
  A E E Q S S T I U Y O N
              *     ^
  A E E Q S S I T U Y O N
            *       ^
  A E E Q S I S T U Y O N
          *         ^
  A E E Q I S S T U Y O N
        *           ^
  A E E I Q S S T U Y O N
                    * ^
  A E E I Q S S T U O Y N
                  *   ^
  A E E I Q S S T O U Y N
                *     ^
  A E E I Q S S O T U Y N
              *       ^
  A E E I Q S O S T U Y N
            *         ^
  A E E I Q O S S T U Y N
          *           ^
  A E E I O Q S S T U Y N
                      * ^
  A E E I O Q S S T U N Y
                    *   ^
  A E E I O Q S S T N U Y
                  *     ^
  A E E I O Q S S N T U Y
                *       ^
  A E E I O Q S N S T U Y
              *         ^
  A E E I O Q N S S T U Y
            *           ^
  A E E I O N Q S S T U Y
          *             ^
  A E E I N O Q S S T U Y
                          ^          
2.1.6*
  Which method runs faster for an array with all keys identical,
  selection sort or insertion sort?

  faster with identical keys:
  insertion=N compares and 0 swaps
  selection=N^2/2 compares and 0 swaps

  Three important facts for this problem:
  1. if all keys are identical then it's sorted
  2. for a sorted array, insert sort is linear (it just checks every
  element to the adjacent one)
  3. for any array, selection sort does a quadratic number of comparisons.

  Since the comparison pattern of selection sort is fixed, it still has
  worst case performance.



2.1.7*
  Which method runs faster for an array in reverse order,
  selection sort or insertion sort?

  faster for reversed array:
  insertion=N^2/2 compares and N^2/2 swaps
  selection=N^2/2 compares and N swaps

  Experimentally
  insertion with reversed array:
    4000   15999998   4.0 [0.049 0.721]
    8000   63999998   4.0 [0.173 3.531]
   16000  255999998   4.0 [0.761 4.399]
   32000 1023999998   4.0 [2.911 3.825]
   64000 4095999998   4.0 [12.374 4.251]
    
  selection with reversed array:
    4000    8005999   4.0 [0.026 0.226]
    8000   32011999   4.0 [0.115 4.423]
   16000  128023999   4.0 [0.489 4.252]
   32000  512047999   4.0 [1.964 4.016]
   64000 2048095999   4.0 [8.282 4.217]  

2.1.8*
  Suppose that we use insertion sort on a randomly ordered array where items 
  have only one of three values. Is the running time linear, quadratic, or 
  something in between? 

  should be quadratic.  Number of values does not matter, it's their distribution.

  three values:
    4000    5203612   3.8 [0.016 0.364]
    8000   21434206   4.1 [0.053 3.313]
   16000   84502719   3.9 [0.210 3.962]
   32000  342564934   4.1 [0.886 4.219]
   64000 1360115026   4.0 [3.488 3.937]
  128000 5419985602   4.0 [12.636 3.623]
  
  two values:
    4000    4039762   4.1 [0.012 0.279]
    8000   16011924   4.0 [0.041 3.417]
   16000   64837772   4.0 [0.155 3.780]
   32000  254433286   3.9 [0.599 3.865]
   64000 1022514350   4.0 [2.537 4.235]
  128000 4097713293   4.0 [9.868 3.890]

  one value (therefore presorted):
    4000       7998   2.0 [0.002 Infinity]
    8000      15998   2.0 [0.001 0.500]
   16000      31998   2.0 [0.001 1.000]
   32000      63998   2.0 [0.000 0.000]
   64000     127998   2.0 [0.001 Infinity]
  128000     255998   2.0 [0.000 0.000]  
    
  To get test, initialize as
        Integer[] a = new Integer[N];
        for (int i = 0; i < a.length; i++)
            a[i] = (i*2)/N;
        StdRandom.shuffle (a);  

2.1.15*
  Expensive exchange. A clerk at a shipping company is charged with the task
  of rearranging a number of large crates in order of the time they are to be
  shipped out. Thus, the cost of compares is very low (just look at the labels)
  relative to the cost of ex- changes (move the crates). The warehouse is
  nearly full --- there is extra space sufficient to hold any one of the crates,
  but not two. What sorting method should the clerk use?

  selection sort # exchanges <= N.    

2.1.24
  Insertion sort with sentinel. Develop an implementation of insertion sort
  that eliminates the j>0 test in the inner loop by first putting the
  smallest item into position. Use SortCompare to evaluate the effectiveness
  of doing so. Note : It is often possible to avoid an index-out-of-bounds
  test in this way-the element that enables the test to be eliminated is
  known as a sentinel. 

  See XInsertionX.java

2.1.25 
  Insertion sort without exchanges. Develop an implementation of insertion
  sort that moves larger elements to the right one position with one array
  access per entry, rather than using exchange(). Use SortCompare to evaluate
  the effectiveness of doing so. 

  See XInsertionX.java

Quiz Answers [4/4] 

Selection sort
        
4 1 9 5 6 0 3 8 7 2
^         *
0 1 9 5 6 4 3 8 7 2
  ^                    
0 1 9 5 6 4 3 8 7 2
    ^             *
0 1 2 5 6 4 3 8 7 9  
      ^     *
0 1 2 3 6 4 5 8 7 9  
        ^ *
0 1 2 3 4 6 5 8 7 9  
          ^...

          
1 2 3 4 5 6 7 8 9 0
^                 *
0 2 3 4 5 6 7 8 9 1
  ^               *
0 1 3 4 5 6 7 8 9 2
    ^             *
0 1 2 4 5 6 7 8 9 3
      ^           *
0 1 2 3 5 6 7 8 9 4
        ^...

        
Insertion sort
        
4 1 9 5 6 0 3 8 7 2
^
4 1 9 5 6 0 3 8 7 2
* ^
1 4 9 5 6 0 3 8 7 2
    ^
1 4 9 5 6 0 3 8 7 2  
    * ^
1 4 5 9 6 0 3 8 7 2 
      * ^
1 4 5 6 9 0 3 8 7 2  
        * ^
1 4 5 6 0 9 3 8 7 2  
      *   ^
1 4 5 0 6 9 3 8 7 2  
    *     ^
1 4 0 5 6 9 3 8 7 2  
  *       ^
1 0 4 5 6 9 3 8 7 2  
*         ^
0 1 4 5 6 9 3 8 7 2  
          ^...

          
1 2 3 4 5 6 7 8 9 0
^
1 2 3 4 5 6 7 8 9 0
  ^
1 2 3 4 5 6 7 8 9 0
    ^
1 2 3 4 5 6 7 8 9 0
      ^
1 2 3 4 5 6 7 8 9 0
        ^
1 2 3 4 5 6 7 8 9 0
          ^
1 2 3 4 5 6 7 8 9 0
            ^
1 2 3 4 5 6 7 8 9 0
              ^
1 2 3 4 5 6 7 8 9 0
                ^
1 2 3 4 5 6 7 8 9 0
                * ^
1 2 3 4 5 6 7 8 0 9
              *   ^
1 2 3 4 5 6 7 0 8 9
            *     ^
1 2 3 4 5 6 0 7 8 9
          *       ^
1 2 3 4 5 0 6 7 8 9
        *         ^
...

Revised: 2024-03-12 10:14