Welcome to CS161!

**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 (Note that some office hours begin in week 3)
- Haden: 2:30pm-3:30pm on Tuesdays at Gates 132 (starting on July 7th)
- Billy: 4:00pm-6:00pm on Tuesdays at Gates B24 (starting on June 30th)
- Apaar: 3:00pm-5:00pm on Wednesdays at Y2E2 161 (starting on July 8th)
- Hao: 3:30pm-5:30pm on Thursdays at Clark Center S255 (starting on July 2nd)
- Neha: 6:00pm-8:00pm on Thursdays at Huang Basement (starting on July 2nd)
- Non-regular office hours (one-time)
~~Haden: 2:00pm-3:00pm at Gates 132 (only~~**on July 1st Wednesday**)- Haden: TBD 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 |
Posted on June 26 at 00:50am. Last updated on June 27 at 2:20pm. Please see Piazza post about HW1 updates here. |

HW 2
[pdf] |
July 10 at 4pm on Gradescope |
Posted on July 2 at 11:25pm. Last updated on July 2 at 11:25pm. Please see Piazza post about HW2 updates here. |

HW 3 | July 17 at 4pm on Gradescope | TBA. |

HW 4 | July 31 at 4pm on Gradescope | TBA. |

HW 5 | Aug 7 at 4pm on Gradescope | TBA. |

- There will be an in-class midterm and a final exam. (Locations to be announced.)
- Midterm: July 21 (11:00am -- 12:50pm).
- Final Exam: August 15 (8:30am -- 11:30am). (as specified by registrar 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). [KT: Ch. 6.1-6.4, 6.6] [Readings (KT): Ch. 2.5, 4.2, 4.4-4.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 [KT: Ch. 6.8, 2.4, 5.1-5.5] [Suggested Exercises (KT): 5.1, 5.2, 5.4, 5.6] |

05 [DRAFT] | 7/7/2015 | Data Structures / Intro to Network Flow and Max-Flow Min-Cut Theorem [KT: Ch. 7.1-7.3] [Suggested Exercises (KT): 7.1, 7.2, 7.3] |

06 [DRAFT] | 7/9/2015 | Applications of Network Flow: Bipartite Matching, Disjoint Path Problem, Circulation with Demands [KT: Ch. 7.5-7.7] [Suggested Exercises (KT): 7.8, 7.13, 7.22] |

07 [DRAFT] | 7/14/2015 | Applications of Network Flow: Survey Design, Airline Scheduling, Image Segmentation, Project Selection [KT: Ch. 7.8-7.11] [Suggested Exercises (KT): 7.20, 7.22, 7.29] |

08 | 7/16/2015 | Topics TBA. (Possibly, review for midterm). [KT: TBA] [Suggested Exercises: Practice Midterm (TBA)] |

09 | 7/21/2015 | Midterm (In-class) at 11:00am. [Coverage: Lectures 1 up to 8 and Homework 1 up to 3, inclusive. (subject to change and will be finalized 1 week prior to exam.) ] |

10 | 7/23/2015 | Computational Tractability: P vs. NP and Reductions. [KT: Ch. 8; more to be announced later ] |

11 | 7/28/2015 | NP-completeness and reductions. [KT: Ch. 8; more to be announced later ] |

12 | 7/30/2015 | Randomized Algorithms. (Details to be announced.) [KT: Ch. 13.1-13.5 ] |

13 | 8/04/2015 | Approximation Algorithms. (Details to be announced.) [KT: Ch. 10.1, 11.1, 11.3 ] |

14 | 8/06/2015 | Approximation Algorithms.(Details to be announced.) [KT: Ch. 11.8, 11.6 ] |

15 | 8/11/2015 | TBA. (Details to be announced.) [KT: TBA ] |

16 | 8/13/2015 | Extra Topics. Class Review. [KT: TBA ] |

8/15/2015 | Final Exam at 8:30 am. [Coverage: Lectures 1 to 15 (inclusive) and all homework assignments.] |