CS420dl Schedule

Introduction to the
Analysis of Algorithms

• Lecture 1 notes, slides
• Discussion 0 due Fri May 18.
  Make sure you understand the instructions for discussions and quizzes, see the syllabus.
• Discussion 1 due Wed May 23
• Reading: The notes are always your first source
  On problems and (in)tractability, further reading is in CLRS (Cormen Leiserson Rivest Stein) Chapter 34.

• Lecture 2 notes, slides
• Lecture 3 notes, slides
• Start working on Assignment 0
• Discussion 2 due Wed May 30
• Reading: CLRS Appendix A, chapter 3, further reading 8.1

• Lecture 4 notes, slides
• Assignment 0 due Sun June 3
• Start working on Assignment 1
  due Sun June 10; Discussion 3 helps you with this.
• Reading: CLRS 4.4, 4.5,
  Rosen Recurrence Relations (6th edition 7.1, 7.2, 7.3)

• Lecture 5 notes, slides
• Discussion 3 due Wed June 6
• Assignment 1 due Sun June 10
• Reading: CLRS Ch 6, 7

• Material from weeks 1, 2, 3, and 4.
  Math fundamentals and intro to sorting.
  Test format: a quiz, that can be taken ONCE over a period of 2 hours. The test period has been extended to June 24.

• lecture 6 notes, slides4.
• Assignment 2 due - July 1
• Reading:CLRS section 33.3: Finding the convex hull

• Midterm Discussion.
• lecture 7 DFBF notes, DFBF slides4,
• lecture 8 Greedy notes, Greedy slides4.
• Assignment 2 due - July 3
• Reading: CLRS Chapter 22: Elementary Graph Algorithms, CLRS Greedy Algorithms 16.1, 16.2, 16.3.

• Lecture 9 DP notes, DP slides.
• Assignment 2 due - July 3
• Assignment 3 due - July 8 Assignment 3
• Discussion 4 due, July 8 Discussion 4
• Reading: CLRS Chapter 15

• Lecture 10 backtrack notes, lecture 10 slides.
  Reading: Donald Knuth's Dancing Link Notes. Dancing Link slides.
• Discussion 6 due, July 13 (Yes we are skipping discussion 5) Discussion 6
• Assignment 4 due - July 15 Assignment 4

• Knapsack lecture notes , slides.
• Notice: Slide 39 was updated
  after the lecture (imprecise language)
• Assignment 5 due July 24

• Shortest paths lecture notes, slides.
• Discussion 7 due July 27

• Graph Traversals to Shortest Paths
  Test in on line quiz format, open from Sat July 28 until Wed Aug 1