coursera UNIT 1

ELEMENTARY SORT‣ rules of the game

Sample sort client 1

Goal. Sort any type of data.

Ex 1. Sort random real numbers in ascending order.

seems artificial, but stay tuned for an application

1
2
3
4
5
6
7
8
9
10
11
12
13

public class Experiment
{
    public static void main(String[] args)
    {
        int N = Integer.parseInt(args[0]); 
        Double[] a = new Double[N];
        for (int i = 0; i < N; i++)
            a[i] = StdRandom.uniform();
        Insertion.sort(a);
        for (int i = 0; i < N; i++)
            StdOut.println(a[i]):
    }
}

Sample sort client 2

Ex 2. Sort strings from file in alphabetical order.

1
2
3
4
5
6
7
8
9
10

public class StringSorter
{
    public static void main(String[] args)
    {
        String[] a = In.readStrings(args[0]); 
        Insertion.sort(a);
        for (int i = 0; i < a.length; i++)
            StdOut.println(a[i]);
    } 
}

Sample sort client 3

Ex 3. Sort the files in a given directory by filename.

1
2
3
4
5
6
7
8
9
10
11
12

import java.io.File;

public class FileSorter {
    public static void main(String[] args)
    {
        File directory = new File(args[0]);
        File[] files = directory.listFiles();
        Insertion.sort(files);
        for (int i = 0; i < files.length; i++)
            StdOut.println(files[i].getName());
    } 
}

Callbacks

Q. How can sort() know how to compare data of type Double, String, and java.io.File without any information about the type of an item’s key?

Callback = reference to executable code.

• Client passes array of objects to sort() function.
• The sort() function calls back object’s compareTo() method as needed.

Implementing callbacks.

• Java: interfaces.
• C: function pointers.
• C++: class-type functors.
• C#: delegates.
• Python, Perl, ML, Javascript: first-class functions.

Callbacks: roadmaps


Total order

A total order is a binary relation $≤$ that satisfies:

• Antisymmetry: if $v≤w$ and $w≤v$, then $v=w$.
• Transitivity: if $v≤w$ and $w≤x$, then $v≤x$.
• Totality: either $v≤w$ or $w≤v$ or both.

Ex.

• Standard order for natural and real numbers.
• Chronological order for dates or times.
• Alphabetical order for strings.
• …

Surprising but true.

The $<=$ operator for double is not a total order. (!)

violates totality: (Double.NaN <= Double.NaN) is false

Comparable API

Implement compareTo() so that v.compareTo(w)

• Is a total order.
• Returns a negative integer, zero, or positive integer
• if $v$ is less than, equal to, or greater than $w$, respectively. Throws an exception if incompatible types (or either is null).

Built-in comparable types.

Integer, Double, String, Date, File, …

User-defined comparable types.

Implement the Comparable interface.

Implementing the Comparable interface

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public class Date implements Comparable<Date>
{
    private final int month, day, year;
    public Date(int m, int d, int y)
    {
        month = m;
        day   = d;
        year  = y;
    }
    public int compareTo(Date that)
    {
        if (this.year < that.year ) return -1;
        if (this.year > that.year ) return +1;
        if (this.month < that.month) return -1;
        if (this.month > that.month) return +1;
        if (this.day < that.day )   return -1;
        if (this.day > that.day )   return +1;
        return 0;
}

Two useful sorting abstractions

‣ selection sort

‣ insertion sort

‣ shellsort

‣ shuffling

‣ convex hull

Stacks and queues

Fundamental data types.

• Value: collection of objects.
• Operations: insert, remove, iterate, test if empty.
• Intent is clear when we insert.
• Which item do we remove?

Client, implementation, interface

Benefits.

• Client can’t know details of implementation ⇒

  client has many implementation from which to choose.

• Implementation can’t know details of client needs ⇒

  many clients can re-use the same implementation.

• Design: creates modular, reusable libraries.

• Performance: use optimized implementation where it matters.

‣ stacks

Warmup API. Stack of strings data type.

Warmup client. Reverse sequence of strings from standard input

1
2
3
4
5
6
7
8
9

public static void main(String[] args)
{
    StackOfStrings stack = new StackOfStrings();
    while (!StdIn.isEmpty()) {
        String s = StdIn.readString();
        if (s.equals("-"))  StdOut.print(stack.pop()); 
        else                stack.push(s);
    }
}

Stack: linked-list representation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public class LinkedStackOfStrings
{
    private Node first = null;
    private class Node {
        // private inner class (access modifiers don't matter)
        String item;
        Node next; 
    }
    public boolean isEmpty()
    {  return first == null;  }

    public void push(String item)
    {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
    }

    public String pop()
    {
        String item = first.item;
        first = first.next;
        return item;
    }
}

Stack: linked-list implementation performance

Proposition. Every operation takes constant time in the worst case.

Proposition. A stack with N items uses $\sim40N$ bytes.

Remark. This accounts for the memory for the stack (but not the memory for strings themselves, which the client owns).

Stack: array implementation

Array implementation of a stack.

• Use array s[] to store N items on stack.
• push(): add new item at s[N].
• pop(): remove item from s[N-1].

Defect.

Stack overflows when N exceeds capacity. [stay tuned]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public class FixedCapacityStackOfStrings
{
    private String[] s;
    private int N = 0;
    
    public FixedCapacityStackOfStrings(int capacity // a cheat (stay tuned))
    {  s = new String[capacity];  }

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

    public void push(String item)
    {  s[N++] = item; // use to index into array; then increment N }

    public String pop()
    { return s[--N]; // decrement N; then use to index into array } 
}

Stack considerations

Overflow and underflow.

Null items: We allow null items to be inserted.

Loitering: Holding a reference to an object when it is no longer needed.

1
2
3
4
5
6

public String pop() { return s[--N]; }	// Loitering.

// this version avoids "loitering": 
// garbage collector can reclaim memory only if no outstanding references
public String pop()
{	String item = s[--N]; s[N] = null;	return item;	}

‣ resizing arrays

Stack: resizing-array implementation

Q. How to grow and shrink array?

Problem. Requiring client to provide capacity does not implement API!

First try.

• push(): increase size of array s[] by 1.
• pop(): decrease size of array s[] by 1.

Too expensive.

• Need to copy all items to a new array.

• Inserting first N items takes time proportional to $1+2+…+N\sim N^2/2$.

Challenge: Ensure that array resizing happens infrequently.

Q. How to grow array?

A.

If array is full, create a new array of twice(“repeated doubling”) the size, and copy items.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public ResizingArrayStackOfStrings()
{  s = new String[1];  }

public void push(String item)
{
    if (N == s.length) resize(2 * s.length);
    s[N++] = item;
}

private void resize(int capacity)
{
    String[] copy = new String[capacity];
    for (int i = 0; i < N; i++)
        copy[i] = s[i];
    s = copy;
}

Consequence.

Cost of inserting first N items: Inserting first N items takes time proportional to N (not N 2 ).

$\begin{align} N_{1\ array\ access/push}+(2+4+8+…+N)_{k\ array\ accesses\ to\ double\ to\ size\ k,(ignoring\ cost\ to\ create\ new\ array)}~3N \end{align}$

Q. How to shrink array?

First try：Too expensive in worst case.

• Consider push-pop-push-pop-... sequence when array is full.
• Each operation takes time proportional to $N$.

Efficient try.

1
2
3
4
5
6
7

public String pop()
{
    String item = s[--N];
    s[N] = null;
    if (N > 0 && N == s.length/4) resize(s.length/2);
    return item;
}

Invariant: Array is between 25% and 100% full.

performance

Amortized analysis.

Average running time per operation over a worst-case sequence of operations.

Proposition.

Starting from an empty stack, any sequence of $M$ push and pop operations takes time proportional to $M$.

memory usage

Proposition.

Uses between ~ $8\ N$ and ~ $32\ N$ bytes to represent a stack with $N$ items.

• ~ 8 $N$ when full.
• ~ 32 $N$ when one-quarter full.

This accounts for the memory for the stack (but not the memory for strings themselves, which the client owns).

resizing array vs. linked list

Tradeoffs.

Can implement a stack with either resizing array or linked list; save a link to the list; client can use interchangeably. Which one is better?

Linked-list implementation.

• Every operation takes constant time in the worst case.
• Uses extra time and space to deal with the links.

Resizing-array implementation.

• Every operation takes constant amortized time.
• Less wasted space.

‣ queues


linked-list representation

‣ generics

Parameterized stack

‣ iterators

Design challenge

Support iteration over stack items by client, without revealing the internal representation of the stack.

Java solution: Make stack implement the java.lang.Iterable interface.

Iterators

• What is an Iterable? – Has a method that returns an Iterator.

1
2
3
4

 public interface Iterable<Item>
{
   Iterator<Item> iterator();
}

• What is an Iterator? – Has methods hasNext() and next().

1
2
3
4
5
6

public interface Iterator<Item>
{
   boolean hasNext();
   Item next();
   void remove(); // optional; use at your own risk
}

• Why make data structures Iterable? – Java supports elegant client code.

1
2
3
4
5
6
7
8

for (String s : stack) StdOut.println(s); // shorthand
||
// longhand
Iterator<String> i = stack.iterator(); while (i.hasNext())
{
  String s = i.next();
  StdOut.println(s);
}

Stack iterator: linked-list implementation

Stack iterator: array implementation

Bag API


Main application. Adding items to a collection and iterating (when order doesn’t matter).

Implementation. Stack (without pop) or queue (without dequeue).

‣ applications

Java collections library

List interface.

java.util.List is API for an sequence of items.

Implementations.

caveat: only some operations are efficient

• java.util.ArrayList uses resizing array;
• java.util.LinkedList uses linked list.

java.util.Stack

• Supports push(), pop(), and and iteration.
• Extends java.util.Vector, which implements java.util.List interface from previous slide, including, get() and remove().
• Bloated and poorly-designed API (why?)

java.util.Queue： An interface, not an implementation of a queue.

Best practices：Use our implementations of Stack, Queue, and Bag.

War story (from Assignment 1)

Generate random open sites in an N-by-N percolation system.

• Jenny: pick(i,j) at random; if already open, repeat. | Takes ~$c_1N^2$ seconds.

• Kenny: create a java.util.ArrayList of $N^2$ closed sites. Pick an index at random and delete. | Takes ~$c_2N^4$ seconds.

Lesson. Don’t use a library until you understand its API!

This course. Can’t use a library until we’ve implemented it in class.

Stack applications

• Parsing in a compiler.
• Java virtual machine.
• Undo in a word processor.
• Back button in a Web browser.
• PostScript language for printers.
• Implementing function calls in a compiler.

Function Calls

How a compiler implements a function.

Recursive function: Function that calls itself.

Note: Can always use an explicit stack to remove recursion

• Function call: push local environment and return address.
• Return: pop return address and local environment.

‣ 1.4 ANALYSIS OF ALGORITHMS Introduction

Stake holder

• Programmer
• Client
• Theoretician
• Blocking and tackling

Successes

FFT algorithm: Discrete Fourier transform.

• Break down waveform of N samples into periodic components.
• Applications: DVD, JPEG, MRI, astrophysics, ….
• Brute force: N² steps.
• FFT algorithm: NlogN steps, enables new technology.

Barnes-Hut algorithm: N-Body Stimulation

• Simulate gravitational interactions among N bodies.
• Brute force: N² steps.
• Barnes-Hut algorithm: NlogN steps, enables new research

Scientific method

A framework for predicting performance and comparing algorithms.

• Observe some feature of the natural world.
• Hypothesize a model that is consistent with the observations. Predict events using the hypothesis.
• Verify the predictions by making further observations.
• Validate by repeating until the hypothesis and observations agree.

Principles

• Experiments must be reproducible.
• Hypotheses must be falsifiable.

Example 3-SUM : Brute-force Algorithm

Given N distinct integers, how many triples sum to exactly zero —- Deeply related to problems in computational geometry.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public class ThreeSum {
	public static int count(int[] a) {
		int N = a.length;
		int count = 0;
		for (int i=0; i<N; i++) 
			for (int j = i+1; j < N; j++) 
				for (int k = j+1; k < N; k++) // check each triple
					if (a[i] + a[j] + a[k] == 0) // for simplicity, ignore integer overflow
						count++;
		return count;
	}

	public static void main(String[] args) {
		int[] a = In.readInts(args[0]);
		StdOut.println(count(a));
	}
}

Messure Running Time

1
2
3
4
5
6
7

public static void main(String[] args)
{
	int[] a = In.readInts(args[0]);
	Stopwatch stopwatch = new Stopwatch();
	StdOut.println(ThreeSum.count(a)); 
	double time = stopwatch.elapsedTime();
}

Empirical analysis

Data analysis

Standard plot.

Log-log plot.

Plot running time T(N) vs. input size N using log-log scale.

Regression.

Hypothesis.

Prediction and validation

Doubling hypothesis - Quick way to estimate b in a power-law relationship

Experimental algorithmics

‣ Mathematical models for running time

Total running time: sum of cost × frequency for all operations.

• Need to analyze program to determine set of operations.
• Cost depends on machine, compiler.
• Frequency depends on algorithm, input data.

Example 1-SUM:

Q. How many instructions as a function of input size N ?

1
2
3
4

int count = 0;
for (int i = 0; i < N; i++)
   if (a[i] == 0)
      count++;

Example 2-SUM

Q. How many instructions as a function of input size N ?

1
2
3
4
5

int count = 0;
for (int i = 0; i < N; i++)
   for (int j = i+1; j < N; j++)
      if (a[i] + a[j] == 0)
				count++;

Simplification of calculation：

1. cost model: Use some basic operation as a proxy for running time.

2. tilde notation

   Technical definition: $f(N)$~$g(N)$ means $$ \lim_{N \to \infty} \frac{f(N)}{g(N)}=1 $$

   • Estimate running time (or memory) as a function of input size N.
   • Ignore lower order terms.
     • when N is large, terms are negligible
     • when N is small, we don’t care

Q. Approximately how many array accesses as a function of input size N ?

A. ~$N^2$ array accesses.

Bottom line. Use cost model and tilde notation to simplify counts

Example 3-SUM

Q. Approximately how many array accesses as a function of input size N ?

1
2
3
4
5
6

int count = 0;
for (int i = 0; i < N; i++)
   for (int j = i+1; j < N; j++)
      for (int k = j+1; k < N; k++)
         if (a[i] + a[j] + a[k] == 0)
            count++;

A. ~$\frac{1}{2}N^3$ array accesses.

Estimating a discrete sum

Q. How to estimate a discrete sum?

A1. Take discrete mathematics course.

A2. Replace the sum with an integral, and use calculus!

‣ Order-of-growth classifications

the small set of functions suffices to describe order-of-growth of typical algorithms. —— $1$, $logN$, $N$, $NlogN$, $N^2$, $N^3$, $2^N$

Bottom line. Need linear or linearithmic alg to keep pace with Moore’s law.

‣ theory of algorithms

Type of analyses

• Best case. Lower bound on cost.

Determined by “easiest” input.

Provides a goal for all inputs.

• Worst case. Upper bound on cost.

Determined by “most difficult” input.

Provides a guarantee for all inputs.

• Average case. Expected cost for random input.

Need a model for “random” input.

Provides a way to predict performance.

Actual data might not match input model?

• Need to understand input to effectively process it.

• Approach 1: design for the worst case.

• Approach 2: randomize, depend on probabilistic guarantee.

Goals:

• Establish “difficulty” of a problem.
• Develop “optimal” algorithms.

Approach.

• Suppress details in analysis: analyze “to within a constant factor”.
• Eliminate variability in input model by focusing on the worst case.

Optimal algorithm.

• Performance guarantee (to within a constant factor) for any input.
• No algorithm can provide a better performance guarantee.

Commonly-used notations

Algorithm design approach

Start.

• Develop an algorithm.
• Prove a lower bound.

Gap?

• Lower the upper bound (discover a new algorithm).
• Raise the lower bound (more difficult).

Golden Age of Algorithm Design.

• 1970s-. Steadily decreasing upper bounds for many important problems.
• Many known optimal algorithms.

Caveats.

• Overly pessimistic to focus on worst case?
• Need better than “to within a constant factor” to predict performance.

‣ memory

Basics

• Bit. 0 or 1.
• Byte. 8 bits.
• Megabyte (MB). 1 million or 220 bytes.
• Gigabyte (GB). 1 billion or 230 bytes.
• 64-bit machine. We assume a 64-bit machine with 8 byte pointers.
  • Can address more memory.
  • Pointers use more space.（some JVMs “compress” ordinary object pointers to 4 bytes to avoid this cost）

Typical memory usage for primitive types and arrays

for primitive types

for one-dimensional arrays

for two-dimensional arrays

Typical memory usage for objects in Java

• Object overhead. 16 bytes.
• Reference. 8 bytes.
• Padding. Each object uses a multiple of 8 bytes.

Memory Usage Summary

Total memory usage for a data type value:

• Primitive type: 4 bytes for int, 8 bytes for double, …
• Object reference: 8 bytes.
• Array: 24 bytes + memory for each array entry.
• Object: 16 bytes + memory for each instance variable + 8 bytes if inner class (for pointer to enclosing class).
• Padding: round up to multiple of 8 bytes.

Shallow memory usage: Don’t count referenced objects.

Deep memory usage: If array entry or instance variable is a reference, add memory (recursively) for referenced object.

1.5 UNION_FIND‣ DYNAMIC CONNECTIVITY

Given a set of N objects.

• Union command: connect two objects.
• Find/connected query: is there a path connecting the two objects?

Modeling the objects

Applications involve manipulating objects of all types.

• Pixels in a digital photo.
• Computers in a network.
• Friends in a social network.
• Transistors in a computer chip.
• Elements in a mathematical set.
• Variable names in Fortran program.
• Metallic sites in a composite system.

When programming, convenient to name objects 0 to N –1.

• Use integers as array index.

• Suppress details not relevant to union-find.

  (can use ST to translate from site names to integers: stay tuned (Chapter 3))

Modeling the connections

We assume “is connected to” is an equivalence relation:

• Reflexive: p is connected to p.
• Symmetric: if p is connected to q, then q is connected to p.
• Transitive: if p is connected to q and q is connected to r, then p is connected to r.

Implementing the operations

• Find query. Check if two objects are in the same component.
• Union command. Replace components containing two objects with their union.

Union-find data type (API)

Goal. Design efficient data structure for union-find.

• Number of objects N can be huge.
• Number of operations M can be huge.
• Find queries and union commands may be intermixed.

Dynamic-connectivity client

• ・Read in number of objects N from standard input.
• ・Repeat:
  • – read in pair of integers from standard input
  • – if they are not yet connected, connect them and print out pair

1
2
3
4
5
6
7
8
9
10
11
12
13

public static void main(String[] args)
{
	int N = StdIn.readInt(); 
	UF uf = new UF(N);
	while (!StdIn.isEmpty()) {
		int p = StdIn.readInt(); 
		int q = StdIn.readInt(); 
		if (!uf.connected(p, q)) {
			uf.union(p, q);
			StdOut.println(p + " " + q); 
		}
	} 
}

‣ QUICK-FIND

Eager approach

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class QuickFindUF
{
    private int[] id;

    public QuickFindUF(int N)
    {
        id = new int[N];
        for (int i = 0; i < N; i++) {
            id[i] = i;
        }
    }

    public boolean connected(int p, int q)
    {   return id[p] == id[q];  }

    public void union(int p, int q)
    {
        int pid = id[p];
        int qid = id[q];
        for (int i = 0; i < id.length; i++) {
            if (id[i] == pid)
                id[i] = qid;
    }
}

Data Structure

• Integer array id[] of length N.
• Interpretation: p and q are connected iff they have the same id.

Find.

Check if p and q have the same id.

Union.

To merge components containing p and q, change all entries whose id equals id[p] to id[q].

Quick-Find is too slow

Cost model. Number of array accesses (for read or write).

order of growth of number of array accesses:

Union is too expensive :It takes $N^2$ array accesses to process a sequence of $N$ union commands on $N$ objects.

Quadratic algorithms do not scale

‣ QUICK-UNION

Lazy approach

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public class QuickUnionUF
{
    private int[] id;

    public QuickUnionUF(int N)
    {		// set id of each object to itself (N array accesses)
        id = new int[N];
        for (int i = 0; i < N; i++) id[i] = i;
    }

    private int root(int i)
    {		// chase parent pointers until reach root (depth of i array accesses)
        while (i != id[i])  i = id[i];
        return i;
    }

    public boolean connected(int p, int q)
    // check if p and q have same root (depth of p and q array accesses)
    {   return root[p] == root[q];  }

    public void union(int p, int q)
    {		// change root of p to point to root of q (depth of p and q array accesses)
        int i = root(p);
        int j = root(q);
        id[i] = j;
    }
}

Data structure

• Integer array id[] of length N.
• Interpretation: id[i] is parent of i.
• Root of i is id[id[id[...id[i]...]]](keep going until it doesn’t change (algorithm ensures no cycles))

Find.

Check if p and q have the same root.

Union.

To merge components containing p and q, set the id of p’s root to the id of q’s root.

Quick-union is also too slow

Cost model. Number of array accesses (for read or write).

Quick-find defect.

• Union too expensive ( $N$ array accesses).
• Trees are flat, but too expensive to keep them flat.

Quick-union defect.

• Trees can get tall.
• Find too expensive (could be N array accesses).

‣ IMPROVEMENT

1 Weighted quick-union.

• Modify quick-union to avoid tall trees.

• Keep track of size of each tree (number of objects).

• Balance by linking root of smaller tree to root of larger tree.

  (reasonable alternatives: union by height or “rank”)

Quick-union and weighted quick-union example

Weighted quick-union: Java implementation

Data structure.

Same as quick-union, but maintain extra array sz[i] to count number of objects in the tree rooted at i.

Find.

Identical to quick-union.

1

return root(p) == root(q);

Union.

Modify quick-union to:

• Link root of smaller tree to root of larger tree.
• Update the sz[] array.

1
2
3
4
5

int i = root(p);
int j = root(q);
if (i == j) return;
if (sz[i] < sz[j])  {   id[i] = j; sz[j] += sz[i];    }
else                {   id[j] = i; sz[i] += sz[j];    }

Weighted quick-union analysis

Running time.

• Find: takes time proportional to depth of p and q.
• Union: takes constant time, given roots.

Proposition.

($lg=base-2$ logarithm) Depth of any node $x$ is at most $lgN$

Pf. When does depth of x increase?

Increases by $1$ when tree $T_1$ containing $x$ is merged into another tree $T_2$.

• The size of the tree containing $x$ at least doubles since $|T_2|≥|T_1|$.

• Size of tree containing $x$ can double at most $lgN$ times. Why?

  

Q. Stop at guaranteed acceptable performance?

A. No, easy to improve further.

Improvement 2: path compression

Quick union with path compression.

Just after computing the root of p, set the id of each examined node to point to that root.

Path compression: Java implementation

Two-pass implementation:

add second loop to root() to set the id[] of each examined node to the root.

Simpler one-pass variant:

Make every other node in path point to its grandparent (thereby halving path length).

1
2
3
4
5
6
7
8
9

private int root(int i)
{
    while (i != id[i]) 
    {
        id[i] = id[id[i]];  // only one extra line of code !
        i = id[i];
    }
    return i; 
}

In practice.

No reason not to! Keeps tree almost completely flat.

Weighted quick-union with path compression: amortized analysis

Proposition. |[Hopcroft-Ulman, Tarjan]

Starting from an empty data structure, any sequence of $M$ union-find ops on $N$ objects makes $≤c;(N+M;lg*N)$ array accesses.

• Analysis can be improved to $N+M;α(M,N)$.
• Simple algorithm with fascinating mathematics.

iterate log function:

Linear-time algorithm for M union-find ops on N objects?

• Cost within constant factor of reading in the data.
• In theory, WQUPC is not quite linear.
• In practice, WQUPC is linear.

Amazing fact. |[Fredman-Saks]

in “cell-probe” model of computation

No linear-time algorithm exists

Summary

Bottom line.

Weighted quick union (with path compression) makes it possible to solve problems that could not otherwise be addressed.

Ex. | [109 unions and finds with 109 objects]

• WQUPC reduces time from 30 years to 6 seconds.
• Supercomputer won’t help much; good algorithm enables solution.

‣ APPLICATIONS

Union-find applications

• Percolation.
• Games (Go, Hex).
• Dynamic connectivity. ✓
• Least common ancestor.
• Equivalence of finite state automata.
• Hoshen-Kopelman algorithm in physics.
• Hinley-Milner polymorphic type inference.
• Kruskal’s minimum spanning tree algorithm.
• Compiling equivalence statements in Fortran.
• Morphological attribute openings and closings.
• Matlab’s bwlabel() function in image processing.

Percolation

A model for many physical systems:

• N-by-N grid of sites.
• Each site is open with probability $p$ (or blocked with probability $1–p$).
• System percolates iff top and bottom are connected by open sites.

Likelihood of percolation

Depends on site vacancy probability p.

Percolation phase transition

When $N$ is large, theory guarantees a sharp threshold $p^*$.

• $p>p^*$: almost certainly percolates.
• $p<p^*$: almost certainly does not percolate.

Q. What is the value of $p^*$ ?

A. About 0.592746 for large square lattices.

constant known only via simulation

Monte Carlo simulation

• Initialize $N-by-N$ whole grid to be blocked.
• Declare random sites open until top connected to bottom.
• Vacancy percentage estimates $p^*$.

Dynamic connectivity solution to estimate percolation threshold

Q. How to check whether an N-by-N system percolates?

Q. How to check whether an N-by-N system percolates?

• Create an object for each site and name them $0$ to $N^2–1$.

• Sites are in same component if connected by open sites.

• Percolates iff any site on bottom row is connected to site on top row.

  (brute-force algorithm: N 2 calls to connected())

Clever trick.

• Introduce 2 virtual sites (and connections to top and bottom).

• Percolates iff virtual top site is connected to virtual bottom site.

  (efficient algorithm: only 1 call to connected())

Q. How to model opening a new site?

A. Mark new site as open; connect it to all of its adjacent open sites.

(up to 4 calls to union())

Percolation Exercise

Java Environment

1
2
3

import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.StdStats;
import edu.princeton.cs.algs4.WeightedQuickUnionUF;

Note that your code must be in the default package; if you use a package statement, the autograder will reject your submission.

Percolation.

Given a composite systems comprised of randomly distributed insulating and metallic materials: what fraction of the materials need to be metallic so that the composite system is an electrical conductor?

Given a porous landscape with water on the surface (or oil below), under what conditions will the water be able to drain through to the bottom (or the oil to gush through to the surface)?

Scientists have defined an abstract process known as percolation to model such situations.

The model.

We model a percolation system using an n-by-n grid of sites.

Each site is either open or blocked.

A full site is an open site that can be connected to an open site in the top row via a chain of neighboring (left, right, up, down) open sites. We say the system percolates if there is a full site in the bottom row.

In other words, a system percolates if we fill all open sites connected to the top row and that process fills some open site on the bottom row. (For the insulating/metallic materials example, the open sites correspond to metallic materials, so that a system that percolates has a metallic path from top to bottom, with full sites conducting.

For the porous substance example, the open sites correspond to empty space through which water might flow, so that a system that percolates lets water fill open sites, flowing from top to bottom.)

The problem.

In a famous scientific problem, researchers are interested in the following question:

if sites are independently set to be open with probability $p$ (and therefore blocked with probability $1−p$), what is the probability that the system percolates? When $p$ equals 0, the system does not percolate; when $p$ equals 1, the system percolates.

The plots below show the site vacancy probability $p$ versus the percolation probability for 20-by-20 random grid (left) and 100-by-100 random grid (right).

When n is sufficiently large, there is a threshold value $p^*$ such that when $p<p^*$ a random n*-by-n grid almost never percolates, and when $p>p^$, a random n-by-n grid almost always percolates.

No mathematical solution for determining the percolation threshold $p^*$ has yet been derived. Your task is to write a computer program to estimate $p^*$.

Percolation data type.

To model a percolation system, create a data type Percolation with the following API:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class Percolation {

    // creates n-by-n grid, with all sites initially blocked
    public Percolation(int n)

    // opens the site (row, col) if it is not open already
    public void open(int row, int col)

    // is the site (row, col) open?
    public boolean isOpen(int row, int col)

    // is the site (row, col) full?
    public boolean isFull(int row, int col)

    // returns the number of open sites
    public int numberOfOpenSites()

    // does the system percolate?
    public boolean percolates()

    // test client (optional)
    public static void main(String[] args)
}

Corner cases.

By convention, the row and column indices are integers between 1 and $n$, where $(1,1)$ is the upper-left site: Throw an IllegalArgumentException if any argument to open(), isOpen(), or isFull() is outside its prescribed range.

Throw an IllegalArgumentException in the constructor if $n≤0$.

Performance requirements.

The constructor must take time proportional to n2; all instance methods must take constant time plus a constant number of calls to union() and find().

Monte Carlo simulation.

To estimate the percolation threshold, consider the following computational experiment:

• Initialize all sites to be blocked.
• Repeat the following until the system percolates:
• Choose a site uniformly at random among all blocked sites.
• Open the site.
• The fraction of sites that are opened when the system percolates provides an estimate of the percolation threshold.

For example, if sites are opened in a 20-by-20 lattice according to the snapshots below, then our estimate of the percolation threshold is 204/400 = 0.51 because the system percolates when the 204th site is opened.

By repeating this computation experiment T times and averaging the results, we obtain a more accurate estimate of the percolation threshold. Let xt be the fraction of open sites in computational experiment t. The sample mean x⎯⎯⎯x¯ provides an estimate of the percolation threshold; the sample standard deviation s; measures the sharpness of the threshold.

$$\begin{align} \overline{x}=\frac{x_1+x_2+…+x_T}{T}, \tag{1}s^2=\frac{(x_1-\overline{x})^2+(x_2-\overline{x})^2+…+(x_T-\overline{x})^2}{T-1} \end{align}$$

Assuming T is sufficiently large (say, at least 30), the following provides a 95% confidence interval for the percolation threshold:

$$\begin{align} \overline{x}-\frac{1.96s}{\sqrt{T}}, \tag{2}\overline{x}+\frac{1.96s}{\sqrt{T}}, \end{align}$$

To perform a series of computational experiments, create a data type PercolationStats with the following API.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public class PercolationStats {

    // perform independent trials on an n-by-n grid
    public PercolationStats(int n, int trials)

    // sample mean of percolation threshold
    public double mean()

    // sample standard deviation of percolation threshold
    public double stddev()

    // low endpoint of 95% confidence interval
    public double confidenceLo()

    // high endpoint of 95% confidence interval
    public double confidenceHi()

   // test client (see below)
   public static void main(String[] args)
}

Throw an IllegalArgumentException in the constructor if either n ≤ 0 or trials ≤ 0.

Also, include a main() method that takes two command-line arguments n and T, performs T independent computational experiments (discussed above) on an n-by-n grid, and prints the sample mean, sample standard deviation, and the 95% confidence interval for the percolation threshold. Use StdRandom to generate random numbers; use StdStats to compute the sample mean and sample standard deviation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

~/Desktop/percolation> java-algs4 PercolationStats 200 100
mean                    = 0.5929934999999997
stddev                  = 0.00876990421552567
95% confidence interval = [0.5912745987737567, 0.5947124012262428]

~/Desktop/percolation> java-algs4 PercolationStats 200 100
mean                    = 0.592877
stddev                  = 0.009990523717073799
95% confidence interval = [0.5909188573514536, 0.5948351426485464]

~/Desktop/percolation> java-algs4 PercolationStats 2 10000
mean                    = 0.666925
stddev                  = 0.11776536521033558
95% confidence interval = [0.6646167988418774, 0.6692332011581226]

~/Desktop/percolation> java-algs4 PercolationStats 2 100000
mean                    = 0.6669475
stddev                  = 0.11775205263262094
95% confidence interval = [0.666217665216461, 0.6676773347835391]

Analysis of running time and memory usage (optional and not graded).

Implement the Percolation data type using the quick find algorithm in QuickFindUF.

Use Stopwatch to measure the total running time of PercolationStats for various values of n and T.

• How does doubling n affect the total running time?

• How does doubling T affect the total running time?

• Give a formula (using tilde notation) of the total running time on your computer (in seconds) as a single function of both n and T.

• Using the 64-bit memory-cost model from lecture, give the total memory usage in bytes (using tilde notation) that a Percolation object uses to model an n-by-n percolation system.

• Count all memory that is used, including memory for the union–find data structure.

Now, implement the Percolation data type using the weighted quick union algorithm in WeightedQuickUnionUF. Answer the questions in the previous paragraph.