Course Home | Syllabus | Assignments | Schedule | Downloads | [print]

CS 3510: Advanced Algorithms/Data Structures

Spring 2021 Schedule

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

Class announcements may modify schedule from that listed above.

Last Updated 01/08/2021