- 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

</TBODY></TABLE>Week | Lecture | Tutorial | ||||

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. | ||||

5 | 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. | ||||

6 | 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). | ||||

7 | 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. | ||||

11 | 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. | ||||

14 |
| Red-black trees (including split and join). |

course_info.pdf 39782 Bytes