Lectures in CS252--Winter 2020


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

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, 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. 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. Exercise: where does $2^{n^2}$ fit into the complexity hierarchy: 1, log n, n , n^2, 2^n, n!, n^n?
Lecture 2 (Jan 9) We covered all of chapter 2 and part of chapter 3 of CLR. Introduction to recurrences. Fast exponentiation. The divide-and-conquer solution to Problem CLR4.7 (chip testing). 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). Recursion tree to explain the master theorem. Strassen matrix multiplication. Ham-sandwich and pancake theorems and halfspace counting. Exercise: Analyze T(n) = T(n/3) + T(2n/3) + n using the recursion tree. Exercise: How do you compute the complex product (a+bi)(c+di)? Exercise: What is the "big theta" order of the solution of T_n = T_(n/2) + log n? Assignment 1 handed out. Due January 21, 2020, 8:30am. Scribed notes on divide-and-conquer (part II).
Lecture 4 (Jan 16) Linear time selection: finding the k-th smallest by the algorithm of Blum, Floyd, Pratt, Rivest and Tarjan. O(n) complexity proof based on induction. Exercise: Look at the median-of-3 version of this algorithm and show, by using recursion trees, that its complexity is big theta of n log n. Linear expected time selection by Hoare's algorithm "FIND". The induction method illustrated on mergesort. Recurrence for binary search with binary and ternary oracles, and solution by induction for the ternary oracle. Exercise: For binary search using a binary comparison oracle, show that T(n) is not more than 2 + ceiling(log_2 n). And for a ternary comparison oracle, show by substitution or induction that T(n) is not more than the ceiling of \log_2 (n+1). Scribed notes on divide-and-conquer (part III).
Lecture 5 (Jan 21) Assignment 1 due. Handout of notes on FFT, the Fast Fourier Transform. Multiplying polynomials in time O(n log n). This is in CLR30.
Lecture 6 (Jan 23) Assignment 2 handed out. Due January 30, 2020, 8:30am. Dynamic programming. Computing binomial coefficients and partition numbers. Traveling salesman problem. Knapsack problem. Exercise: Modify the algorithm for the case that we have an unlimited supply of items of the given sizes. Job scheduling problem. Scribed notes on dynamic programming.
Lecture 7 (Jan 28) Longest common subsequence problem. Exercise: from the nxm matrix of lengths of longest common subsequences, determine in time O(n+m) a longest matching. Assignment problem. Matrix chains. Optimal binary search tree.
Lecture 8 (Jan 30) Assignment 2 due, 8:30am. Hand out course notes on lower bounds. See also CLR 9.1. Oracles. Viewing algorithms as decision trees. Proof of lower bound for worst-case complexity based on decision trees. Examples include sorting and searching. Lower bounds for board games. Merging two sorted arrays using finger lists.
Lecture 9 (Feb 4) Assignment 3 handed out. It is due on February 11 at 8:30am. Lower bounds via witnesses: finding the maximum. Lower bounds via adversaries. Guessing a password. Sorting via adversaries. Finding maximum and minimum. Finding the median. Finding the two largest elements.
Lecture 10 (Feb 6) Introductory remarks about ADTs (abstract data types). Lists. Chapter 11 of CLR: primitive ADTs such as stacks, queues, deques, and lists. We deviate only slightly from this chapter. For the notation for list operations, see chapter 1 of Data Structures and Network Algorithms (R.E. Tarjan, SIAM, Philadelphia, 1983). Scribed notes by Florestan Brunck: ADTs, lists, 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: 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 by Florestan Brunck: Intro to trees.
Lecture 11 (Feb 11) Assignment 3 due, 8:30am. Continuing with 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. Complete trees: implicit storage, height. Exercise: Generalize the navigation formulas seen in class for binary trees to k-ary trees. Counting binary trees (Catalan's formula). Representing and storing trees: binary trees require about 2n bits. Sections 11.3, 11.4, and 5.3 of CLR. Preorder, postorder, inorder and level order listings and traversals. Recursive and nonrecursive traversals. Practice exercise: Reconstruct an ordered tree in linear time from its preorder and postorder listings. Exercises: Write linear time algorithms to go between any of the $2n$-bit representations of binary trees, and a binary tree.
Lecture 12 (Feb 13) Midterm.
Lecture 13 (Feb 18) Introduction to the ADT Dictionary. Definition of a binary search tree. Binary search trees: chapter 13 of CLR. Standard operations on binary search trees, all taking time O(h), where h is the height. Generic tree sort. Scribed notes by Florestan Brunck: Dictionary, binary search tree. Definition of red-black trees.
Lecture 14 (Feb 20) Assignment 4 handed out, due February 27, 9:55am. Red-black trees (chapter 14). See also here. Red-black trees as 2-3-4 trees. 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. Augmented data structures. This is nicely described in CLR (chapter 15). Examples:
  • (1) Data that participate in several data structures.
  • (2) Combining search trees and ordered linked lists.
Lecture 15 (Feb 25) Augmented data structures continued (CLR 15). Examples:
  • (3) Order statistics trees. Operations rank and selection.
  • (4) Interval trees. VLSI chip layout application. Sweepline paradigm.
  • (5) Level linking in red-black trees. Exercise: Explain how to maintain the level links during a rotation operation.
  • (6) k-d-trees. Range search, partial match search. Quadtrees. The multidimensional search trees are not in CLR.
Scribed notes on augmented data structures.
Lecture 16 (Feb 27) Assignment 4 due, 9:55am. [Can also be submitted electronically to Konrad Anand.] Random binary search trees. Cartesian trees. Treaps. Analysis of the expected time of the main operations. Quicksort. Lecture notes.
Lecture 17 (Mar 10) Assignment 5 handed out, due March 17, 9:55am. Priority queues (as abstract data types). Uses, such as in discrete event simulation and operating systems. Binary heaps (chapter 7 of CLR): superficial coverage. Tournament trees (handout). Tournament sort.
Lecture 18 (Mar 12) Amortization (chapter 18 of CLR). Potential functions. Simple examples: stack with multipop (not done this year), dynamic tables, lazy delete in red-black trees, binary addition, weight-balanced search trees (not done this year), Fibonacci heaps. Scribed notes on amortized analysis, courtesy of Ariel Goodwin and Malcolm Sutcliffe.
Corona virus interruption No lectures on March 17, 19, 24 and 26.
Lecture 19 (Mar 31) Assignment 5 due today, March 31, at 10am. Submit to myCourses. Introduction to compression and coding. Fixed and variable width codes. Prefix codes. Most of this lecture is covered by section 17.3 of CLR. Definition of entropy and Shannon's result on best possible compression ratios. Huffman trees. Huffman code. An O(n log n) algorithm for finding the Huffman tree. Definition of a greedy algorithm. Data structures for Huffman coding. Merging sorted lists by the greedy method. Generating a random integer.
Lecture 20 (Apr 2) Entropy of an input source. Kraft's inequality. Proof of Shannon's theorem. The Shannon-Fano code. 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 21 (Apr 7) Introduction to graphs: notation, definitions, adjacency matrix, adjacency lists. Graph traversals as the fundamental procedures for most graph algorithms: depth first search (sections 23.1, 23.2 of CLR). DFS forest and DFS properties. Classification of edges. Detecting cycles. Euler tour.
Lecture 22 (Apr 9) Breadth first search (section 23.3 of CLR). BFS tree. Detecting bipartite graphs. Shortest path problem. Dijkstra's algorithm. Shortest path properties. See here. Minimal spanning tree. Main properties. Greedy approach for the MST: the Prim-Dijkstra algorithm. Application in hierarchical clustering. Kruskal's algorithm. A two-approximation for the traveling salesman problem (section 37.2 of CLR). Notes on MST and shortest paths by Youri Tamitegama.