Lectures in CS610--Winter 2014

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

Lecture 1 (Jan 6) General introduction. Definition of an algorithm. Examples of simple computer models: Turing model, RAM model, pointer based machines, comparison model. Uniformly bounded time, bit model of computation (or: logarithmic model). Landau symbols: O, Omega, Theta, small o, small omega. Polynomial versus exponential time classes. Chapter 1 in CLR. The Fibonacci example: introduce recursion, dynamic programming, and fast exponentiation. The Russian peasant method. Check here for some notes by David Eppstein.
Lecture 2 (Jan 8) We covered all of chapter 2 and part of chapter 3 of CLR. Some discussion of complexity classes. Introduction to recurrences. Solutions of simple recurrences. Binary search. Mergesort. Recursive solution for convex hulls in the plane. Divide-and-conquer (Karatsuba) multiplication. Master theorem. Recursion tree to explain the master theorem.
Lecture 3 (Jan 13) The chip testing problem. Ulam's problem (finding an integer with an incorrect oracle). Strassen matrix multiplication. Euclid's algorithm. Hand out assignment 1, due January 22, 2014.
Lecture 4 (Jan 15) Solving recurrences by induction: mergesort. Linear worst-case algorithm for finding the k-th smallest element (the selection problem).
Lecture 5 (Jan 20) Lower bounds via decision trees. Proofs of lower bounds for average and worst-case time based on decision trees (take notes). Part of the material is in section 9.1. Examples include sorting, searching, and Mastermind. The reduction method: lower bound of n log n for finding the convex hull in the plane.
Lecture 6 (Jan 22) Lower bounds via witnesses and adversaries: finding the maximum, finding maximum and minimum. Finding the median. Merging sorted sets by using finger lists. Hand out assignment 2, due February 3, 2014.
Lecture 7 (Jan 27) Introductory remarks about ADTs (abstract data types). Lists. Chapter 11 of CLR: primitive data structures such as stacks, queues, deques, and lists. We deviate only slightly from this chapter. For the notation for list operations, chapter 1 of Data Structures and Network Algorithms (R.E. Tarjan, SIAM, Philadelphia, 1983). Classification and use of linked lists. Introduction to trees: free trees, rooted trees, ordered trees, position trees, binary trees. Counting binary trees: Catalan's formula. Coding of binary trees.
Lecture 8 (Jan 29) Preorder, postorder, inorder traversals and representations. Correspondence between forests of ordered trees and binary trees. Correspondence between ordered trees on n nodes and binary trees on n-1 nodes. Complete binary trees: implementation, path properties, height. Heavy and light edge decomposition of a tree. Finding the least common ancestor in O(log n) time given the heavy/light edge decomposition.
Lecture 9 (Feb 3) Handout on various algorithms for the least-common-ancestor (LCA) and range-min query (RMQ) problems. Hand out assignment 3, due February 12, 2014.
Lecture 10 (Feb 5) Introduction to the ADT Dictionary. Cartesian trees with as special cases, binary search tree, treap, and random binary search tree. Binary search trees: chapter 13 of CLR. Standard operations, all taking time O(h). Searching with an oracle. Inorder traversal, insertion sort. Treap operations. Analysis of expected depth of the j-th ranked node in a treap.
Lecture 11 (Feb 10) Course notes on Cartesian trees and treaps handed out. Analysis of delete, insert, and join in a treap. Definition of a pagoda. Analysis of quicksort. Definition of red-black trees. Main properties of red-black trees.
Lecture 12 (Feb 12) Assignment 3 due. Discussion of the main operations on red-black trees: insert, delete, join, split. Definition of AVL tree, 2-3 tree. Hand out assignment 4, due February 24, 2014.
Lecture 13 (Feb 17) Augmented data structures. This is nicely described in CLR (chapter 15). Examples:
  • (1) Combining search trees and ordered linked lists.
  • (2) Order statistics trees. Operations rank and selection.
  • (3) Interval trees. VLSI chip layout application. Sweepline paradigm.
  • (4) Browsing operation. Level-linked red-black trees.
  • (5) Combining search trees and heaps.
Lecture 14 (Feb 19) Introduction to amortized analysis. Potential functions. Simple examples: stack with multipop, dynamic tables, lazy delete in red-black trees, binary addition.
Lecture 15 (Feb 24) Assignment 4 due. Potential functions continued. Weight-balanced search trees (handout). Splay trees (handout). Hand out assignment 5, due March 10, 2014.
Lecture 16 (Feb 26) Splay trees (continuation). Priority queues. Tournament trees (handout pending). Binary heaps (chapter 7 of CLR). Heapsort. Additional binary heap operations. k-ary heaps (determining best k). Pointer-based implementation of binary heaps.
Lecture 17 (Mar 10) Assignment 5 due. Binomial heaps. Fibonacci heaps. Hand out assignment 6, due March 19, 2014.
Lecture 18 (Mar 12) Fibonacci heaps, continued. Disjoint set data structures: chapter 22 of Cormen.
Lecture 19 (Mar 17) Introduction to graphs. Depth-first search.
Lecture 20 (Mar 19) Assignment 6 due. Depth-first search, continued. Finding cycles. Euler tours. Breadth-first search. Detecting bipartite graphs. Hand out assignment 7, due March 26, 2014.
Lecture 21 (Mar 21) Shortest path properties. Shortest path problem. Dijkstra's algorithm. Minimal spanning tree. Prim-Dijkstra method. Brief mention of Kruskal's method.
Lecture 22 (Mar 24) Directed acyclic graphs. Topological sorting. NIM games. PERT networks. Strongly connected components in directed graphs.
Lecture 23 (Mar 26) Assignment 7 due. All-pairs shortest path problem. Floyd-Warshall algorithm (dynamic programming). Bushfire algorithm. Transitive closure via strongly connected component decomposition. Transitive closure by matrix multiplication.
Lecture 24 (Mar 31) Hand out assignment 8, due April 2, 2014. Introduction to matchings. Stable matchings. The Gale-Shapley algorithm. 1.5-Approximation for the traveling salesman tour via maximal weighted matchings and Christofides's algorithm. Maximum bipartite weighted matching / the assignment problem: introduction.
Lecture 25 (Apr 2) Assignment 8 due. Pattern matching: Karp-Rabin algorithm, Knuth-Morris-Pratt algorithm.