Algorithmic paradigms

[greedy | divide and conquer | dynamic programming]

Designing algorithms

There is no single recipe for inventing algorithms
There are basic rules:
- Understand your problem well – may require much mathematical analysis!
- Use existing algorithms (reduction) or algorithmic ideas

Algorithmic Paradigms

Greedy: build up a solution incrementally, myopically optimize some local criteria
Divide and Conquer: break up a problem into non-overlapping subproblems, solve subproblems independently, and then combine solutions to the subproblems to form solution to the original problem.
Dynamic Programming (DP): break up a problem into a series of overlapping subproblems, and build up solutions to larger and larger subproblems

Greedy Algorithm

Greedy algorithms do not always yield optimal solutions, but for many problems they do.
- Greedy-choice property (definition) :
  a globally optimal solution can be arrived at by making a locally optimal (greedy) choice.
- Optimal substructure (definition):
  a problem exhibits optimal substructure if an optimal solution to the problem contains within itself optimal solutions to subproblems, or in other words,
  a problem optimal substructure if an optimal solution to the problem can be efficiently constructed from optimal solutions of its subproblems.
Examples of greedy algorithms:

we have seen a greedy algorithm before: the Huffman tree building (see notes).
Cashier's algorithm:

determine the minimum number of coins to give when providing change to the customer:
- at each iteration, add one coin of the largest value that does not go above the total amount to be paid
The cashier's algorithm is optimal for U.S. coinage (but it may not be optimal for other currency coinage).
Activity selection problem:

Suppose we have:
- a set $S = { 1, 2, . . . , n}$ of $n$ activities (e.g. class meetings)
- that compete for the same resource (e.g. a classroom),
- which can be used by only one activity (e.g. a class meeting) at a time.
Each activity $i$ has a start time $s_i$ and a finish time $f_i$, where $s_i \leq f_i$.
Activities $i$ and $j$ are compatible if the intervals $[s_i, f_i)$ and $[s_j,f_j)$ do not overlap (i.e., $i$ and $j$ are compatible if $s_i >= f_j$ or $s_j >= f_i$).
The activity-selection problem is to select a maximum-size set of mutually compatible activities.

The greedy-activity-selector algorithm to solve this:
- Sort the activities by increasing finish time
- Pick one with the earliest finish time that can be legally scheduled, repeatedly, until no more activities can be scheduled.
Example of activity-selection:

The activity picked by the greedy-activity-selector is a "greedy" choice in the sense that, intuitively, it leaves as much opportunity as possible for the remaining activities to be scheduled.
The greedy algorithm is guarannteed to find an optimal solution.

(important question: what's the time complexity of the greedy-activity-selector algorithm?)
0-1 knapsack problem & Fractional knapsack problem:

0-1 knapsack problem:

A thief robbing a store finds $n$ items; the $i$th item is worth $v_i$ dollars and weighs $w_i$ pounds, where $v_i$ and $w_i$ are integers.
The thief wants to take as valuable a load as possible, but he can carry at most $W$ pounds in his knapsack for some integer W.
What items should they take to maximize the value of the items (that don't weigh more than they can carry)?

(each item must either be taken or left behind; the thief cannot take a fractional amount of an item or take an item more than once.)

Fractional knapsack problem:

same as the 0-1 knapsack problem, but in this case the thief can take a fractional amount of an item.

Many resource allocation problems can be cast in the framework of a knapsack problem. The general idea is to think of the capacity of the knapsack as the available amount of a resource, and the item types as activities to which this resource can be allocated.

Consider this problem instance:
there are 3 items (item 1 weighs 1 pound and is worth 60 dollars, item 2 weighs 2 pounds and is worth 100 dollars, and item 3 weighs 3 pounds and is worth 120 dollars), and the knapsack can hold 5 pounds.
- 0-1 knapsack problem: greedy solution (160 dollars) != optimal solution (220 dollars).
  The optimal solution can be derived using a dynamic programming algorithm (see below)
- fractional knapsack problem: greedy solution = optimal solution (240 dollars)!
We will also see that greedy algorithms can be used to solve Minimum Spanning Tree (MST) problem.

Divide and Conquer

Basic idea:
when trying to solve a large problem, focus only on using a smaller solution to get to the larger one.
do not worry about how to solve the smaller problem (since it will be solved using an even smaller one!)

Quicksort uses a divide-and-conquer algorithm.

	public void sort(int i, int j) {
		int pivotIndex = findPivot(i, j);
		swapNodes(pivotIndex, j); //Place pivot in the end
		int k = partition(list[j], i-1, j);
		//Put pivot back in place; 
		swapNodes(k, j); 
		if(k > i + 1) { sort(i, k-1); }
		if(j > k + 1) { sort(k+1, j); }
	}

Recursion

Recursion:
a recursive method is a method that contains a call to itself.
Recursion allows programming in a style that reflects divide-and-conquer algorithmic thinking.

A classic example — Computing Fibonacci numbers:

Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584…
$F_n = F_{n-1} + F_{n-2}$, $F_0 = 0$, and $F_1 = 1$

	//Recursively generate the nth Fibonacci number: top-down
	public static long FibRecursive(int n) {
		assert (n > 0) && (n <= 91) : "n out of range [0-91]";	
		if(n == 0) return 0; 
		else if(n == 1) return 1;
		else {
			return FibRecursive(n - 2) + FibRecursive(n - 1);
		}
	}

Elements of a recursive program:
- Basis: a case that can be answered without using further recursive calls
- Creating the smaller problem, and invoking a recursive call on it
- Finishing to solve the original problem

Dynamic Programming

Dynamic Programming works by breaking up a problem into a series of, typically, overlapping subproblems, and building up solutions to larger and larger subproblems
Results for subproblems are computed and stored (so no need to recompute some of the subproblems) for solving bigger problems. In other words, we trade space for time.

Fibonacci number

	//Iteratively generate the nth Fibonacci number: bottom-up
	public static long FibDp(int n) {
		assert (n > 0) && (n <= 91) : "n out of range [0-91]";
		long[] nums = new long[n+1];
		nums[0] = 0;
		nums[1] = 1;
		for(int i = 2; i <= n; i ++ ) {
			nums[i] = nums[i - 1] + nums[i - 2];
		}
		return nums[n];
	}

Calculating n^th Fibonacci number: visualization of a solution using Dynamic Programming.

0-1 knapsack problem

A more formal definition: Given two lists of positive numbers $[v_1, v_2, ..., v_n]$ and $[w_1, w_2, ..., w_n]$, and $W > 0$, determine the subset $T \subseteq \{1, 2, ..., n\}$ that maximizes $\sum_{i \in T} v_i$, subject to $\sum_{i \in T} w_i \leq W$.

We need to define a new variable $V$: $V[i, w]$ stores the maximum $v$ for any subset of $[1, 2, ..., i]$ of at most combined $w$.
Recursive definition: $V[i, w] = max(V[i-1, w], v_i + V[i-1, w-w_i])$

Knapsack.java
Longest common subsequence problem

Given two sequences, the problem is to find the longest subsequence that is common to the input sequences. The characters in a subsequence are not necessarily in a contiguous block. For example, the lonest common subsequence between "abcbdab" and "bdcaba" is "bdab", which has length of 4.
Given two sequences $a_1a_2a_3...a_m$ and $b_1b_2b_3...b_n$, of length m and n, respectively. Define LCS[i, j] as the length of the longest common subsequence between their prefixes, $a_1a_2a_3...a_i$ and $b_1b_2b_3...b_j$, respectively.
- If $a_i$ != $b_j$, LCS[i, j] = max(LCS[i-1,j], LCS[i,j-1]) (the desired subsequence ignores $a_i$ or $b_j$)
- Otherwise, LCS[i, j] = 1 + LCS[i-1, j-1] (the desired subsequence has $a_i$ and $b_j$ match)
Edit distance (for string comparison)

Levenshtein (1966) introduced edit distance between two strings as the minimum number of elementary operations (insertions, deletions, and substitutions) to transform one string into the other.
Edit distance vs Hamming distance).
Given two sequences, $a=a_1...a_m$ and $b=b_1...b_n$
```
//initialization
for(i = 0; i <= m; i ++) d[i][0] = i;
for(j = 0; j <= n; j ++) d[0][j] = j; 
//fill the DP table
for(i = 1; i <= m; i ++)  {
        for(j = 1; j <= n; j ++) {
                if(a[i] == b[j]) c = 0;
                else c = 1; 
                d[i][j] = min(d[i-1][j] + 1, d[i][j-1] + 1, d[i-1][j-1]+c)
        }
}
//trace-back
```
where $d[i][j]$ is the edit distance between prefix $a_1...a_i$ and prefix $b_1...b_j$.
$d[m][n]$ is the edit distance two input sequences.
We will see more dynamic program algorithms (shortest path problem)

Comparison of the different algorithms

Greedy vs DP:

Dynamic Programming often solves the subproblems bottom up, a greedy strategy usually progresses in a top-down fashion, making one greedy choice after another (the choice at a step does not depend on any future choices or on the solutions to subproblems), iteratively reducing each given problem instance to a smaller one.
Divide-and-Conquer vs DP:

DP involves overlapping subproblems.