CS 170
Efficient Algorithms and Intractable Problems
a.k.a. Introduction to CS Theory


Prof. Alessandro Chiesa
Prof. Umesh Vazirani
Spring 2016

Instructors:

Prof. Alessandro Chiesa (office hours Wed 1:30-2:30, Soda 683)
Prof. Umesh Vazirani (office hours Wed 1:30-2:30, Soda 671)

Head TAs:

Steven Bi (office hours Mon 1-2, Fri 1-2)
Cathy Wu (office hours Mon 5-6, Wed 4-5)

TAs:

Abhishek Fatehpuria (office hours Mon 4-5, Wed 5-6)
Aviad Rubinstein (office hours Mon 2-4)
Barak Gila (office hours Mon 10-11, Fri 9-10)
Cheng Xiang (office hours Fri 4-6)
Chenyang Yuan (office hours Mon 11-12 at Soda 411, Thu 5-6 at Soda 611)
Manish Raghavan (office hours Wed 3-4, Thu 1-2)
Nathan Mandi (office hours Tues 1-3)
Patrick Lutz (office hours Mon 9-10, Fri 10-11)
Wesley Hsieh (office hours Fri 3-4)
All TA office hours, unless otherwise specified, are at Soda 411.

Lectures:

TuTh 3:30pm-5:00pm, 1 Pimentel

Sections:

101. Wed 9:00-10:00, 289 Cory (Chenyang)
102. Wed 11:00-12:00, 122 Barrows (Abhishek)
103. Wed 11:00-12:00, 238 Kroeber (Nathan)
104. Wed 12:00-1:00, 2030 VLSB (Patrick)
105. Wed 12:00-1:00, 2066 VLSB (Wesley)
106. Wed 1:00-2:00, 209 Dwinelle (Manish)
107. Wed 1:00-2:00, 2062 VLSB (Cheng)
108. Wed 2:00-3:00, 283 Dwinelle (Manish)
109. Wed 2:00-3:00, 2066 VLSB (Cheng)
110. Wed 2:00-3:00, 2062 VLSB (Cathy)
111. Wed 3:00-4:00, 103 Moffitt (Cathy)
112. Wed 3:00-4:00, 220 Wheeler (Chenyang)
113. Wed 4:00-5:00, 2030 VLSB (Abhishek)
114. Wed 4:00-5:00, 2032 VLSB (Aviad)
115. Wed 5:00-6:00, 2030 VLSB (Patrick)
116. Wed 5:00-6:00, 2032 VLSB (Aviad)
117. Thu 10:00-11:00, 2030 VLSB (Barak)
118. Fri 10:00-11:00, 6 Evans (Barak)
119. Thu 9:00-10:00, 320 Soda (Barak)

Addresses:

Web page: http://www-inst.eecs.berkeley.edu/~cs170/
Announcements, questions: the class Piazza site.
Feel free to mark your question as private if you don't want other students to see it.

Lectures:

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

Date Topic Readings
Tues 1/19 Introduction, big-O notation, arithmetic Chapter 0, Chapter 1.1
Thurs 1/21 Divide-and-Conquer Chapter 2.1, 2.2, 2.3
Tues 1/26 Divide-and-Conquer Chapter 2.4, 2.5, 2.6
Thurs 1/28 Fast Fourier Transform Chapter 2.6
Tues 2/2 Decompositions of graphs Chapter 3
Thurs 2/4 Paths in graphs Chapter 4.1, 4.2, 4.3, 4.4
Tues 2/9 Paths in graphs Chapter 4.4, 4.5, 4.6, 4.7
Thurs 2/11 Greedy Algorithms Overview of Chapter 5, Chapter 5.4
Tues 2/16 Midterm 1
Thurs 2/18 Minimum Spanning Trees Chapter 5.1
Tues 2/23 Greedy Algorithms Chapter 5.2, 5.3
Thurs 2/25 Dynamic Programming Chapter 6
Tues 3/1 Dynamic Programming Chapter 6
Thurs 3/3 Linear Programming Chapter 7.1
Tues 3/8 Network Flow Chapter 7.2
Thurs 3/10 Duality Chapter 7.4
Tues 3/15 Zero-Sum Games Chapter 7.5
Thurs 3/17 Reductions, Bipartite Matching Chapter 7.3
Tues 3/29 Midterm 2
Thurs 3/31 Search Problems Chapter 8.1
Tues 4/5 NP-Completeness Chapter 8.2, 8.3
Thurs 4/7 Coping with NP-Completeness Chapter 9
Tues 4/12 Multiplicative updates N/A
Thurs 4/14 Applications of multiplicative updates N/A
Tues 4/19 Modular arithmetic, Primality Testing Chapter 1.2, 1.3
Thurs 4/21 Hashing, Sketching, Streaming Chapter 1.5 + Notes
Tues 4/26 Hashing, Sketching, Streaming Notes
Thurs 4/28 Quantum factoring Chapter 10
Fri 5/13 Final Exam
7:00-10:00pm

Homeworks:

Homeworks are due Mondays at 11:59 PM. No late homeworks accepted. See Piazza for the homework and homework submission instructions.

Homework Timeline: Every Monday evening, homework is posted under the Resources tab. It is due the following Monday by 11:59 PM. Out of fairness, no late homeworks will be accepted for any reason. Instead, we will drop your two lowest homework scores. This is to offer peace of mind, and not so you can plan to skip assignments.

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. We share tips on getting started (see @18 on Piazza) and provide a simple LaTeX homework response template under Resources > General Resources. Each problem must start on a new page, and indicate the problem number. 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 "give/design/devise/formulate/create/etc. an algorithm" or to "show how" to solve some computational task. In this case, you must respond in the "4-part algorithm format" detailed here.

How to Submit Homework: Homework is submitted via Gradescope. If Gradescope is experiencing site-wide issues, post on Piazza immediately.

The cutoff for submissions on Gradescope may be set later than 11:59 PM at our discretion, but this does not change our official policy: homework is due by 11:59 PM. For example, if Gradescope has site-wide issues at 12:05 AM and won't let you submit, your homework will not be accepted. Plan to turn in homework safely in advance.

Grading: You may request a ref (through Gradescope) within one week of homework return. Read the official solutions; request a regrade only if you were graded inconsistently with the rubric. Your grade may go up, down, or remain constant; the readers' sole priority is consistency.

Homework Resubmissions: Each week, after solutions are released (shortly after homework is due), you may choose a single problem to revise and fix your solution to. Submit your answer to this one problem in a separate Gradescope assignment; the deadline is 11:59 PM on Tuesday (i.e. you have one day to resubmit). We will grade the resubmitted answer with the regularly-submitted answers. Resubmitted answers should not copy or paraphrase official solutions, but may incorporate the ideas of the solution in your words.

Homework parties: We will hold a weekly homework party in Cory 540. See Piazza (@21) for the exact time each week. 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. TAs will be present to help you. If the room is crowded, please, be kind and make room for others by leaving if you can find an alternative source of assistance. When the room is not crowded, people from the class are welcome to just hang out as long as they aren't bothering other people. For us to be able to continue to offer this service, you all have to be very responsible in taking care of the room, not make a mess, and put things back the way they were before you leave.

Extra credit problems: Do the extra credit problems only if you really enjoy working on these problems and want an extra challenge. It is likely not the most efficient manner in which to maximize your score.

Frequently asked questions: See @19 on Piazza.


Discussion Sections

Handouts from discussion sections are available on Piazza.

Reading Quizzes

Reading quizzes must be completed online, before noon each Tuesday.

Do the reading for the upcoming lecture before taking the quiz. Quizzes must be done on your own (no collaboration, and no discussion of the questions or your answers with others). Quizzes will be made available on this web page the Friday before they are due.


Exams

There will be two midterms and one final exam. The midterms will be given on Tuesdays February 16 and March 29, both at 7:00-9:00pm. The final exam will be Friday, May 13, 7-10 PM.

All exams are mandatory. There will be no make-up exams. If you will be unable to attend any of these dates, you must contact the instructor (via a message on Piazza) within one week after the first lecture.


Grading

We will compute grades from a weighted average, as determined by the higher of the following two calculation methods:

Method 1:

  • Homeworks: 20%
  • Midterm 1: 20%
  • Midterm 2: 25%
  • Final exam: 35%

Method 2:

  • Homeworks: 20%
  • Midterm 1: 20%
  • Midterm 2: 25%
  • Final exam: 30%
  • 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 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 the class Piazza site. The staff (instructors and TAs) will check the site regularly, and if you use it, other students will be able to help you too. Avoid posting answers or hints on homework questions before the homework is due. If in doubt, mark your question as private.

If your question is personal or not of interest to other students, you are encouraged to mark the question 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. We prefer that use these methods instead of sending us email; email regrettably does not scale well to a class of this size.

Collaboration: For each homework, you may collaborate with at most 4 other students. We encourage you to collaborate with your fellow students (in small groups) on the homeworks. 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. If you are tempted to look at someone else's solutions (this includes over the Internet), keep in mind that the exams carry much more weight than the homeworks, and there is a strong correlation between students' exam scores and the effort they put into the homework.

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. In particular, keep the following in mind:

We expect that most people can distinguish legitimate collaboration from cheating, but here are some more details. Telling someone who is not in your homework group how to solve a homework problem is not allowed. Splitting up the problems -- "you solve the first three problems, I'll solve the last three problems, and we'll tell each other how to solve them" -- is not collaboration and not allowed. No matter what, you must write up your solutions entirely on your own. For homeworks, you must never read, see, or copy the solutions of other students, and you must not allow other students to see your solutions. You must never share your solutions, or partial solutions, with another student -- not even with the explicit understanding that they won't be copied; not even with students in your homework group. You must not receive help on homeworks from students who have taken the course in previous years. You must not review homework solutions from previous years. You must not search the Internet for a solution to the exact problem we gave you on a homework. The only way to learn algorithms to practice, practice, practice, so we want you to solve the problems on your own, not rely on other sources as a crutch.

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. If you use Github, 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 In order to minimize the distraction that lecture usage of electronics (e.g. laptops) poses to other students, we are limiting electronics usage to the back of the lecture hall (the last few rows).

Discussion sections: Attendance at discussion sections is expected, and sections may cover important material not covered in lecture. You may attend any discussion section. 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.

Re-grading policies: Regrading of homeworks or exams will only be undertaken in cases where you believe there has been a genuine error or misunderstanding. Any requests for grade changes or re-grading must be made within one week of when the work was returned. Submit re-grade requests via Gradescope. We will only accept homework regrade requests if you believe that your answer on that problem is 100% correct and you should have received full credit; we will not regrade homeworks in cases where you believe that you should have received more partial credit. We also will not accept regrade requests for 0.01-point deductions; those exist as a way to give you constructive feedback on your solutions, to help you improve, without affecting your grade.

Bear in mind that our primary aim in grading is consistency, so that all students are treated the same; for this reason, we will not adjust the score of one student on an issue of partial credit unless the score allocated clearly deviates from the grading policy we adopted for that problem.

Late homework policy: We will give no credit for homework turned in after the deadline. Please don't ask for extensions. We don't mean to be harsh, but we prefer to make model solutions available shortly after the due date, which makes it impossible to accept late homeworks.

Extra credit opportunities: The instructor reserves the right to offer optional activities that provide a small number of extra credit, for those eager for a tougher challenge. We recommend you do them only if you enjoy these problems, as spending effort on them is likely not the most efficient way to maximize your final course grade.

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 a professor 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. 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. Don't fall behind! In a conceptual class such as this, it is particularly important to maintain a steady effort throughout the semester, rather than hope to cram just before homework deadlines or exams. This is because it takes time and practice for the ideas to sink in. Make sure you allocate a sufficient number of hours every week to the class, including enough time for reading and understanding the material as well as for doing assignments. (As a rough guide, you should expect to do at least one hour of reading and two hours of problem solving for each hour of lecture.) Even though this class does not have any major projects, you should plan to spend as much time on it as your other technical classes.
  2. Do the homeworks! The homeworks are explicitly designed to help you to learn the material as you go along. Although the numerical weight of the homeworks is small, there is usually a strong correlation between homework scores and final grades in the class. (The most common denominator among people who do poorly in the class is that they skipped several homework assignments or multiple homework problems.)
    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. (In science people learn a lot from emulating the approach of more experienced scientists.)
  3. Don't wait until the last minute to start homeworks! My best advice is to read through the homework problems as soon as they are available, and let them percolate in your brain. Think through possible approaches while you are waiting in line, or stuck in an elevator, or whatever. Sleeping on a problem has often helped people to come up with a creative approach to it. Definitely do not wait until the night before it is due to start working on the homework.
  4. Make use of office hours! 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). You will also likely get more out of an office hour if you have spent a little time in advance thinking about the questions you have, and formulating them precisely. (In fact, this process can often lead you to a solution yourself!)
  5. Take part in discussion sections! Discussion sections are not auxiliary lectures. They 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.
  6. 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. I strongly advise you to 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. Make sure you work through all problems yourself. I've seen a few groups that split up the problems ("you do Problem 1, I'll do Problem 2, then we'll swap notes"); not only is this a punishable violation of our collaboration policies, it also ensures you will learn a lot less from this course.