1
.Von Neumann invented RAM model in Princeton
.\matrix{1 1;1 0}^n = \matrix{F_{n+1} F_n; F_n F_{n-1}}
2
."fudge factor" c: g(n) \leq c f(n) \forall n \geq n_0
.L'Hospital rule
 # (1+1/n)^n = e^{n \ln(1+1/n)}; when n goes to infinity, \ln(1+1/n) goes
 to 0
.bound of H_n: \int_1^{1+n}(1/x)dx \leq H_n \leq 1+\int_1^n (1/x)dx
3
			//613 is prime
			//3702 = 2*3*617
			//660 = 2^2*3*5*11
			//4003 is prime
4
.O(n) median algorithm
 *partition n numbers to groups of 5 elements
 *find the median-of-5 in constant time
 *find the median of these (n/5) medians in O(n/5)
 *then (3n/10) of the n numbers can be safely discarded
5
.n! reads "n factorial"
.the merge step is called the "finger algorithm"
 *use your fingers as pointers
 *lower bound (2n-1) is proved by "adversary analysis"
.use adversary analysis to prove max(n numbers) has lower time complexity
bound (n-1)
 *everyone except the winner must lose at least once
.similarly, second best has lower bound (n-1)+\lceil\lg n\rceil-1
.sortings which beat (n\lg n) bound:
 *bucket sort (every number in range 1..k)- O(n+k) time, O(k \lg k) space
 *radix sort (select k=O(n) buckets)- O(n\lg k/lg n) time, O(n) space
.Note: Andersson & Nilsson (1997): a new sorting algorithm
6
.Probability theory
.prob density function f_A VS. prob distribution function F_A
.moment generating function s:E(e^{sA}) VS. prob generating func z:E(z^A)
.Erd\"os & Spencer (p18) 
 *\binom{n}{k} ~ n^ke^{-k^2/(2n)-k^3/(6n^2)}/k!*(1-o(1)) if n=o(n^{3/4})
.Bernoulli variable A_i = 1 with prob p
.binomial variable B = \sum_1^n A_i
			      \\plato
.Poisson trial A_i = 1 with prob p_i
 *H\"offding's Thm: \sum P_i is upper bounded by B(n,\sum P_i/n)
.geometric variable V: Prob(V=n) = p(1-p)^n \forall n \geq 0
.\Phi(x) (normal distribution F_x) is bounded by functions of \Psi(x)
(normal density f_x)
 *\Psi(x)(1/x-1/x^3) \leq 1-\Phi(x) \leq \Psi(x)/x
.Strong Law of large numbers: 
 *as n goes to infinity, any (S_n-\mu)/\sigma goes to normal distribution
 *Corollary: P(|S_n-\mu|>\sigma x) \leq 2\Psi(x)/x
.Markov, Chebyshev, and Chernoff bounds
 *continuous: P(A\geq X)\leq e^{-sx} E(e^{sA}) \forall s\geq 0
 *discrete: P(A\geq X)\leq z^{-x} E(z^x) \forall z\geq 1
.bound for binomial variable B
 *P(B \geq x)\leq e^{-x-\mu} \forall x \geq e^2 \mu ~ 6\mu
7
.quiz scope: recurrence, function, sorting, selection, and comparison trees
8
.Randomized algorithm
.Sampling
 *SampleRank(x, X) {
 * Let S be a random sample of X-{x} of size s
 * output 1+N/s*(rank(x,S)-1)
 *}
 *analysis: s Prob(y\in S, y<x) = s/N* rank(x,X)-1. So, it's binomial
 distribution
.Random subdivision: partition the segment of length n by s numbers k_1..k_s
 *(N-1)/s*\alpha l_n(n) < Prob(size of arbitrary one subdivision=n)<N^{-\alpha}
.RandSelect by Hoare is regarded as the "canonical selection algorithm"
 *RandSelect(i,B) {
 * random choose the i_1-th splitter b_{i_1}
 * if(i>i_1)RandSelect(i-i_1, {b_i|i>i_1})
 * else RandSelect(i, {b_i|i<i_1})
 *}
 *improved (bracket version) by Floyd & Rivest
  -Choose s=N^{2/3}\lg N, \delta < 3/\alpha,
  -and select in range (s+1)/(N+1)-\delta .. (s+1)/(N+1)+\delta
  -then with prob \geq 1-2N^{-\alpha} b_i is in this range
.RandSelect quicksort
 *\bar{T}(N) \leq 2\bar{T}(N_1) + N^{-\alpha}\bar{T}(N)*N+o(N)+N-1 ~
 \log(N!)
 *optimal average complexity
9
.Red-black trees
.Binary serach with & without errors
.Interpolation
.Unbounded search
.E=I+2n
 *n=#(internal nodes) (internal nodes hold true value)
 *I=\sum(internal length)
 *E=\sum(leaf length) (leaf holds nil)
.bucket sort B[\lfloor F^{-1}(x_1)\rfloor + 1]
.random search table: n random numbers in range [X_0, X_{n+1}]
 *search Y at E(k^*)
 *k is binomial B(n, (Y-X_0)/(X_{n+1}-X_0))
.interpolation search by Andrew Yao
.unbounded search: given 0000.......001111111...., find bound of 0 and 1
 *algorithm 1: doubling search range [1..2^k] k times, then binary search
 in [2^{k-1}, 2^k]; running time = 2 k = 2 \lg n
 *algorithm 2: doubling search range [1..2^{2^k}] k times, then do
 algorithm 1 in [2^{2^{k-1}}, 2^{2^k}], then binary search; time = 2\lg\lg
 n + \lg n
 *algorithm 3,4,.....
10
.Hash table
.load factor is defined as n/m = (#keys to be hashed)/(size of hash table)
.hashing algebraic function (in the last slide)
.assume simple uniform hashing
.2-universal hash family H: 
 *Prob(h(x)=h(y))\leq 1/m \forall x\neq y, random h \in H
 #H_1 = (ax+b) mod p mod m is 2-universal
 #pf: #conflicts = |{r=s mod m|r \neq s,0\leq r,s \leq p-1}| = p(p-1)/m.
 #So, Prob(conflict) = (p(p-1)/m)/(p(p-1)) = 1/m
11
.Amortized analysis: from potential theory in Physics and Economics
.Gray code: O(1) time to increase (bit time)
.accounting method
 #amortized analysis for MultiPop in stack of size s
 #real cost:  push=1, pop=1, MultiPop(k) = min(k,s)
 #new charge: push=2, pop=0, MultiPop(k) = 0
.potential function \Phi:{D_i|0\leq i \leq n}\rightarrow R
 *\Phi(0) is the minimum of \Phi(i)
 *amortized cost of operation i = A(c_i) 
  = c_i(true cost) + \Phi(D_i)-\Phi(D_{i-1});
 *then \sum A(c_i) \sum c_i \forall n
.amortized analysis for doubling array size when not affordable
 *potential function \Phi = 2*#elements - size
 *thrashing if repeatedly expanding & shrinking (contracting) the size of
 array by the same factor
.amortized analysis for "splay" tree
 *potential function \Phi(x) = \lfloor \lg |T(x)| \rfloor
12
.Secondary memory model (CLRS Ch.18)
.N=input, M=memory, B=block size, Z=output size
.n=N/B, m=M/B (memory blocks), z=Z/B
.buffer trees
.range search
.practical sorting (using blocks): 
 *complexity =\Theta(\frac{N\lg(N/B)}{B\lg(M/B)}) = \Theta(n\log_m n)
.practical permuting complexity = \Theta(min(N,n\log_m n)) 
 *N is the complexity of random access
 *pf: let T be #IO time, then (B!)^n (\binom{M}{B} N^2)^T \geq N!
.practical mergesort
 *N/M sorted sequences, each of size M
 *grab B items in each of the m sorted sequences 
 *find the smallest, collect them, store them in B units
 *grab new B items in where the B smallest items are grabbed
 *repeat
.practical bucket sort: \sqrt{m} samples
.practical search tree: B-tree
 *B/2 \leq non-root node degree < B-1
.buffer tree (Arge '95): 
 *lazy insertions, branch down only when B items are collected
 *amortized I/O time = O(1/B) per level per item
.interval tree: each node is an interval
.external interval tree: decrease fan-out from B to \sqrt{B}
 *\sqrt{B} slabs defines O(B) multislabs
.parallel disk model: P=#CPU, D=#disks
 *refer to work of Duke CS fellows
13
.Dynamic programming (CLRS Ch.15.0-15.2)
.matrix-chain multiplication
 *na\"ive cost = p_1(\sum_2^{n-1} p_i p_{i+1})
 *dynamic programming
  -momorize values in hash tables or arrays
  -make choice
 *draw computation table
  -work from the diagonal, forwarding to corner
.O(n^2) time finding the longest monotonically increasing subsequence in
a[1..n] 
.common subsequence of X={x_1,...,x_m} and Y={y_1,...,y_m}
 *optimal substructure observation
 *recursive formulation
 *a DP program
 *computation table: work from the borders to target
 *save arrows to produce a matched subsequence
.Huffman code tree:
 *given keys k_1 < k_2 < ... < k_n
 *given prob p_1, p_2, ..., p_n, for k's
 *given "dummy" key ranges: d_0 \leq k_1 \leq d_1 \leq k_2 \leq ... \leq k_n
 \leq d_n
 *given prob q_0, q_1, q_2, ..., q_n for d's
 *prob property: \sum_1^n p_i + \sum_0^n q_i = 1
 *goal: a binary search tree with minimum expect cost for search
  -E(cost) = \sum_1^n (depth(k_i)+1)p_i + \sum_0^n(depth(d_i)+1)q_i
 *DP yields \Theta(n^3) (and \Theta(n^2) for better design)
			     //the glue cost
14
.Greedy Algorithm
.Matroid: Let \frak{E} = set of objects and \frak{I} \subseteq
Powerset(\frac{E}). Requirements:
 *Empty set is in \frak{I}
 *If S \in \frak{I} is not maximal, then \exists x \in \frak{E}
 s.t. S\cup{x} \in \frak{I}
 #Spanning tree (Any spanning forest not maximal can be added a tree edge)
.Matroid intersection
 *Given I_1, I_2 two matroids, the goal is to find longest S \in I_1 \cap I_2
 #Maximal Matching is a matroid intersection problem
.Weighted matroid problem: each object of \frac{E} is associated with a
weighted value. 
 *Goal: find S \in I to both maximize size(S) = n and (wish to) maximize
 \sum_{x \in S}w(x)
 #Huffmann code revisited: greedy construction
.Depth-first Search (CLRS Ch.23)
.biconnectivity: all subgraphs either is single edge or has two
non-overlapping paths between any vertices
.proper ancesters: ancesters not self
		   //Bob Tarjan is a student? of Knuth
15
.Graph Theory
.For DFS tree, define low(v) = min({v}, {w|there's a path from v to w})
(vertices are numbered according to DFS order)
.Articulation Point: the intersection of each pair of biconneccted
components is at most a single node called the articulation point
 *If find articulation points -> find biconnected components from DFS tree
 *Root is an A.P. iff it has \geq 2 children
 *nonroot a is an A.P. iff there exists v in a's subtree s.t. low(v)\geq a
.For directed graph DFS, types of edges include DFS edges, backward (cycle)
edges, forward edges, and crossedges
.Kosaraju invented the Strong Components Algorithm
 *DFS search, renumber vertices by postorder (pop) order 
 *Reverse all edges
 *DFS on the edge-reversed graph, starting on the highest numbered vertices
 *Output all connected DFS trees
 *O(V+E) time
 *Proof of correctness: for any two vertices u, v with lca(u,v)= r, by DFS
 tree of the reversed graph there is a path from u to r and a path from v
 to r. Suppose there is no path from r to u. Then, since r is poped later
 than u, r is either an ancestor of u in the first DFS tree (contradiction)
 or r and u are in different subtrees (contradicts to the path from u to r,
 which should be used for the first DFS search). Similarly, there must be a
 path from v to r. QED
16
.Minimum Spanning Tree, Union-Find (CLRS Ch. 21, 23)
.cut: a cut "respects" an edge set E if no edge in E crosses the cut
.Prim's algorithm: greedily find min weight crossing the cut respecting
current subtree (like DFS)
 *need heap structure
.Kruskal's algorithm: greedily choose min weight edge s.t. no cycles are
induced. Stop when all nodes are connected (like BFS)
 *need Union-Find structure to merge tree. O(E \alpha(V)) time.
.Amortized analysis (by Tarjan) of path compression: \log^*V bound
		    //assessed = charged
 *lemma: Total rank in block j \leq 3/(2 B(j)) where B(j) is the # of
 blocks in block j
17
.Shortest Paths (CLRS 24.0-24.3, 25.2)
.Any subsequence of a shortest path is a shortest subpath
 *Proof: "surgery" or "cut-and-paste" method
.Dijkstra's algorithm: maintain S \subset V
 *If d(u) + w(adj(u),u) < d(adj(u)) then d(adj(u)) = d(u)+ w(adj(u),u)
.Ford-Bellman algorithm: maintain shortest-path tree with less than i edges
.All-pair: matrix solution d_{ij}^{m hops} = min(d_{ik}^{m-1 hops}+w(k,j))
 *(Change operation: min=>\sum, + =>*) = \sum d_{ik}^{m-1}*w_{kj}=D^{m-1}W
 *O(n^3 \log n)
.Floyd-Warshall: (Floyd from Stanford, Turing Award)
 *d_{ij}^k = min(d_{ij}^{k-1}, d_{ik}^{k-1} + d_{kj}^{k-1})
 *O(n^3)
18
.BFS: define level distance of any edge
.Dijkstra's algorithm is BFS if all weights are 1
.O(VE) matching algorithm: Find augmenting path, which is alternating edges
of mathced and unmatched vertices. (Aug)\xor(Current Match) = (New Match)
by BFS from any unmatched vertex
.Adams: for non-bipartite graph, "shrink the blossom" when odd cycle
discovered. Time bound O(n^4) => O(nm) => O(\sqrt{n} m)