Course Home | Syllabus | Assignments | Schedule | Downloads | [print]
CS 3510: Algorithms
Spring 2024 Schedule
| Day | Topic | Reading | Work Due |
| Jan 8 | Course introduction, algorithms, complexity | Ch 0 | |
| Jan 10 | Experimental measurement of algorithms | Chapter 0 | |
| Jan 12 | Experimental measurement of algorithms | Chapter 0 | |
| Jan 15 | Martin Luther King Jr. Day (no classes) | ||
| Jan 17 | Divide and conquer, Recurrence relations | Ch 2.1,2.2 | Chapter 0 |
| Jan 19 | Mergesort | Ch 2.3 | |
| Jan 22 | Selection | Ch 2.3 | Chapter 2 |
| Jan 24 | Matrix multiplication | Ch 2.5 | Chapter 2 |
| Jan 26 | Closest Pair | Ch 2 | Chapter 2 |
| Jan 29 | Graphs and representations | Ch 3.1 | Chapter 2 |
| Jan 31 | Graphs and representations | Ch 3.1 | Chapter 2 |
| Feb 2 | Depth first search and connectivity | Ch 3.2 | Chapter 2 |
| Feb 2-7 | Examination I | Ch 0,2 | Examination I |
| Feb 5 | Directed graph search | Ch 3.3 | |
| Feb 7 | Strongly connected components | Ch 3.4 | Chapter 3 |
| Feb 9 | Paths, distances, breadth first search | Ch 4.1-4.3 | Chapter 3 |
| Feb 12 | Dijkstra’s algorithm for shortest paths | Ch 4.4 | Chapter 3 |
| Feb 14 | Paths with negative edges | Ch 4.6 | Chapter 3 |
| Feb 16 | Paths in DAGS | Ch 4.7 | Chapter 4 |
| Feb 19 | President’s Day Holiday (no classes) | ||
| Feb 21 | Arrays vs. heaps for priority queues | Ch 4.5 | Chapter 4 |
| Feb 23 | Trees, minimum spanning trees, Cut property | Ch 5.1 | Chapter 4 |
| Feb 26 | Kruskal’s algorithm for MST | Ch 5.1 | Chapter 4 |
| Feb 28 | Disjoint sets and amortized analysis | Ch 5.1 | Chapter 4 |
| Mar 1 | Prim’s algorithm for MST | Ch 5.1 | Chapter 4 |
| Feb 29-Mar 6 | Examination II | Ch 3,4 | Examination II |
| Mar 4 | Huffman encoding | Ch 5.2 | |
| Mar 6 | SAT algorithm with horn formulas | Ch 5.3 | Chapter 5 |
| Mar 8 | Set cover | Ch 5.4 | Chapter 5 |
| Mar 11-15 | Spring Break (no classes) | ||
| Mar 18 | Shortest paths in DAGs (again) | Ch 6.1 | Chapter 5 |
| Mar 20 | Longest increasing subsequence | Ch 6.2 | Chapter 5 |
| Mar 22 | Edit distance | Ch 6.3 | Chapter 5 |
| Mar 25 | Knapsack | Ch 6.4 | Chapter 5 |
| Mar 27 | Chain matrix multiplication | Ch 6.5 | Chapter 6 |
| Mar 29 | All pairs shortest paths | Ch 6.6 | Chapter 6 |
| Apr 1 | Traveling sales person | Ch 6.6 | Chapter 6 |
| Apr 3 | Practical programming with dynamic programming | Ch 6 | Chapter 6 |
| Apr 5 | Linear programming | Ch 7.1 | Chapter 6 |
| Apr 8 | Duality | Ch 7.4 | Chapter 6 |
| Apr 8-14 | Examination III | Ch 5,6 | Examination III |
| Apr 10 | Simplex | Ch 7.6 | |
| Apr 12 | NP-complete problems | Ch 8 | Chapter 7 |
| Apr 15 | Branch-and-bound | Ch 9.1 | Chapter 7 |
| Apr 17 | Approximation algorithms | Ch 9.2 | Chapter 7 |
| Apr 19 | 2-Approximation of TSP | Ch 9.2 | Chapter 7 |
| Apr 22 | Local Search for TSP | Ch 9.3 | Chapter 9 |
| Apr 24 | Quantum Algorithms | Ch 10 | Chapter 9 |
| Apr 26 | Reading Day (no classes) | ||
| May 1 | Final Exam 9:00 am - 10:50 am | Ch 0,2,3-7,9 | Final Exam |
Class announcements may modify schedule from that listed above.
Last Updated 01/08/2024