The schedule may be updated from time to time, as we progress. CLRS refers to Cormen, Leiserson Rivest and Stein(Second Edition)
| Lecture 1 (Jan 6) | General introduction. Review of Relevant material from 308-250. Definition of algorithm, abstract data types, data structures. Introduction to simple computer models: Turing model, RAM model, pointer based machines, comparison model, Boolean, circuits, Boolean Formulas. Uniformly bounded time, bit model of computation (or: logarithmic model). Worst case, best case, and average case complexity. Polynomial versus exponential time classes. Chapters 1,2, and 3 in CLR(this is review of material from 250), web pages from 1997. |
| Lecture 2 (Jan 8) | We review the notion of recursion. We introduce three new examples: Problem 4.6 of CLR, Euclid's Algorithm, Binary Search. The review is chapter 4 of Cormen, except for the proof of the Master Theorem. Euclid's algorithm is pages 856-859 of Cormen. We revisit one old example, Fibonnaci Numbers. |
| Lecture 3 (Jan 13) | Quicksort, Solving Recurrence Relations via Induction. Chapter 7 of CLR. |
| Lecture 4 (Jan 15) | Selection: chapter 9 of CLR. We cover the linear worst-case algorithm in its entirety, and gloss over Hoare's linear expected time algorithm. More Examples of induction proofs for the solution of a recurrence inequality. Assignment 1 handed out . |
| Lecture 5 (Jan 20) | Lower Bounds I: The Decision Tree Model, The information theory lower bounds for sorting and for searching an ordered array. Counting Sort, Bucket Sort and Radix Sort. Chapter 8 of CLR. |
| Lecture 6 (Jan 22) | Lower Bounds II: Further example for information theory lower bounds. Sorting n elements with values in 1 to k. We saw upper and lower bounds of Cnlog k. No notes were provided. |
| Lecture 7 (Jan 27) | Assignment 1 due. Lower Bounds III: The Comparision DAG. The information theory lower bound for the kth smallest element. Adversarial Arguments. The adversarial argument for median finding and finding the maximum and the minimum. The reduction approach and an example: finding convex hulls. No notes were provided. |
| Lecture 8 (Jan 29) | Review of primitive data structures: such as stacks, queues, deques, and lists. Chapter 10 of CLR; foranother account, see the 1997 class notes. Priority Queues, Heaps and Heapsort. Chapter 6 of CLR. Assignment 2 handed out. |
| Lecture 9 (Feb 3) | Review of Basic Graph Definitions, Combined Adjacency List-Adjacency Matrix data strcuture. Properties of trees including A graph is a tree if and only if we can label its vertices with distinct positive integers including 1 so that every vertex not labelled 1 has exactly one neighbour with a smaller label. See Blanchette's web page for CS 250 and Sections 22.1, Theroem B.5.1 (in Appendix) of CLR. |
| Lecture 10 (Feb 5) | DFS-including proof of correctness and use in topological sort and finding strong components Section 22.3, 22.4,22.5 of CLR. |
| Lecture 11 (Feb 10) | Assignment 2 due. SAT and 2SAT. |
| Lecture 12 (Feb 12) | Minimum weight spanning trees. Chapter 23 of Cormen |
| Midterm (Feb 17) | Note: closed book, 90 minutes, no calculators, cell phones or other electronic devices. THIS EXAM IS MORE OF A CLASS TEST. IT COVERS ONLY THE MATERIAL OF LECTURES 9-12. |
| Lecture 13 (Feb 19) | Approximation Algorithms. Definition of Approximation RATIO. 2-Approx Algorithm for Maximum Matching. 3/2 Approx Algorithm for TSP in Euclicean weighted graphs. |
| Lecture 14 (Mar 2) | Finding Blocks via depth first search. |
| Lecture 15 (Mar 4) | Testing Planarity Using DFS. Non-examined Topic. ` |
| Lecture 16 (Mar 9) | pre-order and post-order Tree Traversals, Dynamic programming examples, Longest increasing subsequence, Knapsack, largest weight stable set and longest path in a tree. See the solution to question 1 of assignment 2 in David Avis' 360 course for the algorithm for longest increasing subsequence. We solved exercise 16.2.2 on page 384 of the text (see the definition of 0-1 knapsack problem on page 382). Assignment 3 handed out. |
| Lecture 17 (Mar 11) | Coding and Compression, Huffman Trees, Lempel-Ziv Compression. See also Section 16.3 of Cormen. |
| Lecture 18 (Mar 16) | Disjoint set structures: sections 21.1, 21.2, 22.3 of CLR, and handout distributed in class. |
| Lecture 19 (Mar 18) | Red-Black Trees: Chapter 13 of Cormen. Brief Introduction to AVL Trees and 2-3 Trees. Assignment 3 due. |
| Lecture 20 (Mar 23) | Red-Black Trees Continued. Computing the transitive closure of a DAG. Partial Orders(page 1076 of Cormen). Linear Extensions. The 1/3-2/3 conjecture. |
| Lecture 21 (Mar 25) |
Augmented data structures. Chapter 14 of CLRS.
|
| Lecture 22 (Mar 30) | Introduction to LP, ILP, Linear time algorithm for 2-dimensional LP Assignment 4 handed out. |
| Lecture 23 (Apr 1) | The Art Gallery Thereom and its variants. |
| Lecture 24 (Apr 6) | Advanced Priority Queues. Binomial Heaps and Fibonnacci Heaps and their application to MWST. Chapters 19 and 20 of CLRS. |
| Lecture 25 (Apr 8) | Review and Perspectives. Assignment 4 due. |