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/).
|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|
|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.)|