CS 161 - Algorithms - Spring 2013

[general info]  [lectures] [homeworks] [exams]

• 5/29. Course notes for lecture 17.
• 5/21. Course notes for lecture 16.
• 5/20. Practice Final has been posted (not due).
• 5/20. hw8 has been posted (due 4pm Tuesday 6/4).
• 5/20. hw7 has been posted (due 4pm Tuesday 5/28).
• 5/20. Course notes for lecture 15.
• 5/15. Course notes for lecture 14.
• 5/14. hw6 has been posted (due 4pm Tuesday 5/21).
• 5/1. Midterm posted.
• 5/1. Course notes for lecture 8.
• 4/29. hw5 has been posted (due 4pm Tuesday 5/7).
• 4/24. Animation for lecture 7.
• 4/24. Course notes for lecture 7.
• 4/22. hw4 has been posted (due 4pm Tuesday 4/30).
• 4/17. Course notes for lecture 6.
• 4/17. Course notes for lecture 5.
• 4/15. hw3 has been posted (due 4pm Tuesday 4/23).
• 4/12. Course notes for lecture 4.
• 4/10. Course notes for lecture 3.
• 4/8. hw2 has been posted (due 4pm Tuesday 4/16).
• 4/8. Course notes for lecture 2.
• 4/6. Office hours for 4/6 and 4/7 moved
• 4/2. Course notes for lecture 1.
• 4/1. hw1 has been posted (due 4pm Tuesday 4/9). please join piazza for questions / updates / clarifications.
• 3/19. welcome

general information

instructor:

• Luca Trevisan, Gates 474, Tel. 650 723-8879, email trevisan at stanford dot edu

TAs:

• Maurizio Caligaris
• Jeffrey Chen
• Phil Chen
• Mike Chrzanowski
• Michael Kim
• Ashish Mathew
• Jaehyun Park
• Prachetaa Raghavan
• TongKe Xue
• email cs161-spr1213-staff@lists.stanford.edu

when and where:

• classes: Mondays and Wednesdays, 4:15-5:30pm, in Braun auditorium, Mudd Chemistry
• office hours: schedule

references: the textbook is

• Jon Kleinberg and Eva Tardos, Algorithm Design. Addison-Wesley

homeworks:

• late policy: there is no late policy, late assignments will not be accepted. If you are unable to submit your homework because of extenuating circumstances such as a family of medical emergency, talk to Luca about it.

• collaboration versus cheating: make sure you are familiar with our policy on collaboration

• how to write your homework solution:

  Write your name, student ID, homework number, and problem number on top of every page.

  Write legibly. Your TAs may mark your solution as incorrect if they cannot read your handwriting.

  Be clear. Ambiguous statements will be interpreted at the discretion of the TA. (If the TA's interpretation of an ambiguous statement differs from what you wanted to say, this is not ground for a regrade.)

  The description of your proofs should be as clear as possible (which does not mean long -- in fact, typically, good clear explanations are also short.)

• submitting the homework: TBA

• regrades: For regrades, you will need to submit a written justification and drop by during office hours to defend your solutions. Your TAs reserve the right to regrade the whole problem set.

• piazza For all homework questions (that do not divulge solutions), post to piazza

schedule of classes

1. April 1. Introduction and examples
   Readings: chapter 1 and 2
   (lecture notes)

2. April 3. Divide and conquer
   Readings: 5.1, 5.5
   (lecture notes)

3. April 8. Master theorem
   Readings: 5.2, lecture notes
   (lecture notes)

4. April 10. Median in linear time
   Readings: lecture notes
   (lecture notes)

5. April 15. Graphs, undirected connectivity, BFS
   Readings: 3.1, 3.2, 3.3
   (lecture notes)

6. April 17. Directed connectivity, DFS, topological sort
   Readings: 3.5, 3.6
   (lecture notes)

7. April 22. Dijkstra's algorithm
   Readings: 4.4
   (lecture notes) (animation)

8. April 24. Shortest paths with negative edge-lengths
   Readings: 6.8
   (lecture notes)

9. April 29. All-pairs shortest paths, independent set in paths, knapsack
   Readings: 6.8, 6.4
   (lecture notes: same as lecture 8)

10. May 1. Sequence Alignment
    Readings: 6.6, 6.7

11. May 6. Minimum spanning tree, Union-find data structures
    Readings: 4.5, 4.6

12. May 8. The maximum flow problem
    Readings: 7.1, 7.2
    (lecture notes)

13. May 13. Cuts and flows
    Readings: 7.1, 7.2

14. May 15. Cuts and flows
    Readings: 7.1, 7.2
    (lecture notes)

15. May 20. Introduction to randomized algorithms
    Readings: 13.1, 13.2
    (lecture notes)

16. May 22. Randomized hashing
    Readings: 13.5
    (lecture notes)

    May 27: no class

17. May 29. NP-completeness
    Readings: chapter 8
    (lecture notes, sections 1-7)

18. June 3. Approximation algorithms
    Readings: 11.1, 11.2, 11.3

19. June 5. What's next: matching, linear programming, FFT, clustering

1. hw1.pdf (hw1.tex) : due 4pm Tuesday 4/9
2. hw2.pdf (hw2.tex) : due 4pm Tuesday 4/16
3. hw3.pdf (hw3.tex) : due 4pm Tuesday 4/23
4. hw4.pdf (hw4.tex) : due 4pm Tuesday 4/30
5. hw5.pdf (hw5.tex) : due 4pm Tuesday 5/7
6. hw6.pdf (hw6.tex) : due 4pm Tuesday 5/21
7. hw7.pdf (hw7.tex) : due 4pm Tuesday 5/28
8. hw8.pdf (hw8.tex) : due 4pm Tuesday 6/4
9. Practice Final

The final is on June 10 12:15-3:15 in Hewlett 200.