Department of Computer Science
Stanford University
CS 161 - Introduction to Algorithms and Data Structures
Summer 2008
Instructor: Dave Kauchak
e-mail: [first_initial][last_name]@stanford.edu
office hours: Monday 11-12am, Gates 195
TA: Neha Kumar
e-mail: [first_name][last_initial]@stanford.edu
Homework submission e-mail: [first_name].[last_name]@gmail.com
office hours: Tuesday 10-12am, Bytes Cafe, Packard building
location: Gates B03
web page: http://www.stanford.edu/class/cs161/
discussion board: http://groups.google.com/group/su_cs161_sum08
scores:
Individual: coursework
Class anonymized: scores
textbook:
- Introduction to Algorithms, 2nd edition (2007). Thomas H. Cormen, Charles E. Leiserson Ronald L. Rivest and Clifford Stein.
- Also useful: Algorithms (2008). Sanjoy Dasgupta, Christos Papadimitiou and Umesh Vazirani.
- Also useful: Algorithm Design (2006). Jon Kleinberg and Eva Tardos.
Announcements
I've posted a student's solution that did well on homework 5 here
There will be a review session for the final: Aug. 14, 4:00-5:30pm - Skilling 191
Homework 6 is available and due Wednesday, Aug. 13 before class.
I've posted some notes for greedy algorithms and dynamic programming from the winter 08 class thanks to Tim Roughgarden
I've posted a student's solution that did well on homework 4 here
I've posted a student's solution that did well on homework 3 here
Homework 5 is available and due Wednesday, Aug. 6 before class.
I've posted the scores we have so far here and will update regularly
Homework 4 is available and due Wednesday, July 30 before class.
No office hours this week (July 21,22). If you have questions/problems e-mail Neha or Dave
I've posted a student's solution that did well on homework 2 here
I've posted a student's solution that did well on homework 1 here
Here is a set of sample midterm questions
The optional (i.e. won't be graded) homework on hashtables is available
There will be a review session for the midterm: July 17, 4:15-5:05pm - Skilling 193
Point values have been added to homework 3. For final grades, all homeworks are equally weighted.
Homework 3 is available and due Wednesday, July 16 before class.
E-mailed homework should be sent to Neha's gmail account (see above)
Homework 2 is available and due Wednesday, July 9 before class.
Neha's office hours on Tuesday July 1 will be moved to Thursday, July 3 from 10-12am.
Homework 1 is available and due Thursday, July 3 by midnight.
Schedule
Note: This is a tentative schedule and is subject to change
| Date | Topic | Reading | Notes/Handouts |
|---|
| 6/25 | Admin. material, Introduction | Ch. 1, 2 | Admin. material, Introduction notes |
| 6/30 | O-notation | Ch. 3 | BigO |
| 7/2 | Recurrences | Ch. 4.1-4.3 | Recurrences |
| 7/7 | Quicksort, Randomized algorithms | Ch. 7,8.1-8.3 | Quicksort |
| 7/9 | Elementary data structures, Heaps | Ch. 6, 10 | Heaps |
| 7/14 | Binary search trees, B-Trees | Ch. 12,18 | Search Trees |
| 7/16 | Hashtables | Ch. 11, except 11.3.3 & 11.5 | Hashtables |
| 7/21 | Midterm | | |
| 7/23 | Graph algorithms | Ch. 22 | Graphs |
| 7/28 | Minimum spanning trees and
single source shortest paths | Ch. 23, 24 | Graphs2 |
| 7/30 | Greedy algorithms | Ch. 16, except 16.4 | Greedy |
| 8/4 | Dynamic programming | Ch. 15, except 15.5 | Dynamic Programming |
| 8/6 | String algorithms | Ch. 32, except 32.4 | Strings |
| 8/11 | NP Completeness | Ch. 34 | NP-Complete |
| 8/13 | Advanced algorithms/Review | | Review |
| 8/16 | Final - 3:30-6:30 pm, Gates B03 | | |