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 17th C1 Introduction; rod-cutting. §§ 1.*; 15.1.	19th C2 Fundamentals of alg. analysis; dynamic programming. §§ 2., 3.; .15.2, 15.3.

24th C3 Dynamic programming. §§ 15.4, 15.5.	26th C4 Divide and conquer. §§ 4.1, 4.2.

31st C5 Solving recurrences. §§ 4.{3,4,5}.	February 2nd C6 ⋆ Quiz 1, regular class time & place.

7th C7 Probabilistic analysis. §§ 5.1, 5.2.	9th C8 Randomized algorithms. §§ 5.3.

14th C9 Augmenting data structures. §§ 14.*.	16th C10 Elementary graph algorithms. §§ 22.*

21st C11 ⋆ Midterm Exam 1, regular class time & place.	23rd C12 Special topic.

28th C13 Minimum spanning trees. §§ 23.*	March 2nd C14 Portfolio presentations v1.

7th ×No class. Spring break Mar. 6th–19th.	9th ×No class. Spring break Mar. 6th–19th.

14th ×No class. Spring break Mar. 6th–19th.	16th ×No class. Spring break Mar. 6th–19th.

21st C15 Shortest paths. §§ 24.{1,2}.	23rd C16 Shortest paths. §§ 24.{3,4,5}.

28th C17 All-pairs shortest paths. §§ 25.*.	30th C18 Maximum ﬂow. §§ 26.*.

April 4th C19 ⋆ Quiz 2, regular class time & place.	6th C20 String matching. §§ 32.{1,2,3}.

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

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

25th C25 Greedy algorithms. §§ 16.{1,2,3}.	27th C26 KMP alg. for str. matching. §§ 32.4.

May 2nd C27 Portfolio presentations v2.	4th C28 Synthesis and review.

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

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