Week 1
The Three Sum Problem
Suppose we have a list of numbers, and we want to find all distinct triples of numbers in the list which sum to 0.
Suppose we try all permutations of numbers (a brute force approach). How would we find the running time?
Empirical analysis
Try to time the program on different input sizes N. However, this means you’re stuck waiting for the program every time, which sort of defeats the purpose of doing it in the first place.
Data analysis
Plot running time against input size, and try to use regression in order to fit a line to the function. This allows us to extrapolate points without running the experiment a bunch of times.
We can use the doubling hypothesis in situations where the input obeys a power law. We double the size of the input each time and find the constant $b$ which the $\log$ of the ratios converge to. The running time of the algorithm will be $aN^b$, where a is some constant we can estimate by solving for at some large given value of N.
Empirical analysis and data analysis are both examples of experimental algorithmics, which have to deal with system dependent effects such as hardware and software as well as system independent effects such as the algorithm and the input data. Also, it’s tough to make precise measurements. We’d much rather do mathematical analysis.
Mathematical Analysis
The general idea is to count the number of operations which “count” according to some cost model, instead of trying to find the clock cycles required for every operation of an algorithm. Discrete mathematics helps with this, and so does integration.
The different types of order notation ($O(n), o(n), \omega(n), \theta(n)$) all count as mathematical analysis.
Order of Growth Classifications
Usually, it suffices to classify algorithms into these types.
| Order of Growth | Typical Code | description |
|---|---|---|
| $O(1)$ | a = b + c; |
statement |
| $O(\log(N))$ | while(N > 1) {N = N / 2; ...} |
divide in half |
| $O(N), O(N^2), O(N^3)$ | \\ 1 for loop, 2 nested loops, 3 nested loops |
loops |
| $O(N\log(N))$ | \\ merge sort |
divide and conquer |
| $O(2^n)$ | \\ combinatorial search |
exhaustive search |
We need linear or logarithmic algorithms to keep up with Moore’s Law of doubling transistors/problem size.
Consider the binary search algorithm:
public static int binarySearch(int [] a, int key) {
int low = 0;
int high = a.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if(key < a[mid])
high = mid - 1;
if(key > a[mid])
low = mid + 1;
if(key == a[mid])
return mid;
}
return -1;
}
Define $T(N)$ to be the number of comparisons made by binarySearch on an input of size $N$. We can obtain an expression for $T(N)$ by solving a recurrence (telescoping).
\(\because T(N) \le T(N / 2) + 1, \forall N> 1 \\
T(N) \le T(N/2) + 1 \\
T(N) \le T(N/4) + 1 + 1 \\
T(N) \le T(N/N) + 1 + 1 + \dots + 1 \\
\therefore T(N) = 1 + \ln(N)\)
Consider an algorithm for the 3 sum problem, which finds 3 distinct integers in a set which sum to 0:
Sort the N distinct numbers
For each pair of numbers a[i], a[j]
Perform a binary search for -(a[i] + a[j]), call it a[k]
If found, return a[i], a[j], a[k] as a triple which sums to 0
This algorithm is $O(N^2\log(N))$, since finding pairs of numbers is $O(N^2)$ and binary search is $O(\log(N))$.
Theory of Algorithms
What is the runtime of quicksort, $O(N\log(N))$ or $O(N^2)$?
Both! It doesn’t make sense to talk about the runtime of an algorithm without first specifying what kind of analysis we’re doing. Best case refers to the lower bound on cost, worst case refers to the upper bound on cost, and average case refers to the expected cost. Order notation analysis is what we do once we know what case we’re talking about
The theory of algorithms refers to a general approach to estimating the difficulty of an algorithm by simplifying its analysis to be within a constant factor of its actual performance, and to focus on the worst case in order to concentrate on an input model.
For example, consider the 3 sum problem. We know that the bruteforce algorithm has a runtime of $O(N^3)$, which we can call the upper bound. Also, since we know that we must at least examine all of the elements in order to solve the problem, we have a lower bound of $\Omega(N)$. Thus, the optimal algorithm will be somewhere in between these two bounds.
In general, we want to find an upper bound and a lower bound for the runtime of our algorithm, and tighten these bounds using proofs in order to find the difficulty of an optimal solution.
Memory
Different data types take up different amounts of memory (think boolean vs. int). Objects have count the memory of their component instance primitives, and in Java specifically, include an object overhead of 16 bytes and a reference of 8 bytes. Arrays contain the amount of storage for their primitive components as well as 24 bytes of overhead.
In addition, since computer memory is usually arranged in blocks of 8 bytes, there may be additional padding on top of all of this.
Union-Find
General steps to developing a usuable algorithm:
- Model the probelm
- Find an algorithm which solves it
- Analyze runtime and memory use
- If runtime and memory usage limits aren’t satisfied, back to step 1
The Dynamic Connectivity Problem
Given a set of n objects, we define:
- a union command, which unions two elements in the set
- find/connected query, which returns whether there is a path connecting two objects (check if objects are in the same component)
An API for this might look like this:
public class UF {
UF(int N) {
// ...
}
void union(UF p, UF q) {
// ...
}
bool find(int p, int q) {
// ...
}
}
Quick-find (Eager Approach)
Use a integer array id [] of size N, which marks each index as a value in the set. At the index of each value, we record the id of the component the value belongs to.
Find is O(1), since we just check if the ids of p and q are equal. However, for union we will have to find all objects of id p and change them to have id q, or vice versa. This makes the union operation hella slow.
public class QuickFindUF {
private int [] id;
// O(N)
public QuickFindUF {
id = new int [N];
// Start off everybody in their own components
for(int i = 0; i < N; i++) {
id[i] = i;
}
}
// O(1)
public boolean connected(int p, int q) {
return id[p] == id[q];
}
// O(N)
public void union(int p, int q) {
int pid = id[p]; // my element id
int qid = id[q]; // your element id
for(int i = 0; i < id.length; i++) {
// if you put id[p] here, it might get overwritten with qid
if(id[i] == pid) {
id[i] = qid;
}
}
}
}
If we wanted to union N elements from q into p, then this algorithm would be $O(n^2)$, which is quadratic time.
Quadratic algorithms do not scale.
As computers get faster, they can address more memory, meaning that the problem size grows faster than the computing power to address it. So quadractic algorithms actually get slower as computers get faster.
Quick Union (Lazy Approach)
Use a integer array id [] of size N, where each id[i] means the parent of i. If there is no parent, then id[i] = i.
Then, to find, we check if p and q have the same root. To union, we set the id of p’s root to the id of q’s root (we make p a child of q).
public class QuickUnionUF {
private int [] id;
// O(N)
public QuickUnionUF(int N) {
id = new int[N];
for(int i = 0; i < N; i++) {
id[i] = i;
}
}
// O(log(N)) best case, O(N) worst case
private int root(i) {
while(id[i] != i) {
id[i] = id[id[i]]; // path compression
i = id[i];
}
return i;
}
// O(log(N)) best case, O(N) worst case
public boolean connected(int p, int q) {
return root(p) == root(q);
}
// O(log(N)) best case, O(N) worst case
public void union(int p, int q) {
int i = root(p);
int j = root(q);
id[i] = j; // change root of p to point of root of q
}
}
Improvements
Weighting
We keep track of the height of each tree, and we always make the smaller tree the child of the larger tree.
With this, we can guarantee $O(\log(n))$ runtime for union and find.
Proof: When a tree’s height increases, the child that the tree is adding must be at least as large as the existing tree. If it were larger, then that child should be the root instead. Thus, the size of a tree at least doubles each time its height increases. Then, the height of the tree can double at most $\log(N)$ times.
We can make a similar guarantee for union by size.
Path compression
After computing a path to a root of p, set each node in the path to point directly to the root. We can do this by adding a second loop to root(int i) to loop through the id of each examind node, or we can use the simpler one pass variant above.
These improvements result in nearly $O(n)$ time, which is really great because union-find is impossible in strictly $O(n)$ time.
Union-find Applications
Percoloation
Conside a N by N grid of sites, each of which are either open or closed. Each site is open with probability p. We say that the system is percolated if there is a path of open sites from the top to the bottom.
Concrete examples of this: fluid flow, social interactions (friend groups), electricity flow
For N large, there exists a sharp percolation phase transition between values of p for which the system almost certainly percolates, and values of p for which the system almost certainly does not percolate. We call the threshold $p = p^*$.
This sounds like a mathematical problem, but we actually solve it experimentally using the union-find computation described earlier. This process is called a Monte Carlo simulation.
Monte Carlo simulation:
- Initialize a N by N grid to be blocked
- Declare random sites open until top connected to bottom
- Once connected, measure the percentage of open sites as $p^*$.
How do we check whether an N by N system percolates? We don’t want to check for percolation along the top or bottom row, because that would result in $O(n^2)$ calls.
Instead, we’ll connect the top open sites to a root (virtual top) and the bottom open sites to a root (virtual bottom) and check for percolation on that.