|
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 algorithm, abstract data types, data structures. 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, web pages from 1997. 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. Summation methods (chapter 3 of CLR). The divide-and-conquer solution to Problem 4.7 (VLSI chip testing) of Cormen, Leiserson and Rivest. Binary search. Mergesort. Divide-and-conquer (Karatsuba) multiplication (problem 32.1 of CLR). Some discussion of complexity classes. |
| Lecture 3 (Jan 13) | Introduction to recurrences. Solutions of simple recurrences. Recursion tree. The master theorem. Solving recurrences by induction. Mergesort example worked out. Euclid's algorithm. Strassen matrix multiplication. Ulam's problem (finding an integer with an incorrect oracle). |
| Lecture 4 (Jan 15) | Selection: chapter 10 of CLR. We cover the linear worst-case algorithm in its entirety. Hoare's linear expected time selection algorithm. Assignment 1 handed out: due January 27, 2:30pm. |
| Lecture 5 (Jan 27) | Assignment 1 due. Lower bounds via decision trees. Part of the material is in section 9.1, and part is covered in the 1997 lecture notes. Proofs of lower bounds for average and worst-case time based on decision trees (take notes). Merging sorted sets by using fingers (take notes). |
| Lecture 6 (Jan 29) |
Not done this year: Lower bounds via witnesses and adversaries.
The reduction method.
Review of the solutions of assignment 1. 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 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). Classification and use of linked lists. |
| Lecture 7 (Jan 30) | Examples of list ADTs: polynomial ADT, large integer ADT, free space list ADT (forgotten: please look up), window manager ADT, Bezier curves example, triangulation example. Uses of stacks and queues in recursions and as scratchpads for organizing futrure work. Postfix expressions evaluated by stacks. A simple example of graph traversal with a stack. Basic properties of trees: free trees, ordered trees, position trees, binary trees. Counting trees. 1997 class notes. Sections 11.3, 11.4, and 5.3 of CLR. Representing and storing trees. |
| Lecture 8 (Feb 3) | Assignment 2 handed out: due February 10, 2:30pm. Complete trees: storage, height. Traversals: Preorder, postorder, inorder, level order. Traversals with/without a stack. Threaded binary trees. |
| Lecture 9 (Feb 5) | Introduction to dictionaries. Tries and related search trees adapted for strings: PATRICIA (compacted) tries, suffix tries, suffix trees, suffix arrays. See here. |
| Lecture 10 (Feb 6) | Binary search trees: chapter 13 of CLR. Check also the 1997 class notes for this. View of a binary search tree as a sorted linked list (augmented data structure). Random binary search trees. Quicksort (chapter 8 of CLR, except that our expected time analysis is shorter). |
| Lecture 11 (Feb 10) | Assignment 2 is due. Introduction to balanced search trees (see here). Red-black trees (chapter 14). See also here. Definition of AVL tree, 2-3 tree. |
| Lecture 12 (Feb 12) |
Augmented data structures.
This is nicely described in CLR (chapter 15),
and to some extent in
topic 20 of the 1997 class notes.
Examples:
|
| Midterm (Feb 13) | As practice, attempt questions 1, 2, 3, 4, 6 and 7 here. Don't immediately look at the solutions. Note: closed book, 90 minutes, no calculators, cell phones or other electronic devices. |
| Lecture 13 (Feb 17) | Hand out assignment 3, due Tuesday, March 3, 2:30pm. Coding, data compression, Huffman trees. Most of this lecture is covered by section 17.3 of CLR. For a few additional applications, check here and here. |
| Lecture 14 (Feb 19) | Lempel-Ziv compression. 1997 class notes on Lempel-Ziv coding. Digital search trees. Priority queues. Uses, such as in discrete event simulation. Tournaments as priority queues. |
| Lecture 15 (Feb 20) | Binary heaps (chapter 7 of CLR). Heapsort. Additional binary heap operations. k-ary heaps (determining best k). Disjoint set structures: sections 22.1, 22.2, 22.3 of CLR. |
| Lecture 16 (Mar 3) | Assignment 3 due. Hand out assignment 4, due March 10, 2:30pm. Amortization (chapter 18 of CLR). Potential functions. Simple examples: stack with multipop, dynamic tables, lazy delete in red-black trees, binary addition, weight-balanced search trees. |
| Lecture 17 (Mar 5) | Second lecture on amortized analysis: splay trees (handout). Definition of and comparison with a treap. |
| Lecture 18 (Mar 6) | Hashing: chapter 12 of CLR. Direct addressing, hashing with chaining. Radix sort, bucket sort. |
| Lecture 19 (Mar 10) | Collect assignment 4. Hashing continued: open addressing, choice of hash functions. Introduction to graphs. |
| Lecture 20 (Mar 12) | Hand out assignment 5, due March 24, 2:30pm. 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. Euler tour. Detecting cycles. |
| Lecture 21 (Mar 24) | Collect assignment 5. Hand out assignment 6, due Apr 7, 2:30pm. Breadth first search (section 23.3 of CLR). Detecting bipartite graphs. |
| Lecture 22 (Mar 26) | Shortest path problem. Dijkstra's algorithm. See here. Minimal spanning trees: parts of chapter 24 of CLR. See also here. We covered the Prim-Dijkstra algorithm, but not Kruskal's. A two-approximation for the traveling salesman problem (section 37.2). |
| Lecture 23 (Mar 27) | Directed acyclic graphs. Topological sorting. See here. Strongly connected components in directed graphs. |
| Lecture 24 (Apr 7) | Collect assignment 6. Fast Fourier Transform. Multiplying polynomials in time O(n log n). |
| Lecture 25 (Apr 9) | Fast Fourier Transform: last details. Review of course material. Practice set on trees and recursion. Attempt questions 1, 2, 3 and 5 before peeking at the solutions. |
| Final (Apr 17: 2-5pm) | Location: Leacock 109. It is a 3-hour closed book examination. No calculators, cell phones, Blackberries, spy cameras, or other electronic devices are allowed. |