CS520 Analysis of Algorithms   

Policies  ·  Schedule  ·  Syllabus

Important information for students on COVID-19:

All students are required to follow public health guidelines in any university space, and are encouraged to continue these practices when off-campus(es). Students also are required to report any COVID-19 symptoms to the university immediately, as well as if they have potentially been exposed or have tested positive at a non-CSU testing location. If you suspect you have symptoms, please fill out the COVID Reporter (https://covid.colostate.edu/reporter/). If you have COVID symptoms or know or believe you have been exposed, it is important for the health of yourself and others that you complete the online COVID Reporter. Do not ask your instructor to report for you; if you report to your instructor that you will not attend class due to symptoms or a potential exposure, you are required to also submit those concerns through the COVID Reporter. If you do not have access to the internet to fill out the online COVID-19 Reporter, please call (970)491-4600.

If you report symptoms or a positive test, your report is submitted to CSU’s Public Health Office. You will receive immediate, initial instructions on what to do and then you will also be contacted by phone by a public health official. Based on your specific circumstances, the public health official may:

If you report a potential exposure, the public health official will help you determine if you are at risk of contracting COVID.

For the latest information about the University’s COVID resources and information, please visit the CSU COVID-19 site (https://covidrecovery.colostate.edu/).

Schedule - Spring 2021

Week Dates Topics Material
1 1/20 and 1/22 Amortized analysis, Sorted-list data type (using binary search trees) Cormen, Chapter 17, Tarjan, Ch. 4
2 1/25-1/29 Binary search trees Tarjan, Ch. 4
3 2/1-2/5 Linking and cutting trees Tarjan, Sections 5.1, 5.2
4 2/8-2/12 Implementation of the ''path'' data type to complete analysis of link - cut trees Tarjan Section 5.3
5 2/15-2/19 Max Flow Cormen, Ch. 26 through Section 26.3; Tarjan, Ch. 8
6 2/22-2/26 Better time bounds for Max flow Tarjan, Ch. 8
7 3/1-3/5 Meldable priority queues Tarjan, Ch.3
8 3/8-3/12 Meldable priority queues, Min Spanning tree, variants on Dijkstra Tarjan, Chapter 6. Use Cormen, Ch. 23 and Section 24.3 as reference for CS 320 material
9 3/15-3/19 Faster bounds for MST. single-source shortest path when edge weights are non-negative, max capacity augmentation Tarjan, Ch. 6
10 3/22-3/26 Better bounds for MST, Binomial heaps Tarjan, Ch. 6, Binomial heaps, on library reserve
11 3/30-4/2 MIDTERM April 2, 9:00 a.m. Binomial heaps. Binomial heaps, library reserve.
12 4/5-4/9 Fibonacci heaps Cormen, Ch. 19
4/12-4/16 SPRING BREAK
13 4/19-4/23 Triangulated graphs and perfect graphs Cormen, Section 16.1 (Review from CS320), Cormen, sections B2 and B4 (review and reference for terminology), Golumbic, Ch. 4, Sections 1, 2, 7; I will present my own variant of Sections 3 and 4. Golumbic, Ch. 1 serves as a reference for notation and terminology.
14 4/26-4/30 Triangulaged graphs, comparability graphs Cormen, appendix B.2, Golumbic, Sections 5.1, 5.7
15 5/3-5/7 Comparability graphs, Permutation graphs, interval graphs Modular Decomposition and Transitive Orientation. I will lecture on the material in Section 4 through subsection 4.1 in this paper. Also, Chapter 7 of Golumbic, focusing on explanation of ideas illustrated in Figure 7.2. (On electronic reserve at the library.)
Final Exam: Thursday 4/13 7:30-9:30 a.m.