CS420 Introduction to Analysis of Algorithms   

Announcements  ·  Overview  ·  Schedule  ·  Syllabus

Schedule - Spring 2012


Week Dates Topics Material Due
1 8/20-8/24 Asymptotic analysis pp. 5-6, Ch. 2, pp. 43-56, Asymptotic analysis (big O)
2 8/27-8/31 Asymptotics, Recurrences Section 4, Recurrences
3 9/3-9/7 Recurrences from algorithms, master theorem Chapter 4, Section 33.4 Recurrences
4 9/3-9/7 Strassen's algorithm, closest pair, sorting networks Chapter 4, Section 33.4, handout on sorting networks
5 9/10-9/14 Strassen's algorithm, closest pair, sorting networks Chapter 4, Section 33.4, handout on sorting networks
6 9/17-9/21 Rules of probability; examples; hiring problem 5.1, 5.2, 5.3
7 9/24-9/28 Randomized algorithms and their analysis; Quicksort 5.1, 5.2, 5.3, Chapter 7
8 10/1-10/5 Review of principles of counting;
9 10/1-10/5 Review of principles of counting; lower bounds for sorting, reductions 8.1
10 10/8-10/12 Selection; randomized selection 9.1, 9.2
11 10/15-10/19 Worst-case bounds for order statistics 9.3
12 10/22-10/26 Review, midterm, randomized search trees Handout on treaps Midterm 10/24
13 10/29-11/2 Randomized search trees; analysis of randomized hashing Handout on treaps; 11.1-11.2
14 11/5-11/9 Amortized analysis Chapter 17; handout on splay trees
15 11/12-11/16 Amortized analysis, advanced data structures Chapter 17; handout on splay trees; handout on binomial heaps
11/19-11/23 Fall break
16 11/26-11/29 Binomial heaps, leftist heaps, simulating array list with binary trees
17 12/3-12/7 Review 12/3; review for final 12/7 Exam 12/5

Final exam: December 10, 7:30-9:30 a.m. (Sorry about the early hour; I don't schedule them.)