| Date | Material | Comments and deadlines | ||
|---|---|---|---|---|
| Aug. 23 | Administrative issues; introduction to algorithm analysis | reading: Chapter 1, 1.4.1-1.4.2 | ||
| Aug. 25 | Worst-case and average case analysis; optimality of algorithms | reading: Chapter 1,call.html
1.4.3 -1.4.7
Assignment 1 |
||
| Aug. 27 | Classifying functions by asymptotic growth rates. L'Hopitals's rule | reading: Chapter 1, 1.5.1-1.5.3 | ||
| Aug. 30 | Mathematical induction; examples. | reading: Chapter 1.3.2 | ||
| Sept. 1 | Recurrence equations. Binary search. Worst-case analysis. | reading:Chapter 1.61-1.6.2 | ||
| Sept. 3 | Binary search. Average-case analysis. Optimality. | reading: Chapter 1.6.3-1.6.4
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 | The Master Theorem. | reading: Chapter 3.6 | ||
| Sept. 13 | Analizing the complexity of integer multiplication. | |||
| Sept. 15 | The celebrity problem: an O(n) time algorithm. | reading: Manber 5.5
Assignment 3: .ps .pdf Assignment 2 due |
||
| Sept. 17 | Majority problem | reading: Manber 6.10 | ||
| Sept. 20 | Sorting:an overview. implementation and analysis of insertion sort | reading: Chapters 4.1, 4.2 | ||
| Sept. 22 | Quicksort. Worst-case and average-case analysis. | reading: Chapter 4.4 | ||
| Sept. 24 | Lower bound for sorting | Assignment 4:
.ps
.pdf
Assignment 3 due |
||
| Sept. 27 | Heaps | reading: Chapter 4.8 | ||
| Sept. 29 | Analysis of heap construction and heapsort | reading:Chapter 4.8 | ||
| Oct. 1 | Radix sort | reading: Chapter 4.11 | ||
| Oct. 4 | Finding the min and max, the largest and second largest. | reading: chapter 5.2-5.3 | ||
| Oct. 6 | Graphs: an overview | Assignment 4 due
Assignment 5: .ps .pdf |
||
| Oct. 8 | canceled (make up for midterm) | |||
| Oct. 11 | October Break | no class | ||
| Oct. 13 | Depth first search | reading: Chapter 7 | ||
| Oct. 15 | Breath first search | reading:
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 | Directed Ayclic graphs. Topological sort | Assignment 6: .ps .pdf |
||
| Oct. 22 | Strongly connected components | reading: Chapter 7.5 | ||
| Oct. 25 | Finding biconnected components | reading: Chapter 7.7 | ||
| Oct. 27 | Minimum cost spanning trees | reading: Chapter 8.2 | ||
| Oct. 29 | Prim's algorithm | reading: Chapters 8.2 | ||
| . | ||||
| Nov. 1 | Single source shortest path | reading: Chapter 8.3
Assignment 6 due Assignment 7: .ps .pdf |
||
| Nov. 3 | Kruskal's algorithm | reading: Chapter 8.4 | ||
| Nov. 5 | All-pairs shortest paths | reading: Chapter 9.4 | ||
| Nov. 8 | Dynamic programming. | |||
| Nov. 10 | Dynamic programming. Optimal Parenthesization | |||
| Nov. 12 | Dynamic programming. Sequence Comparison |
Assignment 7 due Assignment 8: .ps .pdf | ||
| Nov. 15 | String matching | |||
| Nov. 17 | Knuth-Morris-Pratt Algorithm | reading:Chapter 11.1-11.3 | ||
| Nov. 19 | Knuth-Morris-Pratt Algorithm | reading: Chapter 11.1-11.3 | ||
| Nov. 22 | The traveling salesman problem. Greedy strategies | reading: Cahpter 13.8 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 | ||
| Dec. 6 | Bioinformatics | Assignment 9 due |
||
| Dec. 10 | Course Review | |||
| Dec. 13 | FINAL EXAM, 3:20-5:20pm | MATH 175 | ||