Welcome to CS161!
(This class ended on 08/15/2015. For future offerings, please visit http://cs.stanford.edu/courses/ .)

Class Information

  • Instructor: Haden Hooyeon Lee (PhD student in computer science)
  • Lecture: Tuesdays and Thursdays 11:00am - 12:50pm
  • Location: Gates B03
  • Course Description
    Worst and average case analysis. Recurrences and asymptotics. Efficient algorithms for sorting, searching, and selection. Data structures: binary search trees, heaps, hash tables. Algorithm design techniques: divide-and-conquer, dynamic programming, greedy algorithms, amortized analysis, randomization. Algorithms for fundamental graph problems: minimum-cost spanning tree, connected components, topological sort, and shortest paths. Introduction to network flows and graph matchings.
  • Prerequisites
    Before taking CS 161, it is important that you complete CS 103 and CS 109/STATS 116, or the equivalents. In particular, you should be comfortable with proofs, discrete mathematics, basic graph and set theory, and introductory probability theory.
  • Required Textbook: Algorithm Design by Kleinberg and Tardos (KT).
    Optional Textbook: Introduction to Algorithms, 3rd Edition by Cormen, Leiserson, Rivest, and Stein (CLRS) by the MIT Press. (Older editions are fine.)
  • Review Material:
    This class assumes that you are familiar with the topics covered in prerequisite classes (see above). To review some of the topics, we provide an optional homework (homework #0) which will NOT be graded. We will post solutions soon after the class begins.

Teaching Staff (Course Assistants)

  • Apaar Sadhwani, Billy Jun, Neha Nayak, Sean Choi, and Hao Su.
  • Weekly Office Hours
  • No office hours during the midterm week (July 21 - July 25). (See below for Haden's office hours on July 20.)
    • Haden: 2:30pm-3:30pm on Tuesdays at Gates 132 (resuming after July 25th)
    • Billy: 4:00pm-6:00pm on Tuesdays at Gates B24 (resuming after July 25th)
    • Apaar: 3:00pm-5:00pm on Wednesdays at Y2E2 161 (resuming after July 25th)
    • Neha: 2:00pm-4:00pm 6:00pm-8:00pm on Thursdays at Huang Basement (resuming after July 25th)
    • Hao: 4:00pm-6:00pm 3:30pm-5:30pm on Thursdays at Clark Center S255 (resuming after July 25th)
    • Weekly Remote Office Hours
  • Non-regular office hours (one-time)
    • Haden: 2:00pm-3:00pm at Gates 132 (only on July 1st Wednesday)
    • Haden: 4pm-6pm at Gates 132 (only on July 20th)


  • Please do NOT send emails to instructor or CAs. Questions via email will NOT be answered.
  • If you have questions or comments, use Piazza. https://piazza.com/stanford/summer2015/cs161
  • If you need privacy, you can make a private post that is visible only to teaching staff (but we may ask you to make your post public if we think it's more appropriate that way).
  • If you need special accommodations (as required by the OAE), you must obtain a letter from the OAE first, and contact the instructor as soon as possible.

Grading: Homework and Exams

Homework Assignments
  • There will be five six homework assignments.
  • We will drop the lowest score of yours.
  • You will submit your solutions via Gradescope: https://gradescope.com/courses/1091/.
  • Late submissions will NOT be accepted.
  • To get yourself familiar with Gradescope, we recommend that you submit a blank solution for HW0 on Gradescope.
  • Homework problems and solutions:
  • HW No. Due Date Comments
    HW 0
    June 30 at 4pm on Gradescope Homework 0 will NOT be graded.
    You may submit your solution on Gradescope to get yourself familiar with the tool.
    [ Solution ] If you find any error(s) in solution, please report on Piazza.
    HW 1
    July 3 at 4pm on Gradescope Grades released on July 9 at 3:20pm. (See stats here.)
    Please see Piazza post about HW1 updates here.
    [ Solution ] If you find any error(s) in solution, please report on Piazza (use the link above).
    HW 2
    July 10 at 4pm on Gradescope Posted on July 2 at 11:25pm.     Last updated on July 5 at 4:30pm.
    Please see Piazza post about HW2 updates here.
    [ Solution ] If you find any error(s) in solution, please report on Piazza (use the link above).
    HW 3
    July 17 at 4pm on Gradescope Posted on July 9 at 11:05pm.     Last updated on July 15 at 9:00am.
    Please see Piazza post about HW3 updates here.
    [ Solution ] If you find any error(s) in solution, please report on Piazza (use the link above).
    HW 4
    July 31 at 4pm on Gradescope Posted on July 23 at 10:40pm.     Last updated on July 23 at 10:40pm.
    Please see Piazza post about HW4 updates here.
    [ Solution ] If you find any error(s) in solution, please report on Piazza (use the link above).
    HW 5
    Aug 7 at 4pm on Gradescope Posted on July 31 at 8:00am.     Last updated on Aug 1 at 6:00pm.
    Please see Piazza post about HW5 updates here.
    [ Solution ] If you find any error(s) in solution, please report on Piazza (use the link above).
  • There will be an in-class midterm and a final exam. (Location: Gates B03.)
  • Midterm: July 21 (11:00am -- 12:50pm).
  • Final Exam: August 15 (8:30am -- 11:30am). (See information here.)
  • No alternate exam will be given, so plan accordingly.
Policy on collaboration and outside sources:
  • When solving the homework problems, you may consult the following sources: lecture videos and slides / CLRS and KT textbooks / Piazza.
  • You may also talk to student collaborators and the teaching staff, but you should write up your solution independently.
  • If you collaborate with other students, state their names on your homework.
  • If you use information from the web, write down the links.
  • Cite all sources.
Grading Policy
  • Late homework will NOT be accepted.
  • Since we drop the lowest homework grade, we will not grant any extensions.
  • Your final grade will be computed roughly as follows:
    • Homework: 50%
    • Midterm: 20%
    • Final: 30%
Stats on Homework and Exams:
  • HW 1 stats: HERE
  • HW 2 stats: HERE
  • HW 3 stats: HERE
  • HW 4 stats: HERE
  • HW 5 stats: HERE
  • Midterm stats: HERE (Updated on July 28 at 4pm after all regrades are completed.)
  • Final stats: HERE
  • All but final stats: HERE

Lecture Schedule (subject to change)

KT refers to Kleinberg and Tardos.
Lecture slides will be uploaded at least an hour before each lecture.
Note that the slides may be updated afterwards.
Final version of lecture slides will be uploaded soon after each lecture ends.
Link to all lecture VIDEOS.

Lecture No. Date Topics and Reading
01 [PDF] 6/23/2015 Introduction / Big-Oh Notation / Intro to Greedy Algorithms
[Readings (KT): Ch. 1, 2.1-2.4, 4.1-4.2] [Suggested Exercises (KT): 1.5, 1.8, 2.3, 2.5, 4.5.]
02 [PDF] 6/25/2015 More Greedy Algorithms: Dijkstra and Heap, Minimum Spanning Tree and Union-Find
[Readings (KT): Ch. 2.5, 4.2, 4.4-4.6] [Suggested Exercises (KT): 4.8, 4.11, 4.13, 4.21]
03 [PDF] 6/30/2015 Dynamic Programming: Five Problems (WISP, SLSP, Subset-Sum, Sequence Alignment, and Bellman-Ford Algorithm).
[Readings (KT): Ch. 6.1-6.4, 6.6] [Suggested Exercises (KT): 6.6, 6.11, 6.17, 6.19, 6.28]
04 [PDF] 7/2/2015 Bellman-Ford Algorithm / Divide and Conquer: Merge Sort, Counting Inversion, Master Method, Closest Pair Problem, and Integer Multiplication Problem
[Readings (KT): Ch. 6.8, 2.4, 5.1-5.5] [Suggested Exercises (KT): 5.1, 5.2, 5.4, 5.6]
05 [PDF] 7/7/2015 Data Structures / Intro to Network Flow
[Readings (KT): Ch. 7.1-7.3] [Suggested Exercises (KT): 7.1, 7.2, 7.3]
06 [PDF] 7/9/2015 Max-Flow Min-Cut Theorem / Applications of Network Flow: Bipartite Matching, Disjoint Path Problem, Circulation with Demands
[Readings (KT): Ch. 7.3, 7.5-7.7] [Suggested Exercises (KT): 7.8, 7.13, 7.22]
07 [PDF] 7/14/2015 Applications of Network Flow: Survey Design, Airline Scheduling, Image Segmentation, Project Selection (optional)
[Readings (KT): Ch. 7.8-7.10; 7.11 is optional] [Suggested Exercises (KT): 7.20, 7.22, 7.29]
08 [PDF] 7/16/2015 Review for midterm. (come and ask questions, if you have any.)
09 7/21/2015 Midterm (In-class) at 11:00am.
See here for details.
[ Practice Midterm (Solution) ] [ Midterm Solution (Report errors here.) ]
10 [PDF] 7/23/2015 Computational Tractability: Reductions, P vs. NP, and NP-complete problems.
[Readings (KT): Ch. 8.1-8.4] [Suggested Exercises (KT): 8.1, 8.2]
11 [PDF] 7/28/2015 NP-complete problems: TSP, Hamiltonian Cycle, 3-D Matching, Graph Coloring, Numerical Problems.
[Readings (KT): Ch. 8.5-8.8 and 8.10] [Suggested Exercises (KT): 8.5, 8.7, 8.41]
12 [PDF] 7/30/2015 Approximation: Load Balancing, Set Cover, VC (Rounding); Randomized APX: MAX 3-SAT.
[Readings (KT): Ch. 11.1, 11.3, 11.6; Ch. 13.4; (Ch. 13.12 and 13.3 may be helpful for those who need to review probability theory)] [Suggested Exercises (KT): 11.1, 11.3, 11.12, 13.3]
13 [PDF] 8/04/2015 Randomized Algorithm: MAX 3-SAT, Global Min-cut, Randomized Median Finding, Randomized Quick Sort
[Readings (KT): 13.4, 13.2, 13.5; (Ch. 13.12 and 13.3 may be helpful for those who need to review probability theory)] [Suggested Exercises (KT): 13.1, 13.3, 13.12. ]
14 [PDF] 8/06/2015 Finding small vertex cover; Approximation: VC (Pricing Method); P, NP, and co-NP.
[Readings (KT): Ch. 10.1; 11.4; 8.9] [Suggested Exercises (KT): 10.1]
15 8/11/2015 Review for Final Exam.
[Readings (KT): None. ] [Suggested Exercises: Practice Final Exam!]
16 8/13/2015 What is next after CS161: Topics you can study/learn after taking CS161.; Q and A
[Readings (KT): NONE! AWESOME!] [Suggested Exercises: Practice Final Exam!]
8/15/2015 Final Exam at 8:30 am. SEE HERE
[Coverage: Lectures 1 to 16 (inclusive) and all homework assignments.]
Practice Final Exam (Solutions) (If you find typos/errors, please use the Piazza post above to report/ask.)