January 2009
Sunday Monday Tuesday Wednesday Thursday Friday Saturday
       
1


2


3


4


5


6


7

Class 1: Hello algorithms

8


9

Class 2: Growth rates, asymptotic analysis

10


11


12

Class 3: The calculas of Θ, Ω, O

13


14

Class 4: Analysis with O, Θ and Ω

15


16

Class 5: More analysis with O, Θ and Ω

17


18


19


MLK Day
20

Class 6: Finishing analysis of simple iterative algorithms

Monday Schedule
21

Class 7: Analysis with componants

22


23

Class 8: Some classic iterative algorithms

24


25


26

Class 9: Merge Sort and Divide & Conquer

27


28

Class 10: The Master Method and Divide & Conquer

29


30

Class 11: Quicksort

31


February 2009
Sunday Monday Tuesday Wednesday Thursday Friday Saturday
1


2

Class 12: Quicksort's average case

3


4

Class 13: Quick select

Project 1 Assigned
5


6

Class 14: Lower bounds for sorting

7


8


9

Class 15: Number Theoretic Algorithms Part 1

Start X-Week
10


11

Exam 1

12


13

Class 16: Number Theoretic Algorithms Part 2

End X-Week
Project 1 Due
14


15


16


Wash's BDay
17


18

Class 17: RSA

19


20

RSA Lab
(Previous class's notes)

21


22


23

Class 18: Memoizing Matrix Chain Multiplication (the intro I skipped! sorry)

24


25

Missed memoizing intro, recursive solutions to optimiztion problems, a bit about the project.

26


27

Class 19: Finishing memoization (Recovering Solutions)

28


March 2009
Sunday Monday Tuesday Wednesday Thursday Friday Saturday
1


2


Snow Day
3


4

Class 20: Reintroduction to graphs & Breadth-first search

5


6

Class 21: Depth-first search and topological sort

7


8


9

Class 22: Intro to Greedy Algorithms

10


11

Class 23: Greedy Algs & proofs of optimality

12


13

Class 24: Finishing Up Greeedy Algorithms

14


15


16


Spring Break
17


Spring Break
18


Spring Break
19


Spring Break
20


Spring Break
21


22


23

Class 25: Dijkstra as greedy

Project 2 Assigned
24


25

Class 26: Floyd-Warshall all-pairs-shortest path

26


27

Class 27: Amortized Analysis I

28


29


30

Class 28: Amortized Analysis II

Start X-Week
31


       

April 2009
Sunday Monday Tuesday Wednesday Thursday Friday Saturday
     
1

Class 29: "Social Implications" - encryption and national security.

2


3

Exam 2

End X-Week
Project 2 Due
4


5


6

Exam Debrief

7


8

Class 30: Intro to P and NP

9


10

Class 31: Decision Problems, Certificates & a formal definition of NP & Proving Problems are in NP

11


12


13

Class 32: Nondeterministic Computing & Polynomial time reduction

14


Project 3 Assigned
15

Class 33: A non-trivial reduction problem.

16


17

Class 34: NP-Completeness

18


19


20

Class 35: Finishing NP-Completeness & Strategies for NP-Hard Problems: randomized greedy + local optimization

21


22

Class 36: A Geometric view of local optimization

23


24

Class 37: Case study in NP-Hard optimization: partition

25


26


27

Class 38: Project worktime & SOFs

28


Project 3 Due
29


Review & WormWorld tournament (1900, MI302)
30


Final Exam (1930, MI206)