e CS 170: Efficient Algorithms and Intractable Problems
  

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


Prof. David Wagner
Fall 2014

Instructor:

David Wagner (office hours Mon 2-3pm and Fri 1-2pm in 733 Soda)

TAs:

Nima AhmadiPourAnari (office hours Wed 4-5:30 in 611 Soda, Thu 5-6:30 in 651 Soda)
Daniel Fremont (office hours Thu 9:30-11am in 411 Soda, Thu 4-5:30 in 611 Soda)
Lewin Gan (office hours Mon 4-6 in 611 Soda)
Evangelos Georganas (office hours Mon 3:30-5 in 283E Soda, Thu 2:30-4 in 283H Soda)
Yun Park (office hours Tue 4-6 in 611 Soda)
Haley Rowland (office hours Tue 12:30-1:30 in 751 Soda)
Rohit Sinha (office hours Thu 10:30-12 and Thu 1-2:30 in 529 Cory)
Baruch Sterin (office hours Mon 7-8:30pm and Wed 7-8:30pm in 531 Cory)
Ning Tan (office hours Tue 10-11am, Tue 6-7pm, Thu 9-10am, all in 651 Soda)
Amy Tsai (office hours Wed 2:30-4:00 in 531 Cory)
Evan Ye (office hours Tue 11-12 in 651 Soda)

Lectures:

MWF 11:00am-12:00pm, 155 Dwinelle

Sections:

101. Wed 2:00-3:00, 71 Evans (Nima AhmadiPourAnari)
102. Wed 3:00-4:00, 289 Cory (Nima AhmadiPourAnari)
103. Wed 4:00-5:00, 71 Evans (Yun Park)
104. Wed 5:00-6:00, 2 Evans (Evan Ye)
105. Thu 9:00-10:00, 87 Evans (Rohit Sinha)
106. Thu 10:00-11:00, 285 Cory (Ning Tan)
107. Thu 11:00-12:00, 105 Latimer (Ning Tan)
108. Thu 2:00-3:00, 87 Evans (Daniel Fremont)
109. Thu 3:00-4:00, 254 Sutardja Dai (Daniel Fremont)
110. Thu 4:00-5:00, 254 Sutardja Dai (Evangelos Georganas)
111. Thu 5:00-6:00, 85 Evans (Evangelos Georganas)
112. Thu 6:00-7:00, 85 Evans (Baruch Sterin)
113. Fri 10:00-11:00, 85 Evans (Baruch Sterin)
114. Wed 3:00-4:00, 4 Evans (Yun Park)
115. Fri 10:00-11:00, 3111 Etcheverry (Amy Tsai)
116. Thu 3:00-4:00, 2070 VLSB (Haley Rowland)
117. Thu 4:00-5:00, 2066 VLSB (Lewin Gan)

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
Fri 8/29 Introduction, reasoning about correctness  
Mon 9/1 holiday
Wed 9/3 Asymptotic running time, big-O notation Chapter 0
Fri 9/5 Divide-and-conquer algorithms Chapter 2.1
Mon 9/8 Recurrence relations Chapter 2.2, 2.3
Wed 9/10 Median-finding Chapter 2.4
Fri 9/12 Fast Fourier transform Chapter 2.6
Mon 9/15 FFT, cont.  
Wed 9/17 Graph search Chapter 3.1, 3.2
Fri 9/19 Depth-first search Chapter 3.3
slides
Mon 9/22 Topological sorting Chapter 3.3
slides
Wed 9/24 Strongly connected components Chapter 3.4
Fri 9/26 Breadth-first search and shortest paths Chapter 4.1, 4.2
Mon 9/29 Dijkstra's algorithm Chapter 4.3, 4.4
Wed 10/1 Bellman-Ford, shortest paths in dags Chapter 4.6, 4.7
Fri 10/3 Minimum spanning trees, Kruskal's algorithm Chapter 5.1.0, 5.1.2
Mon 10/6 Kruskal's algorithm, Prim's algorithm Chapter 5.1.1, 5.1.2, 5.1.3, 5.1.5
Wed 10/8 Union-find data structure Chapter 5.1.4
Fri 10/10 Amortized running time of Union-find Chapter 5.1.4, worksheet
Mon 10/13 Greedy algorithms: set cover Chapter 5.4
Wed 10/15 Midterm review
Fri 10/17 Huffman codes, compression Chapter 5.2
Mon 10/20 Dynamic programming Chapter 6.1, 6.2
Wed 10/22 Dynamic programming: edit distance Chapter 6.3
Fri 10/24 Dynamic programming: knapsack problems Chapter 6.4
Mon 10/6 Linear programming Chapter 7.1
Wed 10/29 Network flow Chapter 7.2
Fri 10/31 Applications of network flow Chapter 7.3
Optional: notes
Mon 11/3 Search problems Chapter 8.1
Wed 11/5 P and NP, reductions Chapter 8.2
Fri 11/7 NP-complete problems Chapter 8.3
Mon 11/10 Cook-Levin theorem, Satisfiability Chapter 8.3
Wed 11/12 Reductions, NP-completeness, Copying with NP-completeness
Fri 11/14 Midterm review
Mon 11/17 SAT solvers Chapter 9.1
Wed 11/19 Coping with NP-completeness: Approximation algorithms Chapter 9.2
Fri 11/21 Coping with NP-completeness: heuristics Chapter 9.3
Mon 11/24 Machine learning: k-nearest neighbors notes
Wed 11/26 Machine learning: random forests notes
Fri 11/28 holiday
Mon 12/1 Machine learning: pragmatics
Wed 12/3 Streaming algorithms, CountMin sketch
Fri 12/5 Application: PageRank worksheet
Mon 12/15 Final Exam
11:30-2:30pm

Audio webcasts are available on CalCentral under Academics >> Fall 2014 >> CS 170. Video webcasts of some lectures are also available; see Piazza @336.


Homeworks:

Homeworks are due Fridays at 6pm (but I encourage you to submit by 5pm). No late homeworks accepted.

Submission instructions: Submit your homework, in PDF (not images), electronically via PandaGrader. You have three options for creating your PDF files:

  • Use LaTeX. This is the recommended method since it is powerful and convenient to use for typesetting mathematics, and it produces nice-looking documents. We will post a LaTeX template for you to use for each homework for those who wish to use LaTeX. One useful LaTeX platform is texmaker; or, you can compile latex documents to PDF using pdflatex on a Unix machine.
  • Use a word processor and export the document to PDF.
  • Handwrite your homework on paper and scan it to PDF. You can scan at the libraries or using a scanner on the 2nd floor of Soda Hall.

Formatting your homework: Put your name, student ID number, class account userid, and the homework number prominently at the top of the first page of your PDF file. Also, list the people you collaborated with on the first page. Each problem should begin on a new page. Indicate in PandaGrader which pages correspond to each problem. The pages of your homework submissions must be in order (all pages of problem 1 in order followed by all pages of problem 2 in order, etc.). You risk receiving no credit for any homework that does not adhere to these guidelines.

Special information: Please follow these instructions on how to write up algorithms on homeworks. We insist that you provide a clear explanation of your algorithms and the intuition of how it works. It is not acceptable to provide a long pseudocode listing with no explanation. In our experience, in such cases the algorithm usually turns out to be incorrect. Even if your algorithm turns out to be correct, we reserve the right to deduct points if it is not clearly explained. We have further advice on writing good pseudocode, on Piazza. Homework solutions must be legible. We will not grade messy or unreadable submissions.

Homework parties: We will hold a weekly homework party in 531 Cory and 521 Cory, 11am-2pm. 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.


Discussion Sections

Handouts from discussion sections are available on Piazza.

Topic tutorials

Schedule of topic tutorials:
  • Tue Sept 9 (1-2pm, Woz lounge): Invariants and proofs of correctness. slides
  • Tue Sept 16 (11am-noon, 540AB Cory): the FFT algorithm. slides, piazza
  • Tue Sept 23 (11am-noon, 540AB Cory): properties of depth-first search. piazza
  • Tue Sept 30 (11am-noon, 540AB Cory): graph problems. piazza
  • Tue Oct 7 - cancelled.
  • Tue Oct 14 (1-2pm, Woz lounge): graphs, spanning trees, and divide-and-conquer. piazza
  • Tue Oct 28 (6-7pm, 3108 Etcheverry): dynamic programming. piazza
  • Tue Nov 4 (6-7pm, 3108 Etcheverry): dynamic programming. piazza
  • Wed Nov 12 (6-7pm, 540 Cory): midterm prep - linear programming, maximum flow, and reductions. piazza
  • Tue Dec 2 (6-7pm, 3108 Etcheverry): final exam review, approximation algorithm. piazza

Topic tutorials are completely optional. They are a chance to see some specific topic presented a bit more slowly, for those who would like extra help with that topic. We won't introduce new material. No need to attend, unless you feel like you could use more help on that specific topic.


Reading Quizzes

Reading quizzes must be completed online, before 10am each Monday. Yes, this is early in the morning; if you're not a morning person, you might treat them as being due Sunday night.

Do the reading for the prior week 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.

Quiz 10 is the last quiz.

Exams

There will be two midterms and one final exam. The midterms will be given on Wednesday October 15 and Monday November 17, both at 7:00-9:00pm. (Important: midterm 2 has been moved from Nov 12 to Nov 17.) The final exam will be Monday December 15, 11:30am-2:30pm.

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.

Exam solutions:


Grading

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

  • Homeworks: 15%
  • Reading quizzes: 5%
  • Midterm 1: 20%
  • Midterm 2: 20%
  • Final exam: 40%
We will drop the lowest homework score.

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

Computer accounts: We will use 'class' accounts this semester. You will need to obtain an account form with a username and password from your discussion section TA. When you first log into your account, you will be prompted to enter information about yourself; that will register you with our grading software. If you want to check that you are registered correctly with our grading software, you can run check-register at any time. Anyone who does not register their course account by Friday, September 5 risks being dropped from the course.

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.

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

Topic tutorials: Most weeks, we will hold a short tutorial on a specific topic that might be confusing, for those who want to see it gone over a little more slowly. These are purely optional, and only intended for those who could use a little more help on that specific topic. Full disclosure: Topic tutorials are not a replacement for attending lectures or discussion sections, and they will not focus on the homeworks (for homework help, go to the homework party or office hours or ask on Piazza). If this interests you, keep an eye out for announcements of the topic tutorials.

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