Lectures in COMP 251--Winter 2020


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

Lecture 1 (Jan 7) General introduction. Definition of an algorithm. Examples of simple computer models: Turing model, RAM model, pointer based machines, oracles, comparison model. Uniformly bounded time (or: RAM model), 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 9) We covered all of chapter 2 and part of chapter 3 of CLR. Introduction to recurrences. Revisiting fast exponentiation briefly. 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 14) 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). Ham-sandwich and pancake theorems and halfspace counting. Scribed notes on divide-and-conquer (part II).
Lecture 4 (Jan 16) 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 show via 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. Scribed notes on divide-and-conquer (part III).
Lecture 5 (Jan 21) Euclid's algorithm. (Hard) exercise: Show that the bit complexity of gcd(n,m) is O(log n . log m). Dynamic programming (chapter 15 of CLR). Computing binomial coefficients. The partition problem. The rod-cutting example (CLR 15.1). Job scheduling. 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 23) Dynamic programming continued (and covered here). The traveling salesman problem. The knapsack problem. The longest common subsequence problem (CLR 15.4).
Lecture 7 (Jan 28) Dynamic programming continued (and covered here). The assignment problem. Optimal binary search trees (CLR 15.5). Matrix chains (CLR 15.2).
Lecture 8 (Jan 30) 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 9 (Feb 4) Midterm I.
Lecture 10 (Feb 6) 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. Bijection between ordered trees (forests) and binary trees via oldest child and next sibling pointers. Scribed notes: Intro to trees.
Lecture 11 (Feb 11) Continuing with trees (CLR 10.4 and CLR Appendix B5). Complete trees: implicit storage, height. 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 notes on trees by Henri Mertens.
Lecture 12 (Feb 13) Introduction to the ADT Dictionary. Scribed notes on dictionary, binary search trees. 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 18) Insert operation on red-black trees. Standard deletion is not covered in class. Lazy delete. Split and join in red-black trees. Exercise: In time $O(n)$, create a red-black tree from a sorted list either by making a complete binary search tree or a binary search tree of minimal height $\lfloor \log_2 n \rfloor$. Exercise: Convince yourself that the split operation can be implemented in O(log n) time. Scribed notes on red-black trees are available.
Lecture 14 (Feb 20) Augmented data structures (CLR 14). Examples:
  • (1) Data that participate in several data structures.
  • (2) Combining search trees and ordered linked lists.
  • (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. Augmented data structures: Scribed notes (skip the part about level linking).
Lecture 15 (Feb 25) Random binary search trees (CLR 12.4). Cartesian trees. Treaps. Analysis of the expected time of the main operations. Quicksort. Cartesian trees: Lecture notes.
Lecture 16 (Feb 27) 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. Priority queues: Notes by Henri Mertens.
Lecture 17 (Mar 10) Midterm II.
Lecture 18 (Mar 12) 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. This lecture was recorded and is available on myCourses.
Two-week corona virus interruption No lectures on March 17, 19, 24 and 26.
Lecture 19 (Mar 31) Entropy of an input source. Definition of entropy and Shannon's result on best possible compression ratios. Proof of Shannon's theorem (not part of the material for the exam). The Shannon-Fano code. Kraft's inequality (not part of the material for the exam). 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 (Apr 2) 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. Classification of edges. Detecting cycles. Euler tour.
Lecture 21 (Apr 7) Breadth first search (CLR 22.2). BFS tree. Detecting bipartite graphs. Video lecture on Breadth First Search in graphs [66MB, 20 minutes]. This is the first part of the lecture. Shortest path problem. CLR 24. Dijkstra's algorithm. Shortest path properties. Minimal spanning tree. CLR 23. Main properties. 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. Notes by Youri Tamitegami.
Lecture 22 (Apr 9) Directed acyclic graphs. Topological sorting. CLR 22.4. Activity (PERT) networks. Dags continued: NIM games. Strongly connected components in directed graphs. CLR 22.5. Video lecture on directed acyclic graphs. [248MB, 75 minutes].