A rigid schedule is not conducive to effective learning, since it would limit our flexibility in exploring ideas as they arise in class. The actual schedule (both the timing and the selection of topics) will be determined by in-class interactions. Nevertheless, a partial and approximate schedule, to serve as a baseline, appears in Figure 1; it will be updated as we progress. Please use it only as a rough guide to plan your studies. Do not use it to schedule travel or other events. If you need a definite answer on when something will or will not occur, you should check with me.
At the beginning and end of each class, I typically announce the topics and textbook sections covered in that class and those due at the next class. It is important that students read the material before the class in which it is discussed and, in general, keep up with readings and studies.
|
Tuesday |
Thursday |
|
January 19th C1
Introduction; rod-cutting. §§ 1.*; 15.1.
|
21st C2
Fundamentals of alg. analysis; dynamic programming. §§ 2.*, 3.*; .15.2, 15.3.
|
|
26th C3
Dynamic programming. §§ 15.4, 15.5.
|
28th C4
⋆ Quiz 1, regular class time & place.
|
|
February 2nd C5
Divide and conquer. §§ 4.1, 4.2.
|
4th C6
Solving recurrences. §§ 4.{3,4,5}.
|
|
9th C7
Probabilistic analysis. §§ 5.1, 5.2.
|
11th C8
Randomized algorithms. §§ 5.3.
|
|
16th C9
⋆ Midterm Exam 1, regular class time & place.
|
18th C10
Augmenting data structures. §§ 14.*.
|
|
23rd C11
Elementary graph algorithms. §§ 22.*
|
25th C12
Minimum spanning trees. §§ 23.*
|
|
March 1st C13
Shortest paths. §§ 24.{1,2}.
|
3rd C14
⋆ Quiz 2, regular class time & place.
|
|
8th
×No class. Spring break Mar. 7th–20th.
|
10th
×No class. Spring break Mar. 7th–20th.
|
|
15th
×No class. Spring break Mar. 7th–20th.
|
17th
×No class. Spring break Mar. 7th–20th.
|
|
22nd C15
Shortest paths. §§ 24.{3,4,5}.
|
24th C16
All-pairs shortest paths. §§ 25.*.
|
|
29th C17
Maximum flow. §§ 26.*.
|
31st C18
⋆ Quiz 3, regular class time & place.
|
|
April 5th C19
String matching. §§ 32.{1,2,3}.
|
7th C20
NP completeness. §§ 34.{1,2,3}.
|
|
12th C21
NP completeness. §§ 34.{4,5}.
|
14th C22
Greedy algorithms. §§ 16.{1,2,3}.
|
|
19th C23
⋆ Midterm Exam 2, regular class time & place.
|
21st C24
KMP alg. for str. matching. §§ 32.4.
|
|
26th C25
Special topic.
|
28th C26
Special topic. Term project submissions due.
|
|
May 3rd C27
⋆ Term Projects Exhibition.
|
5th C28
Synthesis and review.
|
|
10th
×No class. Finals week May 9th–13th.
|
12th
×No
class. Finals
week
May
9th–13th.
|
|
|
|
|
|
|
|
|