| Lecture | Date | Topic | Reading/Comments | Quizzes | |
| 1. | Aug. 22 | Introduction. Mathematical Induction, Fibonacci numbers, recurrences (review). | Chapters 1-4 (review) | ||
| 2. | Aug. 24 | Fibonacci numbers and the Euclidean Algorithm | Chapters 1-4 (review) | ||
| 3. | Aug. 29 | Euclidean Algorithm, Asymptotics, Master Theorem | Chapters 1-4 (review) | ||
| 4. | Aug. 31 | Master Theorem, Dynamic Programming (Knapsack Problem) | Especially 4-3 through 4-6 | ||
| 5. | Sep. 5 | Dynamic Programming: Knapsack problem and Sequence comparisons | 15-3 for Dynamic Programming overview and 15-1, 15-2 for extra examples. | Quiz 0 takes place in class today. | |
| 6. | Sep. 7 | Dynamic programming, continued. Start of Greedy algorithms. Greedy Sheduling problem, design and proof of optimality. | 16-1 through 16-3 + class notes | ||
| 7. | Sep. 12 | Dynamic Scheduling problem. Huffman encoding (greedy data compression): design. | 16-1 through 16-3 + class notes | ||
| 8. | Sep. 14 | Huffman encoding: implementation and proof of correctness. | 16-1 through 16-3 + class notes + handout | ||
| 9. | Sep. 19 | Begin Graph Theory and Graph Algorithms | 22-1 through 22-3 + class notes | ||
| 10. | Sep. 21 | Graph Theory and Algorithms: the party problem | 22-1 through 22-3 + class notes | Quiz 1 takes place today | |
| 11. | Sep. 26 | Graph theory: basics and begin planar graphs; adjacency matrix versus adjacency list | 22-1 through 22-3 + class notes | ||
| 12. | Sept. 28 | Graph Coloring: chromatic number; scheduling and map coloring; history of the Four Color Problem (now Four Color Theorem) | class notes | ||
| 13. | Oct. 3 | Euler's formula and average degree; Proof of the six color theorem; Proof of the five color theorem; Proof of the four color theorem. Greedy coloring algorithm is in assignment 3, problem 5. | class notes | ||
| 14. | Oct. 5 | Chromatic number, M-Pire graphs, and thickness-two graphs: an open problem. | class notes | Quiz 2 takes place today | |
| 15. | Oct. 10 | Earth-Moon graphs and PCB testing. Begin shortest path algorithms | class notes and Chapter 24 | ||
| 16. | Oct. 12 | Single Source Shortest Paths. Dijkstra's Algorithm; Bellman-Ford Algorithm | class notes and Chapter 24 | ||
| 17. | Oct. 17 | Examination One | Study hard: form a study group and have some fun! | ||
| 18. | Oct. 19 | Dijkstra example, Bellman-Ford Algorithm, and begin Network Flows; side trip to Linear Programming | Chapter 24, class notes, and 29-1 and 29-2 | ||
| 19. | Oct. 24 | Network Flows, continued. Network Flow hall of fame. Ford-Fulkerson | class notes and 26-1 and 26-2 and handout | ||
| 20. | Oct. 26 | Application of the Network Flow problem: Max Flow/Min Cut Theorem | class notes and handout | Quiz 3 takes place today | |
| 21. | Oct. 31 (Happy Halloween!) | Factorization of Integers is time consuming | class notes and 31-9 | ||
| 22. | Nov. 2 | Probabalistic Algorithm for Primality Testing | class notes and 31-8 | ||
| 23. | Nov. 7 | RSA | class notes and 31-1 through 31-7 | ||
| 24. | Nov. 9 | RSA continued. Quantum Cryptography and the breakage of RSA. | class notes | Quiz 4 takes place today | |
| 25. | Nov. 14 | Fast Fourier Transform and Polynomial Multiplication | class notes and 30-1 and 30-2 (See 30-3 for implementation) | ||
| 26. | Nov. 16 | NP Completeness explained by way of 3SAT and (graph) 3-colorability | class notes and Chapter 34 | ||
| null | Nov. 20-24 | Fall Break | Happy Thanksgiving | ||
| 27. | Nov. 28 | Computational Geometry: Art Gallery Theorem | class notes and Chapter 33 for other applications | ||
| 28. | Nov. 30 | Escher Tilings or Thickness Research Presentation | Quiz 5 takes place today | ||
| 29. | Dec. 5 | Examination Two | Study hard: form a study group and have some fun! | ||
| 30. | Dec. 7 | Research presentation on Escher Tilings; guest speaker=Steve Ogden | |||
| 31. | Monday, Dec. 11 | Office hours to be determined |