Algorithms and data structures. Part 1.

Lecture 1. Complexity and computation models. Amortized costs (part 1)

Basic resources: memory and time. O-notation. Sample computation models: Turing machine, RAM machine. Average- and worst-case complexities. Example: sorting problem. Selection sort. Lower bounds via information theory. Decision trees. Lower bounds with decision trees model. Variable-size arrays: additive and multiplicative reallocation. Analyzing multiplicative reallocation strategy via Banker's method.

Lecture 2. Amortized costs (part 2)

Amortized costs more formally: potential, actual and reduced costs. Stacks and queues. Implementing a variable-size array via linked list. Simulating queue via a pair of stacks. Dynamic minimum problem in stacks and queues. Mutable and immutable data structures. Persistent data structures. Analyzing amortized cost of persistent data structures, "multiple futures" issue.

Lecture 3. Merge-Sort and Quick-Sort

Introduction to divide-and-conquer. Merge-Sort algorithm. Merging a pair of ordered lists. Complexity bound. K-way Merge-Sort in external memory. Inplace merge sort. An overview of Quick-Sort. Two methods for implementing Partition. What's a bad pivot? Randomized pivot selection. Average- and worst-case complexity of Quick-Sort. Average- and worst-case recursion depth. Eliminating tail recursion from Quick-Sort. Optimal merge tree problem. Huffman codes. Merging a pair of ordered lists of imbalanced sizes. Lower bounds via information theory. Binary search with galloping.

Lecture 4. Order Statistics. Heaps (part 1)

Selecting order statistics via randomized Quick-Sort. Linearity of expected running time. Approximate medias. Selecting k-th order statistic in worst-case linear time. Heap property for binary trees. Almost complete binary trees: vertex numbering and navigation. Binary heap. Sift-Up and Sift-Down procedures. Implementing Insert, Remove, and Find-Min operations. Make-Heap: turning array in a heap in linear time. Heap-Sort algorithm.

Lecture 5. Heaps (part 2)

k-ary heaps. How to choose k properly? Binomial, leftist, and skew heaps.

Lecture 6. Hashing

Hash function. Collision. Collision resolution methods: chaining, sequential probing, double hashing. Simple uniform hashing hypothesis, estimating the average chain length. Universal families of hash functions, estimating the average chain length. Building a universal family for integer keys. Perfect hash functions. Building a perfect hash function via universal families. Faulty set interface. Bloom filters. Estimating false positive probability. Faulty dictionary interface. Bloomier filters.

Lecture 7. Search Trees (part 1)

What is a search tree? Inserting and removing items. Inorder traversal. Red-black trees: definition and some basic facts. Inserting an item into a red-black tree. Splay-trees. Splay procedure: zig, zig-zig, and zig-zag steps. Impementing Insert, Remove, Merge, and Split procedures for splay trees via Splay.

Lecture 8. Search Trees (part 2)

Cartesian trees (treaps). Uniqueness of Cartesian tree for given distinct keys and priorities. Expected treap height is logarithmic. Merging and splitting treaps. Insertions and removals. Constructing a treap from a sorted sequence of keys in linear time.

Lecture 9. Search Trees (part 3). Disjoint set union

B+ trees: definition and some basic facts. Lookups, insertions, and removals for B+ trees. Disjoint set union data structure. Rank heuristic. Ranks are at most logarithmic. Randomized rank heuristic. Path compression heuristic. Amortized complexity (proof omitted).

Lecture 10. RMQ and LCA Problems

RMQ (range minimum query) and LCA (least common ancestor) problems. Reducing RMQ to LCA via Cartesian tree. Tarjan's offline LCA algorithm. Simplest approaches to online LCA problem: full and sparse answer tables. An approach of Farach-Colton and Bender: ±1-RMQ. Reducing LCA to ±1-RMQ via Euler tour.

Lecture 11. Data Structures for Geometric Search Problems

Location problem, stabbing problem. Interval trees. Reducing interval problems to 2D problems. Point location in a corridor. Priority search tree. Point location in a rectangle. X-wise segment tree with Y-ordered lists of points. Estimating complexity: O(n log n) construction time and O(log^2 n) query time. Reducing query time to O(log n). Simultaneous selection from a collection of ordered lists. Fractional cascading.

Lecture 12. Dynamic Connectivity in Undirected Graphs

Dynamic connectivity problem: edge insertions, edge removals, and connectivity queries. A special case of a forest. Euler tour trees: merging and splitting. Layered data structure, O(log^2 n) amortized time per operation.