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


August 31st C1 Introduction; illustrative algorithm.	September 2nd C2 Illustrative algorithm contd.

7th C3 Aspects of algorithms using example. §§ 1.*.	9th C4 Aspects of algorithms using example, contd. §§ A–D.

14th C5 Rod-cutting. §§ 2.0–2.2; 15.1.	16th C6 Fundamentals of alg. analysis; dynamic programming. §§ 2., 3.; .15.2, 15.3.

21st C7 ⋆ Quiz 1, regular class time & place.	23rd C8 Dynamic programming. §§ 15.4, 15.5.

28th C9 Divide and conquer. §§ 4.1, 4.2.	30th C10 Solving recurrences. §§ 4.{3,4,5}.

October 5th C11 Probabilistic analysis. §§ 5.1, 5.2.	7th C12 ⋆ Midterm Exam 1, regular class time & place.

12th ×No class. Fall break Oct. 11–12.	14th C13 Randomized algorithms. §§ 5.3.

19th C14 Augmenting data structures. §§ 14.*.	21st C15 Elementary graph algorithms. §§ 22.*

26th C16 Minimum spanning trees. §§ 23.*	28th C17 Shortest paths. §§ 24.{1,2}.

November 2nd C18 ⋆ Quiz 2, regular class time & place.	4th C19 Elementary graph algorithms. §§ 22.*

9th C20 Minimum spanning trees. §§ 23.*	11th C21 Shortest paths. §§ 24.{3,4,5}.

16th C22 All-pairs shortest paths. §§ 25.*.	18th C23 ⋆ Midterm Exam 2, regular class time & place.

23rd C24 String matching. §§ 32.{1,2,3}.	25th ×No class. Thanksgiving break Nov. 24–28.

30th C25 NP completeness. §§ 34.{1,2,3}.	December 2nd C26 NP completeness. §§ 34.{4,5}.

7th C27 Greedy algorithms. §§ 16.{1,2,3}.	9th C28 Synthesis and review.

14th ×No class. Finals week Dec. 13–17. ⋆ Final exam: Dec. 14 09:30–11:30.	16th ×No class. Finals week May 7th–11th. ⋆ Check Univ. schedule for ﬁnal exams.

Figure 1: Approximate schedule, likely to change. Notation: §§ x.y ⇒ textbook chapter x, section y.