Schedule

A rigid schedule is not conducive to eﬀective learning, since it would limit our ﬂexibility 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 deﬁnite 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 23rd C1 Introduction; rod-cutting. §§ 1.*; 15.1.	25th C2 Fundamentals of alg. analysis; dynamic programming. §§ 2., 3.; .15.2, 15.3.

30th C3 Dynamic programming. §§ 15.4, 15.5.	February 1st C4 Divide and conquer. §§ 4.1, 4.2.

6th C5 ⋆ Quiz 1, regular class time & place.	8th C6 Solving recurrences. §§ 4.{3,4,5}.

13th C7 Probabilistic analysis. §§ 5.1, 5.2.	15th C8 Randomized algorithms. §§ 5.3.

20th C9 Augmenting data structures. §§ 14.*.	22nd C10 ⋆ Midterm Exam 1, regular class time & place.

27th C11 Elementary graph algorithms. §§ 22.*	March 1st C12 Minimum spanning trees. §§ 23.*

6th C13 Portfolio presentations v1.	8th C14 (snow day) Shortest paths. §§ 24.{1,2}.

13th ×No class. Spring break Mar. 12th–18th.	15th ×No class. Spring break Mar. 12th–18th.

20th C15 Elementary graph algorithms. §§ 22.*	22nd C16 Minimum spanning trees. §§ 23.*

27th C17 ⋆ Quiz 2, regular class time & place.	29th C18 Shortest paths. §§ 24.{1,2}.

April 3rd C19 Shortest paths. §§ 24.{3,4,5}.	5th C20 All-pairs shortest paths. §§ 25.*.

10th C21 NP completeness. §§ 34.{1,2,3}.	12th C22 NP completeness. §§ 34.{4,5}.

17th C23 Catch-up and review.	19th C24 ⋆ Midterm Exam 2, regular class time & place.

24th C25 Portfolio presentations v2.	26th C26 Greedy algorithms. §§ 16.{1,2,3}.

May 1st C27 Synthesis and review.	3rd C28 Synthesis and review.

8th ×No class. Finals week May 7th–11th. ⋆ Final exam: May 8th 8:00–10:00 a.m.	10th ×No class. Finals week May 7th–11th. ⋆ Check Univ. schedule for ﬁnal exams.

Figure 1: Approximate schedule, likely to change. Textbook items are in §§ chapter.section format.