[ Course Schedule | Final | Homework Assignments | Resources ]

**Instructor:** David Eng (email: davideng at cs)

**Location and time:** Tuesday and Thursday 9:30 to 11:20 a.m., Gates B3

**Important!**
Sign up on Piazza for discussions and announcements.

We strongly encourage discussion and asking questions on Piazza. Questions to the course staff (that are not addressed to a specific person) can be sent using a private post in Piazza.

**Course Description**

This course will cover the basic approaches and mindsets for analyzing and designing algorithms and data structures. Topics include the following: 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. Possible additional topics: network flow, string searching.

**Prerequisites:** CS 103 or CS 103B; CS 109 or STATS 116.

**Requirements:** 6 homework assignments (60%) and a final exam (40%).

**There will be three late days.** (max of 2 per assignment).

**Teaching Assistants**

Sean Choi, *yo2seol at stanford*

Braden Hancock, *bradenjh at stanford*

Helen Jiang, *helennn at stanford*

Nishith (Nish) Khandwala, *nishith at stanford*

Sydney Li *sydli at stanford*

Barak Oshri *boshri at stanford*

Topics and readings for future lectures are tentative and may be changed as the course proceeds. The readings refer to the 3rd edition of CLRS (see Resources below), but older editions should be fine as well.

Tuesday |
Thursday |
Friday |

6/27 Algorithmic Analysis, Divide and Conquer I [Slides] [Sorting Notes] CLRS: Ch. 2.3, 3 |
6/29 Divide and Conquer II [Slides] [Recurrence Notes] [Select-k Notes] CLRS: Ch. 3, 9 |
6/30 Homework 1 released |

7/4 NO LECTURE |
7/6 Trees, linear time sorting [Slides] [Linear-time Sorting Notes] [Trees Notes] CLRS: Ch. 8.1, 8.2, 12 |
7/7 Homework 1 due Homework 2 released |

7/11 Randomized Algorithms I [Condensed Slides] [Slides] [Quicksort Notes] CLRS: Ch. 5, 7 |
7/13 Randomized Algorithms II [Condensed Slides] [Slides] [Hashing Notes] CLRS: Ch. 11 |
7/14 Homework 2 due Homework 3 released |

7/18 Graph Algorithms I [Condensed Slides] [Slides] [DFS/BFS Notes] [Dijkstra's Notes] CLRS: Ch. 22, 24.1, 24.3 |
7/20 Graph Algorithms II [Condensed Slides] [Slides] [Strongly Connected Components Notes] [Karger's Notes] CLRS: Ch. 22.5 |
7/21 Homework 3 due Homework 4 released |

7/25 Greedy Algorithms I [Condensed Slides] [Slides] [Greedy Notes] CLRS: Ch. 16.1, 16.2, 16.3 |
7/27 Greedy Algorithms II [Condensed Slides] [Slides] [MST Notes] CLRS: Ch. 23 |
7/28 Homework 4 due Homework 5 released |

8/1 Dynamic Programming I [Condensed Slides] [Slides] [BF/FW Notes] CLRS: Ch. 25.2, 15.1 |
8/3 Dynamic Programming II [Condensed Slides] [Slides] [DP Notes] CLRS: Ch. 15.4 |
8/4 Homework 5 due Homework 6 released |

8/8 Intractable Problems I [Condensed Slides] [Slides] |
8/10 Intracable Problems II [Condensed Slides] [Slides] |
8/13 Homework 6 due |

8/15 Max-flow, min-cut [Max-Flow Min-Cut Notes] |
8/17 Final Review [Final Review Notes] |
8/18 FINAL |

Midterm: There's no midterm.

Final: Friday, August 18 (Location: Dinkelspiel Auditorium, 8:30 a.m. to 11:30 a.m.)

The final is closed-book. In the final, you are allowed to bring two letter-sized double-sided page of notes that **you have prepared yourself**.

- [Practice Final] [Solutions] (Our final will most closely resemble this one.)
- [Autumn 2016] [Solutions]
- [Winter 2011]
- [Winter 2009]

- Homework 1 (released 6/30, due 7/7 at 11:59 p.m.). [PDF][LaTeX][Solutions]
- Homework 2 (released 7/7, due 7/14 at 11:59 p.m.). [PDF][LaTeX][Solutions]
- Homework 3 (released 7/14, due 7/21 at 11:59 p.m.). [PDF][LaTeX][Solutions]
- Homework 4 (released 7/21, due 7/28 at 11:59 p.m.). [PDF][LaTeX][Solutions]
- Homework 5 (released 7/28, due 8/4 at 11:59 p.m.). [PDF][LaTeX][Solutions]
- Homework 6 (released 8/4, due 8/13 at 11:59 p.m., edited 8/7). [PDF][LaTeX][Solutions]

- All assignments are posted on Fridays, and are due the next Friday at 11:59 p.m.
- All assignments must be submitted electronically as a PDF file using Gradescope (access code: 9GNVBM).
- All assignments should be typed using LaTeX, LyX, Microsoft Word, or a similar editor. For first time LaTeX users, see the resources section.
**Scanned handwritten assignments are not accepted.** - Each student is allowed to discuss the assignment (verbally) with any classmates enrolled in CS161. Each student should write and submit their own solution.
**Solutions must be written in your own words.**When you submit the assignment, you should indicate with whom you have discussed the solutions. - You are allowed to use textbooks and resources that are listed on this page.
You
**may not**google around hoping to find a similar problem worked out, but you may use other resources (like Wikipedia, other lecture notes, textbooks) that you find online. If you are using other resources, you must properly cite them, and you must prove any statement from them that you use. - You are not allowed to look for the answers for any of the homework assignments (online or otherwise). If you accidentally find a solution for a question, do not read it (if it is not too late), and indicate that clearly on your assignment (including where you found the solution).
- Please follow the honor code.

**Regrade Policy**

- For each assignment, regrade requests will open on Gradescope on Wednesday (after the grades have been published) and close on Sunday.
- Please provide a detailed explanation for your regrade request.
- Note that we may regrade any part of the assignment, and the new grade may be greater than, equal to, or less than the original grade.

The main textbook we use is:

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, *Introduction to Algorithms*, 3rd Edition, MIT Press

The book is available online through the Stanford library.

We will also occasionally use:

Jon Kleinberg, Éva Tardos, *Algorithm Design*, Pearson/Addison-Wesley

Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, *Algorithms*, McGraw-Hill Education

We strongly recommend typesetting solutions to the homework assignments using LaTeX. LaTeX provides a convenient way to produce high-quality documents and it is the standard used for typesetting computer science papers.

**Guide:** An introduction to LaTeX can be found here. Other guides can be
found at Wikibooks and NYU.

**Online environments:** If you do not wish to install LaTeX, ShareLaTeX and Overleaf are online environments that compile previews of your documents as you type and allow you to share documents with collaborators (this feature won't be useful in this course, though). As a Stanford student, you get a free Overleaf Pro account.

**LyX:** LyX is a version of LaTeX with graphical interface.

**Finding mathematical symbols:** The introduction mentioned above contains a table of mathematical symbols in LaTeX. Alternatively, consider Detexify.