| Date | Material | Comments and deadlines |
|---|---|---|
| Aug. 23 | Administrative issues; introduction to algorithm analysis | reading: Chapters 1.1, 1.4 |
| Aug. 25 | classifying functions by assymptotic growth rates | reading: Chapter 1.5
Assignment 1: .ps .pdf |
| Aug. 27 | Tools for analyzing and comparing performance: L'Hopitals's rule, mathematical induction | reading: Chapters 1.5, 3.1-3.4 |
| Aug. 30 | example for mathematical induction; example for average case analysis | reading: Chapters 1.6, 3.1-3.4 |
| . | ||
| Sept. 1 | binary search: optimality and recurrence equation | reading: Chapter 1 |
| Sept. 3 | recurrence equations | reading: Chapter 3.6
Assignment 2: .ps .pdf Assignment 1 due |
| Sept. 6 | Labor Day | no class |
| Sept. 8 | more on recurrence equations | reading:Chapter 3.6 |
| Sept. 10 | How to use the Master Theorem | reading: Chapter 3.6 |
| Sept. 13 | Two examples of clever O(n) time algorithms: celebrity and majority | reading: Manber 5.5 + 6.10, handout |
| Sept. 15 | Celebrity and majority algorithms | reading: Manber 5.5 + 6.10
Assignment 3: .ps .pdf Assignment 2 due |
| Sept. 17 | Multiplying two n-bit numbers - a divide-and-conquer example | reading: |
| Sept. 20 | Overview of sorting and selection; implementation and analysis of insertion sort | reading: Chapters 4.1, 4.2 |
| Sept. 22 | Average-case analysis of quicksort | reading: Chapter 4.4 |
| Sept. 24 | Lower bound for sorting, Radix sort | reading: Chapters 4.7, 4.11
Assignment 4: .ps .pdf Assignment 3 due |
| Sept. 27 | Heaps as a data strucure | reading: Chapter 4.8 |
| Sept. 29 | Analysis of heap generation, heap sort | reading: Chapter 4.8 |
| . | ||
| Oct. 1 | Using tournaments to find the min and max, the largest and second largest | reading: Chapters 5.2 and 5.3 |
| Oct. 4 | Selecting the k-th smallest element in linear time | reading: Chapter 5.4 |
| Oct. 6 | Review of data structures seen in CS251; introduction to graphs | reading: Chapter 6, 7.1 and 7.2
Assignment 5: .ps .pdf Assignment 4 due |
| Oct. 8 | Euler tours and Hamiltonian paths - two similar, yet different problems | |
| Oct. 11 | October Break | no class |
| Oct. 13 | Graph traversals: DFS and BFS | reading: Chapter 7 |
| Oct. 15 | More on graph traversals; using DFS and BFS to find connected components | reading: Chapter 7
Sample Midterm Questions: .ps .pdf Assignment 5 due |
| Oct. 18 | Review for midterm | |
| Oct. 19 | Midterm exam | 8:30-9:30pm, SMTH 108 |
| Oct. 20 | no class (makeup for midterm) | Assignment 6: .ps .pdf |
| Oct. 22 | DFS in directed graphs | reading: Chapter 7.4 |
| Oct. 25 | Strongly connected components | reading: Chapter 7.5 |
| Oct. 27 | Biconnectivity | reading: Chapter 7.7 |
| Oct. 29 | Minimum cost spanning trees | reading: Chapter 8.2 |
| . | ||
| Nov. 1 | Prim's algorithms | reading: Chapters 8.2 and 8.4 Assignment 6 due Assignment 7: .ps .pdf |
| Nov. 3 | Kruskal's algorithm, Union-Find implementations | reading: Chapters 8.4, 6.63, 6.6.4 |
| Nov. 5 | Single source shortest paths: Dijkstra's algorithm | reading: Chapter 8.3 |
| Nov. 8 | All-pairs shortest paths; dynamic programming | reading: Chapter 9.4 |
| Nov. 10 | Dynamic programming; Multiplying a sequence of matrices | reading: Chapter 10.1-10.3 Assignment 7 due Assignment 8: .ps .pdf |
| Nov. 12 | Dynamic programming: reconstructing the solution | reading: Chapter 10.3 |
| Nov. 15 | Topological search | reading: Chapter 7.4.6 |
| Nov. 17 | Minimum edit distance | reading: Manber 6.8 and Chapter 11.5 |
| Nov. 19 | Knuth-Morris-Pratt Algorithm | reading: Chapter 11.1-11.3 |
| Nov. 22 | Knuth-Morris-Pratt Algorithm | reading:Chapter 11.1-11.3 Assignment 8 due Assignment 9: .ps .pdf |
| Nov. 24 | Thanksgiving Break | no class |
| Nov. 26 | Thanksgiving Break | no class |
| Nov. 29 | Introduction to NP-completeness; decision and optimization problems | reading: Chapter 13 |
| . | ||
| Dec. 1 | Classes P, NP, and NP-complete | Chapter 13 |
| Dec. 3 | NP-completeness; problem reductions | Chapter 13; handout |
| Dec. 6 | Example of a reduction: 3-SAT to Clique | reading: Chapter 13 Assignment 9 due |
| Dec. 8 | Introduction to DNA Computing; Course evaluation | reading: Chapter 13.9 |
| Dec. 10 | Course Review; question and answer session | |
| Dec. 13 | FINAL EXAM, 3:20-5:20pm | MATH 175 |