xxsang

1. variants
	1. 1-1
	2. 1-all
	3. all pairs
	4. euclidean weights
2. Shortest Path Properties
	1. Shortest path tree solution: shortest path from s to all other vertex
		1. distTo[v]: length of shortest path from s to v
		2. edgeTo[v]: last edge on shortest path from s to v
	2. Edge relaxation: update the shortest distance and shortest path to w

xxsang

1. Maxflow
	1. Mincut: a cut is a partition of vertices to A and B, the capcity is the sum of the capacities of the edges from A to B (other way don’t count), find a cut of minimum capacity
	2. Maxflow: a flow is an assignment of values to the edges <= capacity, local equilibrium so inflow=outflow at every vertex, find a flow of maximum value (the value of a flow is the inflow at tartget t)
	3. dual problem (once solved one, solved another)
2. Ford-Fulkerson Algorithm
	1. Start with flow 0
	2. Find undirected augumenting path (any path that can increase flow)
		1. can increase flow on forward edges (not full)
		2. can decrease flow on backward edge (not empty)
	3. Terminate when no more augmenting paths can be found

xxsang

1. String Processing
	1. ASCII 7 bit, 128
	2. Unicode 16 bits
	3. Program language specific
2. Key-index counting
	1. Lower bound: any algorithm with compares NlogN
	2. Can use key as array index
		1. Count frequencies of each letter using key as index
		2. compute frequency cumulates which specify destinations
		3. Access cumulates using key as index to move items

xxsang

1. Tries:Data structure by searching string keys
	1. R-way tries, even faster than red-black BST and hashing
	2. Store characters in nodes
	3. Store values in nodes corresponding to last characters in keys
	4. Search until the ending character with a non-null value
	5. Insertion: create link until the last character and set value in that node
	6. Node: a value +references to R nodes
	7. Search hit: all L characters, search miss: typical sublinear, space: R null links at each leaf
	8. Spell check: 26-way trie
	9. deletion: set the value to null

xxsang

1. Find Pattern in Text
2. Brute-force
	1. Check for pattern starting at each text position
	2. Worst case ~MN
	3. Need backup of the text to go backwards
3. Knuth-Morris-Pratt
	1. Don’t need to back up text pointer
	2. DFA
		1. Deterministic Finite State Automaton
		2. Exactly one transition for each possibility

xxsang

1. RE
	1. Find specified set of string in text
	2. A notation to specify a set of strings
	3. AB*A: zero or more occurance of B
	4. wildcard: .
	5. character class [A-Z]
	6. At least 1 A(BC)+DE
	7. exactly k [0-9]{5}-[0-9]{4}
2. NFAs
	1. Kleene’s algorithm: for any RE there is an DFA and vice versa

xxsang

1. Data Compression
	1. Lossless compression, compress and expand (reconstructs original bitstream)
		1. 50-70% compression ration for Natural language
	2. k-bit code support alphabet of size 2^bit
	3. No universal data compression algorithms
	4. Undecidability: there is no way to find the best way to compress a file
	5. Compression Ration = (result)/(original)
2. Run-length coding
	1. Repeated bits can be stored as counts
	2. Applications: JPEG

xxsang

1. Reductions
	1. Problem-solving models
	2. Desiderata
		1. classify problems according to computational requirements
		2. linear, linearithmic, quadratic,…, exponential
	3. Problem X reduces to problem Y if we can use an algorithm that solves Y to help solve X
	4. Cost of X = total cost of Y + cost of reduction
2. Design Algorithms
	1. Convex hull (Graham scan) can be reduced to sorting
3. Establishing Lower Bounds

xxsang

1. Brewer’s Problem
	1. Linear Programming: problem-solving model for optimal allocation of scarce resources
	2. min or max objective function, subject to the constraints
	3. Formulate the problem
	4. Feasible region is a convex polygon
	5. The objective function is a line
	6. Optimal solution only happens at extreme points
	7. Standard form linear program
		1. Maximize linear objective function of n nonnegative variables, subject to m linear equations
		2. Add slack variable to convert each inequality to an equality

xxsang

1. Intractability
	1. DFA: store input, read tape, finite symbols
	2. TM: store input/output and intermediate results, read and write and move in both directions
	3. TM is just a hypothetic machine
	4. TM is a simple and universal model of computation
	5. No more powerful computational machine than TM
	6. Efficient: running time is polynomial aN^b for all inputs
	7. A problem is intractable if it cannot be solved in polnomial time
		1. Given a constant-size program, does it halt in at most k steps
		2. Given N-by-N checker board position, can the first player force a win?