CS420 Introduction to Analysis of Algorithms, Spring 2020, McConnell   

Policies  ·  Schedule  ·  Syllabus

Tentative Schedule - Spring 2020


MIDTERM, Thursday, March 12, 6:00-9:00 p.m., Clark A103
Week Dates Topics Material
1 1/22 Quick review of asymptotic analysis, recurrences, divide-and-conquer (No recition this week.) Handout on big-O analysis; Cormen text: Chapters 1, 2, 3 through page 56, 4.1, 4.5.;
On-line Python tutorial
2 1/27, 1/29 Review of asymptotics, recurrences, divide-and-conquer; How to read texts and papers in our field, sorting networks. Ch. 8 of a previous edition of our textbook; "Sorting networks" to be posted.
3 2/3, 2/5 Examples of divide-and-conquer. Convolution Ch. 30
4 2/10, 2/12 Fast-Fourier Transform (FFT) -- another example of divide-and-conquer Ch. 30
5 2/17, 2/19 FFT, All-pairs shortest paths Chs. 30, 25
6 2/24, 2/26 All-pairs shortest paths, randomized algorithms, randomized Quicksort Ch. 25; Sections 5.1, 5.2, 5.3, Ch. 7
7 3/2, 3/4 Randomized Quicksort, Randomized Selection Chapter 7, Chapter 9
8 3/9, 3/11 Randomized algorithms, randomized search trees The Design and Analysis of Algorithms, Ch. 13 on e-reserve
Spring break
9 3/25 Randomized data structure for point location. deBergCh6.pdf on E-reserve
10 3/30, 4/1 Point location, Hash tables, Amortized analysis deBergCh6.pdf, Cormen Ch. 11 through 11.2, and Ch. 17, Data Structures and Network Algorithms - Search Trees on e-Reserve
11 4/6, 4/8 Amortized analysis Data Structures and Network Algorithms - Search Trees, Section 4.3 only.
12 4/13, 4/15 Network flows and reductions Cormen, Chapter 26 through Section 26.3
13 4/20, 4/22 Approximation algorithms Cormen, Ch. 35
14 4/27, 4/29 Topic to be determined
Midterm exam: Thursday, March 12, 6:00-9:00 p.m., Clark A103
Final exam: Tuesday May 12, 11:50-1:50 in the usual classroom.