Calendar

January 2004

SunMonTueWedThuFriSat
1 2 3
4 5
6
7
8 9 10
11 12
Class 1: Course intro, "running time"
13
Class 2: Functional Programming & Scheme intro and lab 1
14
Class 3: Growth rates, asymptotic analysis
15 16 17
18 19
No Class
MLK Day
20
Class 4: Lists in Scheme
lab 2
21
Class 5: O, Θ and Ω
22 23 24
25 26
Class 6: Analysis with O, Θ and Ω
27
Class 7: More Scheme! Lists under the hood, lambda (λ)
lab 3
solutions
28
Class 8: More analysis with O, Θ and Ω
29 30 31
Calendar

February 2004

SunMonTueWedThuFriSat
1 2
Class 9: Analysis with componants.
3
Class 10: Lambda!
Lab 4
solutions
4
Class 11: end of analyzing iterative algorithms, start merge sort.
5 6 7
8 9
Class 12: divide & conquer, recurrence relations
10
Class 12
6Week Exam (solutions)
Practice Analysis
11
Class 13: Exam Debrief
12 13 14
15 16
No Class President's Day
17
Class 14 the master method & retest of practicum
18
Class 15 Divide & Conquer and quicksort
Grades Due
19 20 21
22 23
Class 16 Quicksort's average case
24
Class 17 Scheme's dark side Lab 5
solutions
25
Class 18 Quick select
26 27 28
29
Calendar

March 2004

SunMonTueWedThuFriSat
1
Class Cancelled
2
Class 19:
Lower bounds for sorting
Lab 6
3
Class 20:
Quiz & Memoization
4 5 6
7 8
Class 21: Matrix Chain Multiplication
9
Class 22: Memoizing Matrix Chain Multiplication
10
Class 23: Finishing Memoizing Matrix Chain Multiplication
11 12 13
14 15
Spring Break
16
Spring Break
17
Spring Break
18
Spring Break
19
Spring Break
20
21 22
Class 24: Greedy Algorithms
23
Class 25: Greedy Algorithms and Knapsacks
Lab 6
24
Class 26: Knapsack based cryptography
25 26 27
28 29
Class 27: Number-theoretic algorithms Part I
30
Class 28:
12-week Exam &
Num-theory algs II
31
Class 29: Num-theory algs III & RSA intro
Calendar

April 2004

SunMonTueWedThuFriSat
1 2 3
4 5
Class 30: Exam Debrief & RSA
6
Class 31: More with the RSA.
Grades Due
7
Class 32: Introduction to P and NP
8 9 10
11 12
Class 33: Decision Problems & Certificates
13
Class 34: A Formal Definition of NP
14
Class 35: Nondeterministic Computing and Reducibility
15 16 17
18 19
Class 36: NP-Completeness
20
Class 37: NP-Complete Problems Everywhere
21
Class 38:
Quiz 3 (solution) Intro to Amortized Analysis
22 23 24
25 26
Class 39: Amortized Analysis of Multipop Stacks
27
Class 40: Amortized Analysis & Extensible Arrays
28
Class 41:
Social & Ethical Issues: Export of crypto software.
29
Class 42:
Review
a few practice problems
Monday Schedule
30
Calendar

May 2004

SunMonTueWedThuFriSat
1
2 3
4
Final Exam 0755 CH105
5
6 7 8
9 10
11
12
13 14
Grades Due
15
16 17
18
19
20 21 22
23 24
25
26
27 28 29
30 31