Lectures in CS252--Winter 2016


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

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, web pages from 1997. Landau symbols: O, Omega, Theta, small o, small omega. Examples of many complexity classes (linear, quadratic, polynomial, exponential). The Fibonacci example: introduce recursion, iteration, and fast exponentiation. Check here for some notes by David Eppstein.
Lecture 2 (Jan 13) We covered all of chapter 2 and part of chapter 3 of CLR. Fast exponentiation. Introduction to recurrences. The divide-and-conquer solution to Problem 4.7 (chip testing). Divide-and-conquer (Karatsuba) multiplication. Solution of the recurrence for binary search.
Lecture 3 (Jan 15) Recurrences for binary search, mergesort, convex hulls. The master theorem (statement only). Recursion tree to explain the master theorem. Strassen matrix multiplication. Euclid's algorithm. Assignment 1 handed out. Due January 27, 2016, 10am.
Lecture 4 (Jan 20) The induction method: Simple examples: Binary search with two different oracles. Mergesort. Linear time selection: finding the k-th smallest by the algorithm of Blum, Floyd, Pratt, Rivest and Tarjan. Linear expected time selection by Hoare's algorithm "FIND".
Lecture 5 (Jan 22) Dynamic programming. Computing binomial coefficients and partition numbers. Traveling salesman problem. Matrix chains.
Lecture 6 (Jan 27) Dynamic programming, continued. Knapsack problem. Assignment problem. Longest common subsequence problem. Optimal binary search tree. Assignment 2 handed out. Due February 5 2016, 10am.
Lecture 7 (Jan 29) Lower bounds via decision trees. Proofs of lower bounds for worst-case time based on decision trees. Part of the material is in section 9.1, and part is covered in the 1997 lecture notes. Examples include sorting, searching, and board games. Merging two sorted arrays using finger lists.
Lecture 8 (Feb 3) Lower bounds via witnesses: finding the maximum. Lower bounds via adversaries. Finding maximum and minimum. 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 another account, see the 1997 class notes, or, for the notation for list operations, chapter 1 of Data Structures and Network Algorithms (R.E. Tarjan, SIAM, Philadelphia, 1983).
Lecture 9 (Feb 5) 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, complete k-ary trees. Bijection between ordered trees (forests) and binary trees via oldest child and next sibling pointers. 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. 1997 class notes. Sections 11.3, 11.4, and 5.3 of CLR. Assignment 3 handed out. Due February 17, 2016.
Lecture 10 (Feb 10) Preorder, postorder, inorder and level order listings and traversals. Recursive and nonrecursive traversals. Stackless traversal if parent pointers are available. Complete trees: implicit storage, height. 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.
Lecture 11 (Feb 12) Introduction to balanced search trees (see here). Red-black trees (chapter 14). See also here. Deletion is not covered in class. Definition of AVL and 2-3 trees. Red-black trees as 2-3-4 trees. Check also the 1997 class notes for this.
Lecture 12 (Feb 17) Assignment 3 due. Split and join in red-black trees. Application to list implementations (concatenate and sublist in O(log n) time). Definition of k-d trees, range search, partial match search. The multidimensional search trees are not in CLR, but there are a few indicators near the end of topic 10 of the 1997 class notes. Definition of BSP (binary space partition) trees. Painter's algorithm. Quadtrees. Ham-sandwich theorem and halfspace counting.
Lecture 13 (Feb 19) Midterm.
Lecture 14 (Feb 24) Brief discussion of the midterm. Augmented data structures. This is nicely described in CLR (chapter 15), and to some extent in topic 20 of the old class notes. 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.
  • (4) Interval trees. VLSI chip layout application. Sweepline paradigm.
  • (5) Level linking in red-black trees.
Lecture 15 (Feb 26) Assignment 4 handed out. Due March 11, 2016. Random binary search trees. Cartesian trees. Treaps. Analysis of the expected time of the main operations. Quicksort. Priority queues (as abstract data types). Uses, such as in discrete event simulation and operating systems.
Lecture 16 (Mar 9) Binary heaps (chapter 7 of CLR): superficial coverage. k-ary heaps (determining best k). Heapsort. Additional binary heap operations. Introduction to compression and coding. Fixed and variable width codes. Prefix codes. Huffman trees. Huffman code. Most of this lecture is covered by section 17.3 of CLR. For a few additional applications, check here and here. Definition of entropy and Shannon's result on best possible compression ratios. Hu-Tucker algorithm for constructing the Huffman tree. Definition of a greedy algorithm. Merging sorted lists by the greedy method. Optimal way of generating random integers.
Lecture 17 (Mar 11) Assignment 5 handed out. Due March 21, 2016. Entropy of an input source. Proof of Shannon's theorem. Kraft's inequality. Lempel-Ziv compression. 1997 class notes on Lempel-Ziv coding. Data structures for strings and for compression. Digital search tree.
Lecture 18 (Mar 16) Tries, PATRICIA trees, digital search trees. Suffix tries, suffix trees, suffix arrays. String searching in a large file. See here.
Lecture 19 (Mar 18) Pattern matching. The Rabin-Karp method. The Knuth-Morris-Pratt (KMP) method. Direct hashing.
Lecture 20 (Mar 21) Assignment 6 handed out. Due March 30, 2016, 10am. Hashing with chaining. Simple hash functions. Hashing: Uses, examples. Universal hashing. Perfect hashing with two layers of hash functions. Remarks on load balancing and the power of two. Cuckoo hashing. Discussion of rehashing. The material in this section roughly corresponds to chapter 11 of Cormen et al.
Lecture 21 (Mar 23) 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.
Lecture 22 (Mar 24) Classification of edges. Detecting cycles. Euler tour. Breadth first search (section 23.3 of CLR). BFS tree.
Lecture 23 (Mar 30) Detecting bipartite graphs. Shortest path problem. Dijkstra's algorithm. Shortest path properties. See here. Minimal spanning tree. Main properties. Greedy approaches for the MST: Prim-Dijkstra, Kruskal, Boruvka. Application in clustering.
Lecture 24 (Apr 11) Minimal spanning trees continued. See here. A two-approximation for the traveling salesman problem (section 37.2). The all-pairs shortest path algorithm of Floyd and Warshall. Transitive closure of a graph.
Lecture 25 (Apr 13) Directed acyclic graphs. Topological sorting. Activity (PERT) networks. See here. Dags continued: NIM games. Strongly connected components in directed graphs. Introduction to matching. The stable matching algorithm of Gale and Shapley.
Lecture 26 (Apr 15) Fast Fourier Transform. Multiplying polynomials in time O(n log n).