9. Table Doubling, Karp-Rabin

https://www.youtube.com/watch?v=BRO7mVIFt08

Lecture Notes: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec09.pdf


1. in hashing, suppose n is the number of keys and m is the number of slots in the hash table. We want m to similar size to n. But n may grow or shrink, so we need to grow and shrink table to get better performance (and rehash). When grow, double the size. When shrink, wait until n is m/4 and then decrease m by half.

Amortized cost, like paying rent $1500/month = $50/day

2. Karp-Rabin algorithm: rolling hash. Lots of common bits between two hash. Easy to append one bit and remove the first bit.

String Matching with Finite Automata

https://www.youtube.com/watch?v=M_XpGQyyqIQ

Notes:

1. Finite automata is a state machine. It has start and end state(s). A three letter pattern has four states (s0 to s3). Matched one more letter means state changes. If not match, it will go back to one of the appropriate state. ( Instead, in naive matching, if one letter does not match, it will go back to s0).

2. Finite automata is used to parse in compiler and implement regular expression.

3. State transition table. ( column is alphabet, row is states).

4. Matching time is O(N), preprocessing time depends on implementation.

Knuth-Morris-Pratt algorithm for String Matching

https://www.youtube.com/watch?v=kBW6oPaVjq0

Need a prefix table.

The preprocessing is very similar to string matching.
One is to match pattern to itself. The other is to match pattern to text.
Time complexity: O(m) + O(n)  ( O(m) for preprocessing and O(n) for matching).

computational complexity: P, NP, EXP, R

MIT opencouseware : https://www.youtube.com/user/MIT/search?query=algorithm

23. Computational Complexity

https://www.youtube.com/watch?v=moPtwq_cVH8

--------|---------|------------|-----------|------------------------>
<--p-->
<-----np------>
                 NP-CMP
<---------------exp----->
<------------------------- --------="" r="">

1. Tetris is NP-complete

2. Reduction: mapping a new problem A  to old problem B.