CS420 Introduction to Analysis of Algorithms, Spring 2021, McConnell
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, 1/22||Quick review of asymptotic analysis, recurrences, divide-and-conquer|| Handout on big-O analysis; Handout on bounding recurrences.
Cormen text: Chapters 1, 2, 3 through page 56, 4.1, 4.5.; |
On-line Python tutorial
|2||1/25-1/29||Review of asymptotics, recurrences, divide-and-conquer; sorting networks.||Chapter of a previous edition of our textbook, "Sorting Networks" on electronic reserve at the library.|
|3||2/1-2/5||How to read texts and papers in our field. Convolution||Ch. 8, Ch. 30|
|4||2/8-2/12||Fast-Fourier Transform (FFT)||Ch. 30|
|5||2/15-2/19||FFT, (Fri:) Randomized algorithms, randomized Quicksort||Ch. 30, 5.1, 5.2, 5.3, Ch. 7|
|6||2/22-2/26||Randomized algorithms, randomized Quicksort||Sections 5.1, 5.2, 5.3, Ch. 7|
|7||3/1-3/5||Randomized Selection, randomized search trees||Chapter 9, D. Kozen, The Design and Analysis of Algorithms, Ch. 13 on e-reserve at lib.colostate.edu|
|8||3/8-3/12||Randomized search trees, Hash tables||Cormen, Ch. 11 through 11.2||9||3/15-3/19||Midterm March 19, 1:00. Amortized analysis||Cormen, Ch. 17|
|10||3/22-3/26||Amortized analysis of splay trees||Data Structures and Network Algorithms - Search Trees on e-Reserve, Section 4.3 only|
|11||3/30-4/2||Advanced data structure tricks on splay trees, Network flows and reductions||Section 4.3 reserve, Cormen, Chapter 26 through Section 26.3|
|12||4/5-4/9||Network flows and reductions, Approximation algorithms||Cormen, Chapter 26 through Section 26.3, Cormen Ch. 35|
|13||4/20, 4/22||Approximation algorithms||Cormen, Ch. 35|
|14||4/25-4/29||Approximation algorithm, computational geometry||Cormen, Section 33.1, 33.2, 33.3. (33.4 is covered in most of our CS320 sections.)|
|15||5/3-5/7||Brief overview of NP-completeness; review||Cormen, Section 34.5|