CS 161: Design and Analysis of Algorithms (Spring 2017)

[ Course Schedule | Midterm and Final | Homework Assignments | Recitations | Resources ]

Instructor: Mary Wootters (email: marykw at cs)

Location and time: Monday and Wednesday 3:00 PM - 4:20 PM, Hewlett 200

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: 7 homework assignments (35%), a midterm (25%), and a final exam (40%).
There will be no late days. However, we will drop your lowest homework grade.
Note: In order to compute scores on the homework (in deciding which to drop and for averaging), we will normalize the scores by the number of points possible. That is, if 40 points were possible on the homework and you scored a 35, this would count as 35/40 = 0.875.

Teaching Assistants
David Eng, dkeng at stanford
Luna Frank-Fischer [Head TA], luna16 at stanford
Neha Gupta nehgupta at stanford
Jessica Su jtysu at stanford
Daniel Wright dlwright at stanford
Andi Yang, andiy at stanford
Wilbur Yang, wilbury at stanford

Sign up for office hours on QueueStatus.

Course Schedule and Lecture Notes

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.

Midterm and Final

Midterm: Wednesday, May 10, in class (Hewlett 200, 3:00 pm - 4:20 pm) - [problems] [solutions]
Final: Friday, June 9, Hewlett 200, 3:30 pm - 6:30pm
Final Problems and Solutions

Both the midterm and final are closed-book. In the midterm, you are allowed to bring one letter-sized double-sided page of notes, that you have prepared yourself. In the final, you are allowed to bring two letter-sized double-sided page of notes that you have prepared yourself.

The following practice exams are posted here as a resource; the material covered is similar to what we covered this quarter, but not identical.

Practice Midterm 1
Solutions to the Practice Midterm 1
Practice Midterm 2
Solutions to the Practice Midterm 2

Finals from Previous Years

The following final exams are taken from previous offerings of the class. They are posted here as a resource, but the material covered in them may differ what the material covered this quarter, and their structure may differ from this quarter's final exam.

Final Exam 2016
Final Exam 2016 Solutions

Homework Assignments

• Homework 1 (released 4/7, due 4/14 at 3pm). [pdf] [raw LaTeX file] [solutions]
• Homework 2 (released 4/14, due 4/21 at 3pm). [pdf] [raw LaTeX file] [solutions]
• Homework 3 (released 4/21, due 4/28 at 3pm). [pdf] [raw LaTeX file] [solutions]
• Homework 4 (released 4/28, due 5/8 at 3pm). [pdf] [raw LaTeX file] [solutions]
  
• Homework 5 (released 5/12, due 5/19 at 3pm). [pdf] [raw LaTeX file] [solutions]
• Homework 6 (released 5/19, due 5/26 at 3pm). [pdf] [raw LaTeX file] [solutions]
• Homework 7 (released 5/26, due 6/2 at 3pm). [pdf] [raw LaTeX file] [solutions]
• There is no Homework 8. However, if you want some practice on Minimum Cut and Maximum Flow, here are some practice problems (with solutions) from Kleinberg and Tardos: Solved exercise 1 here on randomized algorithms in graphs and Solved exercises 1 and 2 here on min-cut/max-flow.

Submission Instructions and Policies

• All assignments are posted on Fridays, and are due the next Friday at 3pm.
• All assignments must be submitted electronically as a PDF file using Gradescope (access code: MWRJ89).
• 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.
• Late homeworks will not be accepted. However, we will consider your highest 6 (out of 7) homework grades when computing your final course grade.

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.

Recitations

We hold recitation sections in order to review some of the material and solve additional exercises with the students in smaller groups. The sections are optional but highly recommended. The schedule (including locations) of the recitation sections appears in the office hours calendar. Each section covers the material of the previous week except for Friday sections that cover the material of the same week.

Exercises

• Section 1: Loop and recursion invariants, weak and strong induction.
• Section 2 [problems] [solutions]: Selection, big-O, and recurrences.
• Section 3: Randomized algorithms.
• Section 4 [problems] [solutions]: Universal hash functions, randomly built binary search trees.
• YouTube series on red-black trees: Introduction, Rotations, Insertions 1, Insertions 2
• Section 5: Midterm review.
• Section 6 [problems] [solutions]: Graphs.
• Section 7: Dynamic programming.
• Section 8 [problems] [solutions]: Greedy algorithms.
• Final review: [Part 1]

Resources

Textbooks

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

Homework Resources

• Expected level of detail: Your homework solutions should make it clear that you understand what's going on. This means that they should have enough detail to convince the grader that your solution is correct; but they needn't have so much detail that it obfuscates the main points. This is a difficult balance to strike. To help you, here is an example of what we are looking for on the homework assignments.
• General advice: Here are a few pieces of general homework advice:
  • Read the submission instructions and policies above.
  • Read the submission instructions and policies above. Seriously, do it.
  • Look over the problems early. Algorithm design takes time, and even simple algorithms can be surprisingly tricky to develop. We suggest reading over all the problems as soon as the problem set goes out so that you will have the time to play around with them over the course of the week.
  • Work on your own before working in a group or attending office hours. Although you are allowed to work in groups, we strongly recommend not doing so until you have already thought about each of the problems and tried out various solutions. The problem sets tend to have solutions that are not particularly complicated but which require some insight to discover. If you immediately start working on the problem sets in a group, you will miss out on the opportunity to come up with these insights on your own.

LaTeX Resources

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.