Policies · Schedule · Syllabus

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 |