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 22nd C1
Introduction; rod-cutting. §§ 1.*; 15.1.
|
24th C2
Fundamentals of alg. analysis; dynamic programming. §§ 2.*, 3.*; .15.2, 15.3.
|
|
29th C3
Dynamic programming. §§ 15.4, 15.5.
|
31st C4
Divide and conquer. §§ 4.1, 4.2.
|
|
February 5th C5
⋆ Quiz 1, regular class time & place.
|
7th C6
Solving recurrences. §§ 4.{3,4,5}.
|
|
12th C7
Probabilistic analysis. §§ 5.1, 5.2.
|
14th C8
Randomized algorithms. §§ 5.3.
|
|
19th C9
Augmenting data structures. §§ 14.*.
|
21st C10
⋆ Midterm Exam 1, regular class time & place.
|
|
26th C11
Elementary graph algorithms. §§ 22.*
|
28th C12
Minimum spanning trees. §§ 23.*
|
|
March 5th C13
Portfolio presentations v1.
|
7th C14
Shortest paths. §§ 24.{1,2}.
|
|
12th C15
⋆ Quiz 2, regular class time & place.
|
14th C16
Elementary graph algorithms. §§ 22.*
|
|
19th
×No class. Spring break Mar. 16th–24th.
|
21st
×No class. Spring break Mar. 16th–24th.
|
|
26th C17
Minimum spanning trees. §§ 23.*
|
28th C18
Shortest paths. §§ 24.{3,4,5}.
|
|
April 2nd C19
All-pairs shortest paths. §§ 25.*.
|
4th C20
String matching. §§ 32.{1,2,3}.
|
|
9th C21
Catch-up and review.
|
11th C22
⋆ Midterm Exam 2, regular class time & place.
|
|
16th C23
NP completeness. §§ 34.{1,2,3}.
|
18th C24
NP completeness. §§ 34.{4,5}.
|
|
23rd C25
Portfolio presentations v2.
|
25th C26
Greedy algorithms. §§ 16.{1,2,3}.
|
|
30th C27
Synthesis and review.
|
May 2nd C28
Synthesis and review.
|
|
7th
×No
class. Finals
week
May
6th–10th.
|
9th
×No
class. Finals
week
May
7th–11th.
|
|
|
|
|
|
|
|
|