CS520: Analysis of Algorithms   

Policies  ·  Schedule  ·  Syllabus

Schedule - Spring 2016

Week Dates Topics Material Due
1 1/18-1/22 Novel implementations of priority queues Review Cormen, Chapters 1-4 on your own; Read Tarjan Chapters 1 and 3; Binomial heaps, to be posted on the library electronic reserve Homework 1
2 1/25-1/29 Novel implementations of priority queues; Fibonacci heaps Cormen, Chapter 19
3 2/1-2/5 A new look at the Minimum Spanning Tree problem; "balancing" as an algorithm design technique Tarjan, Chapter 6 Homework 2
4 2/8-2/12 Finish new MST bounds; algorithms and bounds for max flow not covered in CS420 Tarjan, Chapter 8; review Cormen, pp. 708-726
5 2/15-2/19 Bounds for max flow on unit graphs; minimum cycle mean Richard M. Karp, A Characterization of the Minimum Cycle Mean in a Digraph To get Karp's paper, google the title and download the PDF. You may need to log in throught secure.colostate.edu to get access to it.
5 2/22-2/26 Minimum cycle mean, blossoms and matching in arbitrary graphs Karp's paper (cont.); Jack Edmonds, Paths, Trees, and Flowers, Canadian J. Math. 17 (1965), 449-467. Get Edmonds's paper the way you got Karp's.
6 2/29-3/4 Maximum matching in non-bipartite graphs Finish Edmonds's paper; Tarjan, Chapter 9. Chapter 9, which shows how to get better bounds than Edmonds did, is also helpful as a guide to some of the elements of Edmonds's paper. Homework 3, due 3/8. Midterm on 3/10.
7 3/7-3/11 Review for midterm; midterm Thursday
3/14-3/18 Spring break
8 3/21-3/25 NP-completeness Handout on NP-completeness; Accompanying Python file; Cormen, Chapter 34 after Tuesday's class.
9 3/28-4/1 NP-completeness Continue on handout; Cormen, Chapter 34 Homework 4, due April 12
10 4/4-4/8 NP-completeness; linear programming Cormen, Chapter 34; Posting on Canvas; soon to be moved to On-Line Reserve at library. Ignore marks in the text (they belong to a previous owner of the book).
11 4/11-4/15 Linear programming Postings in Canvas, Linear Programming Ch. 1-4
12 4/18-4/22 Linear programming, Computational Geometry Linear Programming, Ch. 5; de Berg, Ch. 1, 2 Homework 5
13 4/25-4/29 Computational Geometry de Berg, Ch. 2
14 5/2-5/6 Computational Geometry de Berg, Ch. 6, available for download from Springer, from campus or through secure.colostate.edu
Final exam: Tuesday, May 10, 6:20-8:20 p.m.