Lectures in CS251--Winter 2019


The schedule may be updated from time to time, as we progress. CLR refers to Cormen, Leiserson, Rivest and Stein.

-->
Lecture 1 (Jan 8) General introduction. Definition of an algorithm. Examples of simple computer models: Turing model, RAM model, pointer based machines, oracles, comparison model. Uniformly bounded time, bit model of computation (or: logarithmic model). Definition and examples of an oracle. Chapter 1 in CLR. The Fibonacci example: introduce recursion, iteration, and fast exponentiation. Fast exponentiation. Check here for some notes by David Eppstein. Landau symbols: O, Omega, Theta, small o, small omega. Examples of many complexity classes (linear, quadratic, polynomial, exponential). Scribed notes on Landau symbols.
Lecture 2 (Jan 10) We covered all of chapter 2 and part of chapter 3 of CLR. Introduction to recurrences. The divide-and-conquer solution to Problem CLR 4.5 (chip testing). Exercise: Show that our chip testing algorithm takes only O(n) time even if n is not a power of two. Divide-and-conquer (Karatsuba) multiplication. Mergesort, convex hulls in the plane. Exercise: Describe in algorithmic form the linear time upper hull merge algorithm described in class. Scribed notes on divide-and-conquer (part I).
Lecture 3 (Jan 15) The master theorem (statement only: CLR 4.5, but not CLR 4.6). Recursion tree to explain the master theorem (CLR 4.4). Brief mention of the substitution method (CLR 4.3). Strassen matrix multiplication (CLR 4.2). Euclid's algorithm. (Hard) exercise: Show that the bit complexity of gcd(n,m) is O(log n . log m). Ham-sandwich and pancake theorems and halfspace counting. Scribed notes on divide-and-conquer (part II).
Lecture 4 (Jan 17) Linear time selection (chapter 9 of CLR): finding the k-th smallest by the algorithm of Blum, Floyd, Pratt, Rivest and Tarjan (CLR 9.3). We briefly looked at the median-of-3 version of this algorithm and showed, by using recursion trees, that its complexity is big theta of n log n. Linear expected time selection by Hoare's algorithm "FIND" (CLR 9.2). Recurrence for binary search with binary and ternary oracles, and solution by induction for the ternary oracle. Exercise: For binary search using a binary oracle, show that T(n) is not more than 2 + ceiling(log_2 n). Scribed notes on divide-and-conquer (part III).
Lecture 5 (Jan 22) The induction method illustrated on mergesort (see scribed notes). Ulam's problem (not included in the scribed notes or CLR). Dynamic programming (chapter 15 of CLR). The rod-cutting example (CLR 15.1). Computing binomial coefficients. Note: All the material covered in class on the topic of dynamic programming (three lectures worth), the rod-cutting example excepted, has been scribed.
Lecture 6 (Jan 24) Dynamic programming continued (and covered here). Computing binomial coefficients. The partition problem. The traveling salesman problem. The knapsack problem.
Lecture 7 (Jan 29) Dynamic programming continued (and covered here). Assignment problem. Longest common subsequence problem (CLR 15.4). Optimal binary search tree (CLR 15.5). Matrix chains (CLR 15.2).
Lecture 8 (Jan 31) Lower bounds (covered here). Oracles. Lower bounds via decision trees (CLR 8.1). Examples include sorting and searching. Lower bounds for board games. Merging two sorted arrays using finger lists.
Lecture 10 (Feb 7) Introductory remarks about ADTs (abstract data types). Elementary data structures such as lists, stacks and queues (CLR 10). We deviate only slightly from this chapter. For another account, see the scribed notes on lists and stacks. Classification and use of linked lists, including representations of large integers and polynomials, and free space lists. Uses of stacks and queues in recursions and as scratchpads for organizing future work. Introduction to trees (CLR 10.4 and CLR Appendix B5): free trees, ordered trees, position trees, binary trees, complete k-ary trees. Height of complete k-ary tree. Bijection between ordered trees (forests) and binary trees via oldest child and next sibling pointers.
Lecture 11 (Feb 12) Continuing with trees (CLR 10.4 and CLR Appendix B5). Complete trees: implicit storage. Exercise: Generalize the navigation formulas seen in class for binary trees to k-ary trees. Depth, height, external nodes, leaves, preorder numbers, postorder numbers. Relationship between number of leaves and number of internal nodes with two children in a binary tree. Counting binary trees (Catalan's formula--no proof). Representing and storing trees: binary trees require about 2n bits. Preorder, postorder, inorder and level order listings and traversals. Recursive and nonrecursive traversals. Stackless traversal if parent pointers are available. Expression trees, infix, postfix (reverse Polish), and prefix (Polish) representation. Exercises: Write linear time algorithms to go between any of the linear representations of binary trees, and a binary tree. Scribed scribbles by Henri Mertens.
Lecture 12 (Feb 14) Introduction to the ADT Dictionary. Binary search trees (CLR 12). Standard operations on binary search trees (CLR 12.2, CLR 12.3), all taking time O(h), where h is the height. Generic tree sort. Red-black trees (CLR 13). See also here. Red-black trees as 2-3-4 trees.
Lecture 13 (Feb 19) Insert operation on red-black trees. Standard deletion is not covered in class. Lazy delete. Split and join in red-black trees. Application to list implementations (concatenate and sublist in O(log n) time). Exercise: Convince yourself that the split operation can be implemented in O(log n) time. Scribed notes on red-black trees are available. Augmented data structures (CLR 14). Examples:
  • (1) Data that participate in several data structures.
  • (2) Combining search trees and ordered linked lists.
Lecture 14 (Feb 21) Augmented data structures (CLR 14). Examples:
  • (3) Order statistics trees. Operations rank and selection. CLR 14.1.
  • (4) Interval trees. VLSI chip layout application. Sweepline paradigm. CLR 14.3.
  • (5) k-d-trees. Range search, partial match search. Quadtrees.
  • (6) Binary space partition trees.
Lecture 15 (Feb 26) Random binary search trees (CLR 12.4). Cartesian trees. Treaps. Analysis of the expected time of the main operations. Quicksort. Lecture notes in PDF format courtesy of students Kaylee Kutschera, Pavel Kondratyev and Ralph Sarkis.
Lecture 16 (Feb 28) Priority queues (as abstract data types). CLR 6. Uses, such as in discrete event simulation and operating systems. Binary heaps (CLR 6). Tournament trees. Tournament sort.
Lecture 18 (Mar 14) Introduction to compression and coding. Fixed and variable width codes. Prefix codes. Most of this lecture is covered by CLR 16.3. Huffman trees. Huffman code. Huffman tree. Definition of a greedy algorithm. Data structures for Huffman coding. Merging sorted lists by the greedy method.
Lecture 19 (Mar 19) Entropy of an input source. Definition of entropy and Shannon's result on best possible compression ratios. Proof of Shannon's theorem. The Shannon-Fano code. Kraft's inequality. Lecture notes in PDF format courtesy of 2017 students Adel Magra, Emma Gouné and Irène Woo. Lempel-Ziv compression. Data structures for Lempel-Ziv compression. Digital search tree.
Lecture 20 (Mar 21) Data structures for strings and compression. Tries, PATRICIA trees, digital search trees. Suffix tries, suffix trees, suffix arrays. The Rabin-Karp pattern matching algorithm and introductory notions on pattern matching.
Lecture 21 (Mar 26) Introduction to graphs: notation, definitions, adjacency matrix, adjacency lists. Graph traversals as the fundamental procedures for most graph algorithms: depth first search (CLR 22.1, CLR 22.3). DFS forest and DFS properties.
Lecture 22 (Mar 28) Classification of edges. Detecting cycles. Euler tour. Breadth first search (CLR 22.2). BFS tree. Detecting bipartite graphs.
Lecture 23 (Apr 2) Shortest path problem. CLR 24. Dijkstra's algorithm. Shortest path properties. Minimal spanning tree. CLR 23. Main properties.
Lecture 24 (Apr 4) Minimal spanning trees continued. CLR 23. Greedy approach for the MST: the Prim-Dijkstra algorithm. A two-approximation for the traveling salesman problem (CLR 35.2). Kruskal's algorithm. Application in clustering. The all-pairs shortest path algorithm of Floyd and Warshall. CLR 25.1, 25.2.
Lecture 25 (Apr 9) Flow networks (CLR 26.1). The Ford-Fulkerson method (CLR 26.2), including the Edmonds-Karp algorithm.
Lecture 26 (Apr 11) Directed acyclic graphs. Topological sorting. CLR 22.4. Activity (PERT) networks. Dags continued: NIM games. Strongly connected components in directed graphs. CLR 22.5.