- This syllabus is only tentative, and will be subject to some changes.
- Analysis Techniques: Amortized time, backward analysis.
- Design Techniques: Dynamization, persistent data structures, dynamic programming.
- Data structures: Fibonacci heaps, search trees, splay trees, treaps, universal and perfect hash tables, loglog N priority queues, dynamic trees.
- Suffix arrays.
- Applications: Minimum spanning trees, network flows, pattern matching, problems in computational geometry.
- Various other stuff: Will be determined as the semester proceeds.
Detailed Course Plan
|1||Amortized analysis: the credit method and the potential method. Simple examples: stack with multipop, dynamically expanding array. Binomial heaps. Binomial heaps with lazy melding.||Amortized analysis - examples using the credit method and the potential method: dynamically expanding and contracting array, binary counter with increment, binary counter with increment and reset. Discussion.|
|2||Fibonacci heaps. Applications: Dijkstra's shortest path algorithm; Fredman and Tarjan's MST algorithm.||A general framework for MST algorithms (the red and blue rules). Kruskal's algorithm and Prim's algorithm as special cases.|
|3||Splay trees (including split and join).|
|4||Dinitz's max-flow algorithm - dynamic trees implementation. Dynamic trees (splay tree implementation) - part 1.||Max-flow: review (definitions and Ford and Fulkerson's method). Dinitz's max-flow algorithm.|
Dynamic trees - part 2. Quicksort. Random search trees. Treaps
Randomized algorithm for finding a pair of points closest to each other among a given set of points in the plane. Backwards analysis yielding expected linear time complexity.
|Comparison based computation (decision trees): O(n log n) lower bound for element distinctness, upper and lower bound of ceil(3n/2)-2 for finding the maximum and minimum (simultaneously) in a set of n elements.|
Backwards analysis: backwards analysis of expected height.
Dynamic programming. Knuth's O(n^2) optimal search tree algorithm.
|Dynamization of static data structures (the logartithmic scheme).|
Perfect hashing based on universal hashing. Dynamic perfect hashing.
|Universal hashing: definitions and example. Application: element distinctness in linear expected time.|
|8||No Lectures, there are two consecutive recitations instead.||Dynamic programming.|
|9||String matching: Knuth, Morris, and Pratt's algorithm.||Backward Analysis.|
|10||Suffix arrays.||Static data structure supporting O(1) time LCA queries.|
History Independent Data Structures:
Weak and Strong history independence.
2-3 trees, Hashtables, Heaps, Lower bounds and safe memory allocation.
|Interval trees. Segment trees.|
|12||Persistent data structures. Example: making 2-3-4 B+ trees partially persistent. planar point location.||RMQ, Suffix Arrays, LCP, Suffix Trees.|
|13||log log N priority queue.||Range trees.|
|Red-black trees (including split and join).|
course_info.pdf 39782 Bytes