CS 161 - Algorithms - Spring 2013
[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
Trevisan, Gates 474, Tel. 650 723-8879, email trevisan at stanford dot edu
- Maurizio Caligaris
- Jeffrey Chen
- Phil Chen
- Mike Chrzanowski
- Michael Kim
- Ashish Mathew
- Jaehyun Park
- Prachetaa Raghavan
- TongKe Xue
- email email@example.com
when and where:
You can ask questions using piazza
- classes: Mondays and Wednesdays, 4:15-5:30pm, in Braun auditorium, Mudd Chemistry
- office hours: schedule
grading: the homeworks are worth 50% of the grade, the final 30% and the midterm 20%. We will drop the lowest homework grade in computing the homework grade average.
- Jon Kleinberg and Eva Tardos,
- 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
- 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
- April 1. Introduction and examples
Readings: chapter 1 and 2
- April 3. Divide and conquer
Readings: 5.1, 5.5
- April 8. Master theorem
Readings: 5.2, lecture notes
- April 10. Median in linear time
Readings: lecture notes
- April 15. Graphs, undirected connectivity, BFS
Readings: 3.1, 3.2, 3.3
- April 17. Directed connectivity, DFS, topological sort
Readings: 3.5, 3.6
- April 22. Dijkstra's algorithm
- April 24. Shortest paths with negative edge-lengths
- April 29. All-pairs shortest paths, independent set in paths, knapsack
Readings: 6.8, 6.4
(lecture notes: same as lecture 8)
- May 1. Sequence Alignment
Readings: 6.6, 6.7
- May 6. Minimum spanning tree, Union-find data structures
Readings: 4.5, 4.6
- May 8. The maximum flow problem
Readings: 7.1, 7.2
- May 13. Cuts and flows
Readings: 7.1, 7.2
- May 15. Cuts and flows
Readings: 7.1, 7.2
- May 20. Introduction to randomized algorithms
Readings: 13.1, 13.2
- May 22. Randomized hashing
May 27: no class
- May 29. NP-completeness
Readings: chapter 8
(lecture notes, sections 1-7)
- June 3. Approximation algorithms
Readings: 11.1, 11.2, 11.3
- June 5. What's next: matching, linear programming, FFT, clustering
- hw1.pdf (hw1.tex) : due 4pm Tuesday 4/9
- hw2.pdf (hw2.tex) : due 4pm Tuesday 4/16
- hw3.pdf (hw3.tex) : due 4pm Tuesday 4/23
- hw4.pdf (hw4.tex) : due 4pm Tuesday 4/30
- hw5.pdf (hw5.tex) : due 4pm Tuesday 5/7
- hw6.pdf (hw6.tex) : due 4pm Tuesday 5/21
- hw7.pdf (hw7.tex) : due 4pm Tuesday 5/28
- hw8.pdf (hw8.tex) : due 4pm Tuesday 6/4
- Practice Final
The final is on June 10 12:15-3:15 in Hewlett 200.