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

CS 3510: Advanced Algorithms/Data Structures

Spring 2017 Schedule

Day Topic Reading Work Due
Jan 10 Course introduction, algorithms, complexity Ch 0
Jan 12 Experimental measurement of algorithms Chapter 0
Jan 16 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 0
Jan 24 Modular arithmetic algorithms Ch 1.2 Chapter 0
Jan 26 Primality algorithms Ch 1.3 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 1
Feb 7 Mergesort, selection Ch 2.3,2.4 Chapter 1 Chapter 2
Feb 9 Matrix multiplication, Closest Pair Ch 2.5,2 Chapter 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 20 President’s Day Holiday (no classes)
Feb 21-26 Examination I Ch 0,1,2 Examination I
Feb 21 Strongly connected components Ch 3.4 Chapter 3
Feb 23 Paths, distances, breadth first search, Dijkstra’s algorithm for shortest paths Ch 4.1-4.4 Chapter 3
Feb 28 Paths with negative edges, paths in DAGS Ch 4.6,4.7 Chapter 3 Chapter 4
Mar 2 Arrays vs. heaps for priority queues Ch 4.5 Chapter 3 Chapter 4
Mar 7 Trees, minimum spanning trees, Cut property and Kruskal’s algorithm for MST Ch 5.1 Chapter 3 Chapter 4
Mar 9 Disjoint sets and amortized analysis Ch 5.1 Chapter 5
Mar 13-17 Spring Break (no classes)
Mar 21 Prim’s algorithm for MST, Huffman encoding Ch 5.1,5.2 Chapter 5
Mar 23 SAT algorithm with horn formulas, Set cover Ch 5.3,5.4 Chapter 5
Mar 28 Shortest paths in DAGs (again), Longest increasing subsequence Ch 6.1,6.2 Chapter 5
Mar 30 Quiz Review, Entropy and information theory Ch 3,4,5 Chapter 5
Mar 29-Apr 4 Examination II Ch 3,4,5 Examination II
Apr 4 Edit distance Ch 6.3 Chapter 5 Chapter 6
Apr 6 Knapsack, Chain matrix multiplication Ch 6.4,6.5 Chapter 5 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 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 6 Chapter 7
Apr 25 Review/Quiz Ch 0-7 Chapter 7
Apr 27 Reading Day
May 2 Final Exam 10:30 am - 12:30 pm Ch 0-7 Final Exam

Class announcements may modify schedule from that listed above.

Last Updated 03/21/2017