CS 161 - Design and Analysis of Algorithms

Summer 2012

Instructor: Mark Zhandry
Course Assistants: Tarun Singh
Jun Yu
Office Hours:
Mark Zhandry:     Wednesday 12-2PM Gates 494
Tarun Singh: Monday, Thursday 4-6PM     Gates B24A
Jun Yu: Wednesday 4-8PM Gates B24B
Contact: cs161-summer2012-staff@lists.stanford.edu
Piazza: Piazza for CS 161
Lectures: MWF 2:15-3:30 at Skilling Auditorium
Textbook: Algorithm Design by Kleinberg & Tardos
Important Dates: First Day of Class: Monday, June 25th
Midterm: Wednesday, July 25th in class
Last Day of Class: Wednesday, August 15th
Final Exam: Friday, August 17th 12:15-3:15PM. Location: Skilling Auditorium

Topic Schedule

Week LectureDate Topic Details Pages Homework
1 1 June 25Intro/Big Oh 29-42
2 June 27Data Structures I Lists, Stacks, Queues, Hash Tables N/A HW 1 out
3 June 29Data Structures II BSTs, Self-Balancing Trees, Priority Queues N/A
2 4 July 2 Graph Search I BFS, DFS, Undirected Connectivity 73-94
July 4 Holiday HW 2 out
5 July 6 Graph Search II Directed Connectivity, Topological Sorting 97-104 HW 1 due
3 6 July 9 Greedy Algorithms I Dijsktra 137-142
7 July 11Greedy Algorithms II MSTs 116-157HW 3 out
8 July 13Greedy Algorithms III More MSTs, Interval Scheduling HW 2 due
4 9 July 16Greedy Algorithms IV Huffman Encoding, Set Cover 161-177
10 July 18Divide & Conquer I Recurrences, (Matrix) Multiplication, Master Method 231-234
11 July 20Divide & Conquer II Merge Sort, Quick Sort, Median 210-220HW 3 due
5 12 July 23Divide & Conquer III FFT 234-242
July 25Midterm In Class HW 4 out
13 July 27 Divide & Conquer IV FFT continued, Multiplication revisited
6 14 July 30 Dynamic Programming I Weighted Interval Scheduling 251-260
15 Aug 1 Dynamic Programming II Sequence Alignment 278-284HW 5 out
16 Aug 3 Dynamic Programming III All Pairs Shortest Paths, TSP 290-307HW 4 due
7 17 Aug 6 Linear Programming I Flows 337-357
18 Aug 8 Linear Programming II Reductions N/A
19 Aug 10 NP-Complete I Definitions, SAT, 3SAT 451-495HW 5 due
8 20 Aug 13 NP-Complete II More NP-Complete Problems, Coping with NP-Complete 499-649
21 Aug 15 Beyond CS 161 N/A
Aug 17 Final Exam 12:15-3:15PM, Skilling Auditorium




Lecture Notes


Contact Information

This course uses Piazza, which is the main form of communication regarding the class. If you have any questions that may be of interest to other students, please post them on Piazza. The staff checks Piazza regularly, and other students can answer your questions as well. Please do not post any answers to homework problems until solutions have been released.

If your question is personal in nature or of no interest to other students, you can use the staff email: cs161-summer2012-staff@lists.stanford.edu. If you choose to email the staff, please use this address instead of emailing us directly.


There are a total of five homework assignments. Homework assignments will be available on this website each Wednesday, and are due by the start of class at 2:15PM on the following Friday. Exceptions: No homework is due the week of the midterm or the last week of classes.

Late Policy: Every student is allowed one extension of up to 72 hours. In other words, for exactly one homework assignment, you may choose to turn your solutions in by the start of class at 2:15PM on the Monday after the homework was due. Outside of this extension, no late homeworks will be accepted.

Collaboration: You may work on homeworks in groups of up to three students. However, every student must write up their own solutions in their own words. If you choose to collaborate, put the names and Stanford ID numbers of your collaborators on your submission.

Submitting: You have three options for submitting your homework solutions: in class, during office hours, or by emailing cs161-summer2012-submissions@lists.stanford.edu.

Requirements for all homework submissions: Your name and Stanford ID number must be at the top of the first page of your solutions. In addition, all answers to problems and subproblems must be in order.

Requirements for electronic submissions: If you submit an electronic copy of your solutions, it must be typed, preferably in LaTex. Scans of handwritten work will not be accepted. Exception: we understand that many SCPD students cannot make it to class or office hours to turn in their homework physically, so for SCPD students only, emailing a scan of your homework solutions is acceptable as long as we can read it.

Requirements for paper submissions: If you submit a physical copy of your solutions, it is still encouraged but not required that you type up your solutions in LaTex. However, if you write your solutions by hand, your handwriting must be legible. Further, all physical submissions must be stapled as a single document (no paper clips, binder clips, or loose pages).

Submissions failing to meet the criteria above risk receiving no credit.

Regrades: Regrade requests must be made within one week of the homework being returned, with a written explanation. We reserve the right to regrade the entire assignment, which could potentially result in a lower score than the original.


There is one midterm and one final exam. The midterm will be held in class on Wednsday, July 25, and the final will be held on Friday, August 17 from 12:15-3:15PM in Skilling Auditorium. If you have any conflicts with the midterm, let the staff know by the end of the second week of classes, and special arrangements can be made. All students must be present for the final exam.

Exams will be open-book, open-notes, with questions similar in style to the homework assignments.


Grades will be assigned as follows:

Homeworks: 50%
Midterm: 20%
Final: 30%