| Date | Class Period & Lecture Topic | Reading | Assignment | |
|---|---|---|---|---|
| Aug 30 | 1. What is the class about and how will it work? (Syllabus, policies, business, motivation) |
Read and understand the course website and get on Slack | ||
| Sep 01 | 2. Algorithm Essentials (Big-O and basic arithmetic) |
Chapters 0, 1 | pp. 1-15 | Install Python and start playing around. |
| Sep 06 | 3. Algorithm Essentials (Modular arithmetic and Primality) |
Chapter 1 | pp. 16-30 | HW1 |
| Sep 08 | 4. Algorithm Essentials
(Cryptography and Euclid) |
pp. 30-38 | HW2 Project1 Design Experience |
|
| Sep 13 | 5. Divide and Conquer (Multiplication, Recurrence Relations, Merge Sort) |
Chapter 2 | pp. 45-50 | HW3 Project1: Primality Tester |
| Sep 15 | 6. Divide and Conquer (Medians, Matrix Multiplication, Convex Hull) |
pp. 50-57 | HW4 |
|
| Sep 20 | 7. Graphs (Depth-first Search) |
Chapter 3 | pp. 80-87 | HW5 Project2 Design Experience |
| Sep 22 | 8. Graphs (Directed Graphs and Strong Connectedness) |
pp. 87-95 | HW6 | |
| Sep 27 | 9. Graphs (Shortest Paths) |
Chapter 4 | pp. 104-113 | HW7 |
| Sep 29 | 10. Graphs (Priority Queues and Variations on Shortest Path) |
pp. 113-120 | HW8 Project2: Convex Hull |
|
| Oct 04 | 11. Greedy Algorithms (Minimum Spanning Trees) |
Chapter 5 | pp. 127-138 | HW9 |
| Oct 06 | 12. Greedy Algorithms (Huffman Encoding) |
pp. 138-143 | HW10 Project3 Design Experience |
|
| Oct 11 | 13. Greedy Algorithms (Horn Formulas and Set Cover) |
pp. 144-147 | HW11 | |
| Midterm (October 12[8am]-14[9pm; late fee after 2pm] in the testing center) Study Guide | ||||
| Oct 13 | 14. No lecture (Midterm) | |||
| Oct 18 | 15. Dynamic Programming (Longest Increasing Subsequence and Edit Distance) |
Chapter 6 | pp. 156-164 | HW12 |
| Oct 19 | Project3: Network Routing | |||
| Oct 20 | 16. Dynamic Programming (Knapsack and Chain Matrix Multiplication) |
pp. 164-171 | HW13 | |
| Oct 25 | 17. Dynamic Programming (Shortest Paths and Independent Sets) |
pp. 171-177 | Project4 Design Experience |
|
| Oct 27 | 18. Linear Programming (Introduction) |
Chapter 7 | pp. 188-198 |
HW14 |
| Nov 01 | 19. Linear Programming (Duality and Zero-sum Games) |
pp. 206-213 | HW16 | |
| Nov 03 | 20. Intelligent Search (Backtracking and Branch & Bound) |
Chapter 9 | pp. 271-276 + extra B&B TSP material | HW17 Project4: Gene Sequencing |
| Nov 08 | 21. Intelligent Search (More Branch & Bound) |
Chapter 9 | pp. 271-276 + extra B&B TSP material | no homework assignment |
| Nov 10 | 22. Intelligent Search (NP-completeness) |
Chapter 8 | pp. 232-247 + "Unsolvable Problems" box on page 263 | HW18 Project5 Design Experience |
| Nov 15 | 23. Intelligent Search (Approximation and Local Search) |
Chapter 9 | pp. 276-293 | HW19 |
| Nov 17 | 24. Advanced Algorithms (Randomized Algorithms) Why Consider Grad School? |
Sec 2.4 | Boxes on pp. 29, 56, 140 | HW20 |
| Nov 22 | Friday Instruction |
|||
| Nov 24 | Thanksgiving |
|||
| Nov 29 | 25. Advanced Algorithms (Evolutionary Computation) |
Project5: TSP with Branch and Bound | ||
| Dec 01 | 26. Advanced Algorithms (Neural Networks) |
|||
| Dec 06 | 27. Advanced Algorithms (Quantum Computation) |
Chapter 10 | pp. 297-302 | |
| Dec 08 | 28. Group Project Presentations |
Project6: Group TSP | ||
| Dec 09 | Reading Day | |||
| Dec 12 | Sec. 2 Final (7:00am–10:00am in class) Study Guide | |||
| Dec 12 | Sec. 4 Final (2:30pm-5:30pm in class) Study Guide | |||
| Dec 15 | Sec. 3 Final (3:00pm-6:00pm in class) Study Guide | |||
| Dec 16 | Sec. 1 Final (7:00am–10:00am in class) Study Guide | |||
CS 312: Algorithm Design and Analysis |
|