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, and Sean Choi
- Weekly Office Hours (Note that some office hours begin in week 3)
- Billy: 2pm-4pm on Tuesdays at Gates B24 (
**starting on June 30th**) - Apaar: 3pm-5pm on Wednesdays at Y2E2 161 (
*starting on July 8th*) - Neha: 6pm-8pm on Thursdays at Huang Basement (
**starting on July 2nd**) - Haden: 3:30pm-4:30pm on Thursdays at Gates 132 (
*starting on July 9th*) - Non-regular office hours (one-time)
- Haden: 4:30pm-5:30pm at Gates 132 (
**on July 2nd**)

**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 six homework assignments.
- We will drop the lowest score of yours.
- You will submit your solutions on Scoryst: https://scoryst.com/enroll/ljakqAxceJ/
- Late submissions will NOT be accepted.
- To get yourself familiar with Scoryst, we recommend that you submit a blank solution for HW0 on Scoryst.
- Homework problems and solutions:

HW No. | Due Date | Comments |
---|---|---|

HW 0 [pdf] |
June 30 at 4pm on Scoryst |
Homework 0 will NOT be graded. You may submit your solution on Scoryst 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 Scoryst |
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 | TBA. | TBA. |

HW 3 | TBA. | TBA. |

HW 4 | TBA. | TBA. |

HW 5 | TBA. | TBA. |

HW 6 | TBA. | 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.

Lecture No. | Date | Topics and Reading |
---|---|---|

01
[PDF]
[ VIDEO ] |
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]
[ VIDEO ] |
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 [DRAFT] |
6/30/2015 | Dynamic Programming: Weighted Interval Scheduling, Knapsack Problem and Sequence Alignment [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 | 7/2/2015 | Bellman-Ford Algorithm / Intro to Divide and Conquer: Merge Sort and Master Method [KT: Ch. 6.8, 2.4, 5.1-5.3] |

05 | 7/7/2015 | More Divide and Conquer: Closest Pair, Integer Multiplication / Data Structures [KT: Ch. 5.4-5.5] |

06 | 7/9/2015 | Intro to Network Flow: Ford-Fulkerson Algorithm and Max-Flow Min-Cut Theorem [KT: Ch. 7.1-7.2] |

07 | 7/14/2015 | Applications of Network Flow: Matching, Disjoint Path Problem [KT: Ch. 7.5-7.6] |

08 | 7/16/2015 | Extension of Network Flow: Circulation and Demands / Image Segmentation Problem [KT: Ch. 7.7, 7.10] |

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