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

CS 3510: Advanced Algorithms/Data Structures

Spring 2018 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 Arithmetic algorithms Ch 1.1 Chapter 0
Jan 19 Modular arithmetic algorithms Ch 1.2 Chapter 1
Jan 22 Modular arithmetic algorithms Ch 1.2 Chapter 1
Jan 24 Modular arithmetic algorithms Ch 1.2 Chapter 1
Jan 26 Primality algorithms Ch 1.3 Chapter 1
Jan 29 RSA cryptography algorithms Ch 1.4 Chapter 1
Jan 31 RSA cryptography algorithms Ch 1.4 Chapter 1
Feb 2 Divide and conquer, multiplication, Recurrence relations Ch 2.1,2.2 Chapter 2
Feb 5 Mergesort, selection Ch 2.3,2.4 Chapter 2
Feb 7 Mergesort, selection Ch 2.3,2.4 Chapter 2
Feb 9 Matrix multiplication, Closest Pair Ch 2.5,2 Chapter 2
Feb 12 Graphs and representations Ch 3.1 Chapter 2
Feb 14 Graphs and representations Ch 3.1 Chapter 2
Feb 16 Depth first search and connectivity, Directed graph search Ch 3.2,3.3 Chapter 2
Feb 19 President’s Day Holiday (no classes)
Feb 20-25 Examination I Ch 0,1,2 Examination I
Feb 21 Strongly connected components Ch 3.4
Feb 23 Paths, distances, breadth first search, Dijkstra’s algorithm for shortest paths Ch 4.1-4.4
Feb 26 Paths with negative edges, paths in DAGS Ch 4.6,4.7 Chapter 3
Feb 28 Paths with negative edges, paths in DAGS Ch 4.6,4.7 Chapter 3
Mar 2 Arrays vs. heaps for priority queues Ch 4.5 Chapter 3
Mar 5 Trees, minimum spanning trees, Cut property and Kruskal’s algorithm for MST Ch 5.1 Chapter 3
Mar 7 Trees, minimum spanning trees, Cut property and Kruskal’s algorithm for MST Ch 5.1 Chapter 4
Mar 9 Disjoint sets and amortized analysis Ch 5.1 Chapter 4
Mar 12-16 Spring Break (no classes)
Mar 19 Prim’s algorithm for MST, Huffman encoding Ch 5.1,5.2 Chapter 4
Mar 21 Prim’s algorithm for MST, Huffman encoding Ch 5.1,5.2 Chapter 4
Mar 23 SAT algorithm with horn formulas, Set cover Ch 5.3,5.4 Chapter 5
Mar 26 Shortest paths in DAGs (again), Longest increasing subsequence Ch 6.1,6.2 Chapter 5
Mar 28 Shortest paths in DAGs (again), Longest increasing subsequence Ch 6.1,6.2 Chapter 5
Mar 30 Edit distance Ch 3,4,5 Chapter 5
Apr 2-Apr 8 Examination II Ch 3,4,5 Examination II
Apr 2 Quiz Review Ch 6.3
Apr 4 Edit distance Ch 6.3
Apr 6 Knapsack, Chain matrix multiplication Ch 6.4,6.5 Chapter 6
Apr 9 All pairs shortest paths Ch 6.6 Chapter 6
Apr 11 All pairs shortest paths Ch 6.6 Chapter 6
Apr 13 Traveling sales person,Practical programming with dynamic programming Ch 6.6 Chapter 6
Apr 16 Linear programming, Duality Ch 7.1,7.4 Chapter 6
Apr 18 Linear programming, Duality Ch 7.1,7.4 Chapter 6
Apr 20 Simplex, NP-complete problems and dealing with them Ch 7.6,8,9 Chapter 7
Apr 23 Review/Quiz Ch 0-7 Chapter 7
Apr 25 Review/Quiz Ch 0-7 Chapter 7
Apr 26 Reading Day
Apr 30 Final Exam 7:00 am - 8:50 am Ch 0-7 Final Exam

Class announcements may modify schedule from that listed above.

Last Updated 04/01/2018