Welcome to CS161!

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

**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.

- 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 - Sean: Remote office hours (link) for SCPD students (
**starting on July 14**) - 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.

- 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 [pdf] |
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
[pdf] |
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
[pdf] |
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
[pdf] |
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
[pdf] |
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 [pdf] |
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.

- 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.

- 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%

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.) |