Instructor:
Dan Gildea
Time: TTh 11:05-12:20
Location: Computer Studies Building 632.
TAs and office hours:
Textbook: Introduction to Algorithms, Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. MIT Press, 2001.
Prerequisites: MTH150 Discrete Mathematics and CSC172 Data Structures
How does one design programs and ascertain their efficiency? Divide-and-conquer techniques, string processing, graph algorithms, mathematical algorithms. Advanced data structures such as balanced tree schemes. Introduction to NP-completeness and intractable combinatorial search, optimization, and decision problems.
| Date | Lecture | HW Assigned | HW Collected |
|---|---|---|---|
| Sep. 3 Th | Course Organization | * | * |
| Sep. 7 Tu | Chapter 2: Getting Started | * | * |
| Sep. 9 Th | Chapter 6: Heap Sort | 1 | * |
| Sep. 14 Tu | Chapter 7: Quicksort | * | * |
| Sep. 16 Th | Chapter 8: Sorting in Linear Time | 2 | 1 |
| Sep. 21 Tu | Chapter 9: Median and Order Statistics | * | * |
| Sep. 23 Th | Chapter 11: Hashing | 3 | 2 |
| Sep. 28 Tu | Chapter 12: Binary Search Tree | * | * |
| Sep. 30 Th | Chapter 13: Red-Black Tree | 4 | 3 |
| Oct. 5 Tu | Chapter 13: Red-Black Tree (cont'd) | * | * |
| Oct. 7 Th | Chapter 14: Augmenting Data Structures | * | 4 |
| Oct. 12 Tu | Problem Session 1 covering Assignments 1 through 4 | * | * |
| Oct. 14 Th | Midterm No. 1 covering Chapters 2, 6-9, 11-13 | * | * |
| Oct. 19 Tu | Chapter 15: Dynamic Programming | 5 | * |
| Oct. 21 Th | Chapter 15: Dynamic Programming (cont'd) | * | * |
| Oct. 26 Tu | Chapter 15: Dynamic Programming (cont'd) | 6 | 5 |
| Oct. 28 Th | Chapter 16: Greedy Algorithms (excluding matroids) | * | * |
| Nov. 2 Tu | matroids, Chapter 17: Amortized Analysis | 7 | 6 |
| Nov. 4 Th | Chapter 18: B-Tree | * | * |
| Nov. 9 Tu | Chapter 18: B-Tree (cont'd) | 8 | 7 |
| Nov. 11 Th | Chapter 19: Binomial Heaps | * | * |
| Nov. 16 Tu | Problem Session 2 covering Assignments 5, 6, 7, and 8 | * | 8 |
| Nov. 18 Th | Midterm No. 2 covering Chapters 14 through 18 | * | * |
| Nov. 23 Tu | solutions to midterm 2 | * | * |
| Nov. 30 Tu | Chapter 22: Graph Algorithms | 9 | * |
| Dec. 2 Th | Chapter 21: Disjoint Sets; Chapter 20: Fibonacci Heaps | * | * |
| Dec. 7 Tu | Chapter 23: Minimum Spanning Tree; Chapter 24: Single-Source Shortest Path | * | 9 |
| Dec. 9 Th | Chapter 25: All-Source Shortest Path | * | * |