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:

• choose to recommend that you be tested and help arrange for a test;
• conduct contact tracing;
• initiate any necessary public health requirements or recommendations and notify you if you need to take any steps.

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

Course topics

Week Dates Topics Material
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
Spring break
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
Final exam: Tuesday May 11, 7:30-9:30 a.m.