CS 170
Efficient Algorithms and Intractable Problems

Professor Christos H. Papadimitriou
Professor Luca Trevisan
Fall 2016


Professor Christos Papadimitriou (OH Wednesday 5-6p in 689 Soda)
Professor Luca Trevisan (OH Wednesday 1:30-3p in 625 Soda)
All TA/reader office hours are at Soda 411.


Aaron Schild (OH Tuesday 3-5p)
Allen Tang (OH Thursday 1-2p)
Barak Gila (OH Monday 1-2p, Friday 12-1p)
Elan Frenkel (office hours Thursday 11-1p)
Liuxiao (Betty) Zhang (OH Friday 11-12p)
Mike Ambrose
Nathan Mandi (OH Tuesday 1-2p, Thursday 2-3p)
Peter Manohar (OH Monday 11-1p)
Rudy Laprade (OH Friday 1-2p)
Tony Duan (OH Monday 3-4p)
Wesley Hsieh (OH Wednesday 3-5p)


Albert Lin
Albert Pham
Aurelia Guy (OH Friday 12-1p)
Devyn Krevat
Jerry Cheng (OH Friday 12-1p)
Kevin Arifin (OH Thursday 2-3p, Friday 11-12p)
Nikhil Sharma
Patrick Yang (OH Friday 11-1p)
Richard Qian
Sabrina Shie (OH Monday 3-4p)
Sukyun Chung
Tina Zheng (OH Wednesday 3-5p)
Yuchen Jiang

TA office hours by day:

Monday: 11-2p, 3-4p
Tuesday: 1-2p, 3-5p
Wednesday: 3-5p
Thursday: 12-3p
Friday: 11a-2p, HW Party 2p-5p


TuTh 6:30pm-8:00pm, 1 Pimentel


You may go to any section, regardless of your registration.

Time # Location TA
Wed 9a 101 Etcheverry 3111 Allen
Wed 10a 103 Moffitt Library 103 Liuxiao (Betty)
Wed 11a 104 Hearst Field Annex B5 Tony
Wed 12p 105 Soda 320 Aaron
Wed 12p 106 Soda 405 Wesley
Wed 1p 107 Soda 310 Rudy
Wed 2p 108 Soda 405 Barak
Wed 2p 117 Soda 310 Rudy
Wed 3p 113 Soda 310 Barak
Wed 4p 109 Soda 405 Allen
Wed 4p 115 Latimer 105 Elan
Wed 4p 116 Barrows 104 Liuxiao (Betty)
Wed 5p 102 Etcheverry 3111 Elan
Wed 5p 110 Soda 405 Nathan
Wed 7p 118 Soda 320 Tony
Th 3:30p 111 Soda 310 Nathan
Th 4:30p 112 Soda 405 Aaron
Th 5p 114 Soda 320 Wesley


The lecture schedule is subject to change and will be revised as the course progresses.

# Date Topic Readings
1 8/25 Introduction, big-O notation, divide and conquer Chapter 0, Chapter 2.1, 2.2, 2.3
2 8/30 Divide and Conquer Chapter 2.4, 2.5, 2.6
3 9/1 Fast Fourier Transform Chapter 2.6
4 9/6 Graphs Chapter 3
5 9/8 Graphs Chapter 4
6 9/13 Greedy algorithms intro Minimum Spanning Trees Chapter 5.1
7 9/15 Greedy algorithms Chapter 5.2, 5.3, 5.4
8 9/20 No lecture -- Midterm 1
9 9/22 Dynamic Programming Chapter 6
10 9/27 Dynamic Programming Chapter 6
11 9/29 Dynamic Programming Chapter 6
12 10/4 Dynamic Programming Chapter 6
13 10/6 Linear Programming: intro + simplex overview Chapter 7.1
14 10/11 LP: simplex algorithm and duality Chapter 7.4, 7.6
15 10/13 LP: Network Flow Chapter 7.2; lecture notes
16 10/18 LP: Reductions and bipartite matching Chapter 7.3
17 10/20 Zero-sum games Chapter 7.5
18 10/25 Multiplicative weights lecture notes
19 10/27 Parallelism lecture notes
20 11/1 No lecture -- Midterm 2
21 11/3 Gradient descent lecture notes
22 11/8 Search Problems Chapter 8.1
23 11/10 NP-Completeness Chapter 8.2, 8.3
24 11/15 Coping with NP-Completeness Chapter 9
25 11/17 Coping with NP-Completeness Chapter 9
26 11/22 Streaming lecture notes, part 1
27 11/24 No lecture -- Thanksgiving
28 11/29 Streaming lecture notes, part 2
29 12/1 Last lecture


Every Monday evening, homework is posted on Piazza, and is due the following Monday by 10:00 PM. No late homeworks will be accepted for any reason. This policy aims to be fair and objective towards all students. Instead, we will drop your two lowest homework scores. Please avoid skipping homeworks, saving your drops in case a true emergency or crisis arises. (There will be a project near the end of the semester, which cannot be dropped.)

How to Format Homework: You can write your homework one of the following ways:

  1. Typeset your answers using LaTeX.
  2. Type your answers using a mainstream word processor.
  3. Neatly handwrite, then use a flatbed scanner or smartphone app (such as CamScanner) to produce a PDF. Do not simply take a photo and dump it into a PDF.
We strongly recommend LaTeX; see Piazza for tips on getting started. Each problem must start on a new page, and indicate the problem number. If a problem has multiple parts, they may be on the same page. You are encouraged to do homework in small groups; up to 4 students total. List your collaborators on the first page of your submission. If you have no collaborators, you must explicitly list "none."

How to Respond to Algorithm Problems: Oftentimes, a problem will ask you to find an algorithm. In this case, write your solution in the 4-part algorithm format detailed here.

How to Submit Homework: Submit homework via Gradescope; we will not accept it via any other format. The Gradescope homework cutoff may be set later than 10:00 PM at our discretion, but this grace period does not change our official policy: if you encounter an issue at 10:05 PM and Gradescope doesn't let you submit the homework, it will not be accepted. Thus, you should submit your homework well in advance to reduce the risk of technical issues. (You can even submit an incomplete homework as backup, if you're working on the homework all the way up until the deadline.)

Grading: You may request a regrade request (through Gradescope) within one week of when we release homework grades. Read the solutions carefully beforehand, and request a regrade only if you were graded inconsistently with the rubric. Make sure to clearly and politely explain why your solution was graded incorrectly. We reserve the right to regrade the whole homework assignment when you request a regrade, which could cause your score to change in either direction.

Homework solutions: The staff posts detailed solutions of the homework problems each week, often with multiple solution approaches and commentary. Make it a priority to carefully read the solutions and compare them with your own work. Thoroughly understanding the solutions is a critical step to mastering the material. As an added incentive, we will draw from the homework problems when we write the exams.

Homework parties: We will hold a weekly homework party in the Woz Lounge in Soda Hall, on Fridays from 2-5 PM. Homework parties are completely optional. This is an opportunity to find a group of other students to work together on the homework. Students are expected to form ad-hoc "pickup" homework groups, in the style of a pickup basketball game, and help others in their group. Most students do better at and learn more from the homework when they work in groups, and the HW party is a great opportunity to meet homework partners. In addition, course staff will be present to answer questions and help you.

Redemption files: It is important that you carefully read the posted solutions, even for problems you got right. To encourage this, you have the option of submitting a redemption file, a few paragraphs in which you explain, for each problem you choose to cover, what you did wrong and what the right idea was in your own words (not cutting and pasting from the solution!), and appending it to your homework. These will not be checked routinely, but we promise to look at them if they would make a difference in your grade (ie, you're close to a grade border. For example, as you review your solutions to HW1, you realize you had misunderstood question 3 and answered it incorrectly. You would write down what you just learned, and then submit it in your HW2 assignment the following week. Because these are mainly for your benefit, feel free to format them however is most useful for you.


We'll have weekly reading quizzes, due Tuesday at noon. We'll post a link to the quiz on Piazza at least a few days before the quiz is due. This semester, we're piloting Google Forms for our quizzes, so please bear with us if there are any initial technical difficulties. Quizzes should be done individually (not in groups like the homework), and they should not take very much time if you've read the textbook. The goal of the quizzes is to incentivize you to read the textbook before the lecture, which we've found helps students get the most out of lecture.


There will be two midterms and one final exam. The midterms will be given on Tuesdays September 20 and November 1, both at 6:30-8:30pm. The final exam will be Thursday, 12/15, 11:30-2:30pm.

All exams are mandatory. If you will be unable to attend any of these dates, you must contact the instructors via Piazza within one week of the first lecture. (We are currently aware of, and will accomodate, the conflicting final time with CS 161).


We will compute grades from a weighted average, as follows:

  • Homeworks: 30%
  • Midterm 1: 15%
  • Midterm 2: 15%
  • Final exam: 35%
  • Reading quizzes: 5%
We will drop the two lowest homework scores and the two lowest quiz scores. There is no clobbering policy for exams. However, we may take into account participation in Piazza, discussion, office hours, and HW party, as well as your redemption files and the trendline (looking favorably upon a student who showed improvement between midterms 1 and 2, and the final) if a student's grade is on the borderline between two grade categories.

Course Policies

Announcements: All announcements will be posted to Piazza. You are responsible for staying up-to-date with announcements made on Piazza.

Contact information: If you have a question, the best way to contact us is via Piazza. The staff (instructors, TAs, and readers) will check the site regularly, and if you use it, other students will be able to help you too. However, be very careful when asking about homework to avoid posting potential answers or hints. Please read the Homework FAQ post on Piazza before posting about homework. If in doubt, mark your question as private.

If your question is personal or not of interest to other students, mark it as private on Piazza. If you wish to talk with one of us individually in person, you are welcome to come to any of our office hours.

Collaboration: For each homework, we encourage you to collaborate in groups of at most 4 students total (It's OK to work informally with more students at a homework party). If you don't have a group to work with, come to the homework parties and form one! Clarifying concepts and discussing possible approaches to problems are good forms of collaboration. However, you must write up all solutions on your own, without ever looking at or copying any other student's solutions.

External sources: The textbook (including supplemental notes we will provide) as well as lecture should provide sufficient information to solve the homework problems. You may use the internet, other textbooks, etc. to provide context/supplementary information, but you should never attempt to look up solutions to the homework problems. If you find something useful from a source other than the textbook/notes (for example, a related theorem or explanation of a related problem), you must cite it in your solution (provide the URL). Of course, you should never copy or paraphrase any external source in your own solutions.

Cheating on homeworks or exams will be taken seriously. We refer you to the department's policy on academic dishonesty and the the campus honor code. We expect that most people can distinguish legitimate collaboration from cheating. If you're not sure whether a particular situation is cheating, ask an instructor. To be clear, the following behaviors are cheating:

You must ensure that your solutions will not be visible to other students. If you use Github or another source control system to store your solutions electronically, you must ensure your account is configured so your solutions are not publicly visible. Github offers free student accounts that allow you to keep your solutions private; please use one.

Prerequisites: The prerequisites for CS 170 are CS 61B and CS70. You will need to be comfortable with mathematical induction, big-O notation, basic data structures, and programming in a standard imperative language (e.g., Java or C).

Textbook: The required textbook is Algorithms (Dasgupta, Papadimitriou, and Vazirani) as our textbook. All chapter numbers and exercise numbers in this course refer to the official paper textbook, not the online version.

Electronics Policy: No cell phone, laptop, or other electronics use will be allowed in lecture: if you must use your phone or other device, please step outside. Academic studies have shown that students learn better when taking notes by hand rather than through a keyboard. The fact that it's impossible to write down everything the professor says is a feature, not a bug: it helps you learn by synthesizing the most important information.

Discussion sections: Attendance at discussion sections is expected, and sections may cover important material not covered in lecture. You may attend any discussion section, regardless of your registration. Outside of your discussion section, you should feel free to attend any of the staff office hours (not just your section TA's office hours) and ask any of us for help.

Don't be afraid to ask for help: Are you struggling? We'd much rather you approached us for help than gradually fall behind over the semester until things become untenable. Sometimes this happens when students are afraid of an unpleasant conversation with an instructor if they admit to not understanding something. We would much rather deal with your misunderstanding early than deal with its consequences later. Even if you are convinced that you are the only person in the class that doesn't understand the material, and that it is entirely your fault for having fallen behind, please overcome your feeling of guilt and ask for help as soon as you need it. Remember that the other students in the class are working under similar constraints -- they are taking multiple classes and are often holding down outside employment. In past semesters, TAs have met with many students for many reasons, like working through test-taking stress or getting extra help on specific topics. Don't hesitate to ask us for help -- helping you learn the material is what we're paid to do, after all!

Advice: The following tips are offered based on our experience with CS 170:

  1. Do the homeworks: The effort you spend on the homework assignments is the largest factor in your mastery of the material, and thus performance in the class as a whole.
    Also, regardless of how well you did on the homework, read the sample solutions, even for the problems you got right. You may well learn a different way of looking at the problem, and you may also benefit from emulating the style of the solutions.
  2. Don't wait until the last minute to start homeworks! Read through the homework problems as soon as they are available, and let them percolate in your brain. Schedule multiple times throughout the week to attempt the problems. Often, the solution will only come to you the second or third time you try a problem. Definitely do not wait until the night before it is due to start working on the homework. If you do this (alas, procrastination is all too common), (a) the stress will make it harder to be creative and solve the problems; (b) you will be tempted to ask your homework group for too many hints (or outright solutions) to the problems, which is cheating and impedes your learning, and (c) the stress will sap the joy of finding algorithms!
  3. Make use of office hours and discussion sections: The instructor and TAs hold office hours expressly to help you. You are free to attend as many office hours as you wish (you are not constrained just to use the office hours of your section TA).
    Discussion sections are an opportunity for interactive learning. The success of a discussion section depends largely on the willingness of students to participate actively in it. As with office hours, the better prepared you are for the discussion, the more you are likely to get out of it.
  4. Form study groups! As stated above, you are encouraged to form small groups (two to four students) to work together on homeworks and on understanding the class material on a regular basis. In addition to being fun, this can save you a lot of time by generating ideas quickly and preventing you from getting hung up on some point or other. Of course, it is your responsibility to ensure that you contribute actively to the group; passive listening will likely not help you much. And recall the caveat above that you must write up your solutions on your own. Spend some time on your own thinking about each problem before you meet with your study partners; this way you will be in a position to compare ideas with your partners, and it will get you in practice for the exams.