CS170: EFFICIENT ALGORITHMS
& INTRACTABLE PROBLEMS
Satish Rao (satishr AT
cs.berkeley)
Lectures: Tue/Thu 9:3011 AM, 306 Soda
Office Hours: M/Th 1:302:30 PM, 681 Soda
Fares Hedayati (fares_hedayati AT berkeley)
Omid Etesami (etesami AT eecs.berkeley)
Fares Hedayati: 751 Tuesdays 23pm, 711 Soda Thursdays 23pm
Omid Etesami: 283E Soda Thursdays 34pm, 751 Soda Fridays 12pm
Section 
Time 
Location 
GSI 
101 
Thu 4:005:00 PM 
6 Evans 
Omid 
102 
Fri 10:0011:00 AM 
2 Evans 
Fares 
103 
Fri 11:0012:00 AM 
2 Evans 
Fares 
104 
Fri 12:001:00 PM 
5 Evans 
Omid 
Final Exam on Tuesday December 16 (8am  11am)
Review session on Sunday December 14 (10am12am 306 Soda Hall)
Solution to sample problems on Approximation Algorithms (Chapter 9).
Solution to midterm 2. (11/25/2008)
Midterm 2. October 13. One page notes front and back. Review.
In problem 5.12, assume m = n + Omega(m).
· For 5.3 you are asked to find an edge that when removed does not disconnect the graph, if such an edge does not exit return NULL(10/15)
· Midterm 1 problems and solutions (10/14)
· In problem 4.3, a simple cycle of length 4 consists of four distinct nodes u_{1},u_{2},u_{3},u_{4} such that (u_{1},u_{2}), (u_{2},u_{3}) , (u_{3},u_{4}) , (u_{4},u_{1}) are all edges of the graph._{ }(10/09).
· In problem 4.5, assume that arithmetic addition could be done in constant time (10/09).
· In problem 4.14, by efficient algorithm we mean using Dijkstra at most twice (10/09).
· In problem 4.20, by efficient algorithm we mean using Dijkstra at most twice (10/09).
· Here are our readers contact info, in case if you have any question about your hw: <zmw@berkeley.edu>, <tianyu@berkeley.edu>, <leih@berkeley.edu> (10/04)
· Review session for Midterm 1 will be on Tuesday 68 pm at GBP Building Room 1000 (9/30)
· The node with the lowest post does not necessarily lie in a sink. Counterexample (9/30)
· One page of notes (both sides) is permitted.
· Midterm 1 review pdf (9/28)
· Last year's midterm draft. ps file pdf file Solutions pdf file (9/28)
· For littleomega and littleoh notation click here and here. (8/28)
The textbook for this course is "Algorithms" by Dasgupta, Papadimitriou & Vazirani. You can also access the material online at Algorithms but be aware that it is a slightly different version and exercise numbers may not agree. HW assignments refer to exercise numbers in the printed version.
Lesson # 
Date 
Topic 
Readings 
1 
August 28 
Introduction and overview 
Chapter 0 
2, 3 
September 2, 4 
Arithmetic, primality, RSA 
Chapter 1.11.4 
4 
September 9 
RSA, Hashing 
Chapter 1.41.5 
5, 6 
September 11, 16 
Divideandconquer 
Chapter 2.12.5 
7 
September 18 
Fast Fourier transform 
Chapter 2.6 
8, 9 
September 23, 25 
Graph search 
Chapter 3 
10 
September 30 
Shortest paths I 
Chapter 4 
11 
October 2 
Midterm 1 

12, 13 
October 7, 9 
Shortest paths II 
Chapter 4 
14, 15, 16 
October 14, 16, 21 
Spanning trees and greedy algorithms 
Chapter 5 
17, 18, 19 
October 23, 28, 30 
Dynamic programming 
Chapter 6 
20, 21 
November 4, 6 
Linear Programming I 
Chapter 7 
22 
November 13 
Midterm 2 

23 
November 18 
Linear Programming II 
Chapter 7 
24, 25 
November 20, 25 
NPcompleteness 
Chapter 8 
26, 27, 28 
December 2, 4, 9 
Coping with NPcompleteness 
Chapter 9 
The homework problems will be given every Tuesday in class, and are due the following week at 7 PM Monday in the Soda 283 HW Box, unless otherwise stated. Please staple all sheets together and ensure that the front sheet is labeled with your name, SID number, section number, and "CS170 Fall 2008". You risk receiving no credit for any homework submitted without this information. Please take the time to write clear and concise solutions; we will not grade messy or unreadable submissions. The lowest two homework scores will be dropped. No late homework will be accepted.
Tentative homework schedule:
There will be two midterms and one final. Dates and other details will be announced in class. Midterms dates in the course calendar above are only tentative.
Your grade in the class will be determined as follows: Homework 35%; Midterms 16% each; Final 33%.
Prerequisites:
Formal prerequisites are CS61B and either CS70 or Math55. In particular, you
should be comfortable with mathematical induction, bigO notation, basic data
structures and binary heaps. If you need to refresh any of this background, you
should refer to the relevant portions of the book. It is also assumed that you
have experience with programming in a standard imperative language such as C,
C++ or Java. Although most homeworks will be pencilandpaper exercises, you
may also be expected to do some small programming assignments.
Contact
Information: The instructor and TAs will post announcements,
clarifications, hints, etc. to this website and/or to the class and to bspace.
Hence you must check this website and the bspace frequently throughout the
semester.
If you have a question, your best option is to post a message to the newsgroup. The staff (instructor and TAs) will check the newsgroup regularly, and if you use the newsgroup, other students will be able to help you too. When using the newsgroup, please avoid offtopic discussions, and please do not post answers to homework questions before the homework is due.
If your question is personal or not of interest to other students, you may send email to cs170@cory.eecs. Email to this address is forwarded to the instructor and all TAs. We prefer that you use this address, rather than directly emailing the instructor and/or your TA. If you wish to talk with one of us individually, you are welcome to come to our office hours. If the office hours are not convenient, you may make an appointment with any of us by email. Please reserve email for the questions you can't get answered in office hours, in discussion sections, or through the newsgroup.
In
a class this large, it can be challenging for the instructor to gauge how
smoothly the class is going. We always welcome any feedback on what we could be
doing better. If you would like to send anonymous comments or criticisms,
please feel free to use an anonymous remailer like this one to avoid
revealing your identity.
Collaboration: You are encouraged to work on homework problems in study
groups of two to four people; however, you must write up the solutions
on your own, and you must never read or copy the solutions of other
students. Similarly, you may use books or online resources to help solve
homework problems, but you must credit all such sources in your writeup
and you must never copy material verbatim. Warning: Your
attention is drawn to the Department's Policy on Academic
Dishonesty. In particular, you should be aware that copying solutions, in
whole or in part, from other students in the class or any other source
without acknowledgment constitutes cheating. Any student found to be cheating
risks automatically failing the class and being referred to the Office of
Student Conduct.
Regrading Policies: Regrading of homeworks or exams will only be
undertaken in cases where you believe there has been a genuine error or
misunderstanding. 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.
If you wish to request a regrading of a homework or exam, you must return it to
your section TA with a written note on a separate piece of paper explaining the
problem. The entire assignment may be regraded, so be sure to check the
solutions to confirm that your overall score will go up after regrading. All
such requests must be received within one week from the date on which the
homework or exam was made available for return.
The following tips are offered based on our experience with Upper Division classes in CS Theory. If you follow these guidelines, you will make life much easier for yourself in this class.
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 on any of your other Upper Division technical classes.
2. Take the homeworks seriously! The homeworks are explicitly designed to help you to learn the material as you go along. Although the numerical weight of the homeworks is not huge, there is usually a strong correlation between homework scores and final grades in the class. 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. Make use of office hours! The instructor and TAs hold office hours expressly to help you. It is often surprising how many students do not take advantage of this service. 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!)
4. Take part in discussion sections! Discussion sections are not auxiliary lectures. They are an opportunity for interactive learning, through guided group problem solving and other activities. 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.
5. Form study groups! As stated above, you are encouraged to form small groups (two to four people) 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.