CS170: EFFICIENT ALGORITHMS & INTRACTABLE PROBLEMS
INSTRUCTORS: Christos Papadimitriou
(christos AT cs) &
Umesh Vazirani
(vazirani AT cs)
LECTURES: MWF 34
PLACE: 2060 VALLEY LSB
OFFICE HOURS: Papadimitriou M Th 56 pm, 689 Soda. Vazirani M Th 12, 671 Soda.
TEACHING ASSISTANTS:
Alexandra Kolla (akolla AT eecs, 587 Soda, 6423560)
Lorenzo Orecchia (orecchia AT eecs, 595 Soda, 6434006)
Madhur Tulsiani (madhurt AT eecs, 595 Soda, 6434006)
DISCUSSION SECTIONS(Final  starting from 10/1):
Wed 45: 310 Soda, Alexandra (10/11 in 405 Soda)
Th 23: 215 Dwinelle, Alexandra.
Th 34: 87 Evans, Madhur.
Th 45: 75 Evans, Madhur.
TA OFFICE HOURS:
Alexandra: Tu 122pm, 551 Soda, starting 9/5
Lorenzo: Tu 1112, 511 Soda (alcove)
Madhur: Th 10:3012:30, 551 Soda
TEXTBOOK
The textbook for this course is "Algorithms" by Dasgupta, Papadimitriou & Vazirani.
It will not be available at bookstores until about September 15.
In the meantime, you can access the material online at
Algorithms
COURSE CALENDAR


Topic 
Readings 
1 
August 28 
Introduction and overview 
Chapter 0

2,3,4,5 
August 30, September 1, 6, 8 
Arithmetic, primality, RSA 
Chapter 1.1  1.4

6 
September 11 
Hashing 
Chapter 1.5

7,8&9 
September 13, 15, 18 
Divideandconquer 
Chapter 2.12.5

10&11 
September 20, 22 
Fast Fourier transform 
Chapter 2.5

12,13,14 
September 25, 27, 29 
Graph search 
Chapter 3

15 
October 2 
Shortest paths 
Chapter 4.1

15 
October 4 
Midterm 1 

16&17 
October 6&9 
Shortest paths (continued) 
Chapter 4

18, 19, 20, 21, 22 
October 11, 13, 16, 18 , 20 
Spanning trees and greedy algorithms 
Chapter 5

23, 24, 25 
October 23, 25, 27 
Dynamic programming 
Chapter 6

26, 27 
October 30, November 1 
Linear Programming

Chapter 7


November 3 
Midterm 2 

29, 30 
November 6, 8 
Linear Programming contd.

Chapter 7

31, 32, 33, 34 
November 15, 17, 20, 22 
NPcompleteness 
Chapter 8

35, 36, 37 
November 27, 29, December 1 
Coping with NPcompleteness 
Chapter 9

38 &39 
December 4 & 6 
Quantum algorithms 
Chapter 10

RECENT ANNOUNCEMENTS
The grades for the course have been uploaded on bearfacts. The scores
for the final are available here.
Have a good break!
A new list of grades has been uploaded here
. It includes all homework/midterm grades. You have until Saturday
8AM to report any discrepancy with your records.
An updated list of grades has been uploaded here. Grades for HW12, 13, 14 and the "missing"
HW5's will be uploaded tonight. Please report any discrepancies (not
regrade requests) by
Thursday (12/14) night.
Extra office hours before the exam
 Tuesday (12/12), 111, 511 Soda: Madhur
 Wednesday (12/13), 111, 511 Soda: Lorenzo
 Wednesday (12/13), 13, 587 Soda: Alexandra
Final Exam Material
 Sample Final: ps, pdf.
Solutions: ps, pdf
 Here is an actual final from Spring05: ps, pdf.
 Some practice True/False questions: ps, pdf.
Solutions: ps pdf
Clarification regarding problem 10.3: The problem asks you to compute
Fourier transform "Modulo M". Please note that this is NOT like
problem 2.30 where we computed Fourier transform in a finite
field. For problem 10.3, you are supposed to compute the usual (using
complex roots of unity) Fourier transform. In this context "Mod M"
only means the basis states (of which the QFT is a superposition) are
0>, 1>, ..., M1>.
The review session will be held on Monday (12/11) from 5:30  7:00 pm
in 310, Soda Hall.
Problem 10.2 for HW14 is cancelled. For problem 10.3, refer to the first
two paragraphs in section 10.3
The final exam is going to be held on Thursday, December 14,
12.303.30 pm, in 10 Evans. A review session will be held on Monday,
time and location TBD.
Problem 8.13(e) for HW13 has been made optional
Problems 9.2, 9.3 added to HW13. An additional hint for problem 8.13
has also been added.
A list with all grades recorded so far has been uploaded to this page.
The leftmost column contains the sudent's SID number, mod 164617.
HOMEWORKS
All homeworks are due Friday at 4:00pm unless otherwise stated.
Turn in your homeworks in the box labeled "CS170" on the 2nd
floor of Soda Hall. Please begin your answer to each problem on a new
sheet of paper. Please ensure that each sheet is
labeled with your name, SID number, section number, and "CS170Fall 2006".
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 homeworks will be accepted.

Homework 1 Problems 0.1, 0.4; 1.4, 1.5 from the book. Due
9/1. In Problem 0.4(e), assume that M(n) = n^c for some
constant c.
Solutions ps, pdf

Homework 2 Problems 1.19, 1.20, 1.21, 1.26, 1.34, 1.39 from the book.
And the following problem:
[This problem has been postponed to next week:]
You wish to pick a random 100 digit prime number.
You pick a 100 digit number at random, use a probabilistic test for primality
and output if the algorithm says prime. Let's analyze
this algorithm:
a) Roughly how many 100 digit numbers are prime.
A rough estimate,
within say 1%, is acceptable for this and the subsequent parts of this question.
b) Suppose your primality test gives the wrong answer with
probability 1/1000. What is the chance that your algorithm
mistakenly outputs a composite instead of a prime?
c) Suppose you want the chance of erroneously outputing a
composite to be less than one in a thousand. How small
should the error probability on your primality test be?
Due
9/8.
Solutions ps, pdf
 Homework 3 Problems 1.28, 1.37, 1.44, 1.45, 1.46 and the
problem above postponed from homework 2. Addition: Problem 2.4.
Due 9/15
Solutions ps, pdf
 Homework 4 Problems 2.5, 2.25, 2.27, 2.7, 2.8(a), 2.9(a)
Due 9/22
Solutions ps, pdf
Also solve the following additional "problem".
HW4  Additional Problem (5 points just for giving an answer!)
Please write the answer on a separate sheet and attach it with your
homework. Do not write your name on this sheet  we shall take these
off before reading them (Just write the appropriate option for
multiple choice questions).
Please feel free to write any other suggestions/comments/crtiticisms
that you may have.
1) The pace of the course is:
 a) Speed of light (very fast)
 b) A bit too fast
 c) Close to my pace
 d) A bit too slow
 e) I sleep in the lectures
2) How challeging do you find the material covered in class?
 a) Rocket science
 b) Fairly challenging
 c) Just right
 d) I did this in kindergarden
3) The sections/office hours are:
 a) Very helpful
 b) Useful at times
 c) Pointless
 d) What sections?
4) The homeworks are:
 a) Akin to Roman methods of torture
 b) Challenging, but help understand the material
 c) Challenging but useless
 d) Of reasonable difficulty
 e) Could be more difficult
5) Give two suggestions for making the sections/office hours more
helpful.
6) Give two suggestions for making the lectures better.
 Homework 5 Problems 2.30, 3.1, 3.2(b), 3.8, 3.11, 3.26.
Due 9/29
Solutions ps, pdf
 Homework 6 Problems 3.5, 3.19, 3.20, 3.24.
Due 10/6
Solutions ps, pdf
 Homework 7 Problems 3.28, 4.5, 4.7, 4.13, 4.21.
Due 10/13
Solutions ps, pdf
 Homework 8 Problems 5.3,5.9,5.14,5.19,5.21,5.28,6.2
Due 10/20
Solutions ps, pdf
Note that the above numbers are according to the printed version of
the book.
The numbers according to the online version are 5.3, 5.9,
5.14, 5.19, 5.20, 5.27, 6.2
 Homework 9 Problems 6.4, 6.6, 6.7, 6.8, 6.14
Due 10/27
Solutions ps, pdf
 Homework 10 Problems 6.17, 6.18, 6.21, 7.1, 7.16
Due 11/3
Solutions ps, pdf
 Homework 11 Problems 7.7, 7.11, 7.13, 7.17, 7.18, 7.31
Due 11/13 (Monday)
Solutions ps, pdf
 Homework 12 Problems 7.14, 7.22, 8.1, 8.2, 8.5, 8.6. And
the following problem:
Suppose that we add to the LP in figure 7.2 the constraint x1 + x2 +
x3 >=200.
Solve the new LP, and show your work in the same detail as Figure
7.13. Since (0,0,0) is no longer feasible, you must start by finding a
corner, as described in Section 7.6.3.
Also, to avoid degeneracy you must perturb the equation x1+x2+x3 <=
400, perhaps to x1+x2+x3 <=401, but then you must adjust the final
result. Due 11/20 (Monday again)
Solutions ps, pdf
 Homework 13 Problems 8.10, 8.12, 8.13 and Problems 9.2, 9.3
Due 12/1
(Additional hint for 8.13: The one proof of NPCompleteness that is
not by generalization, can be done by a reduction from DOMINATINGSET)
Note: Part (e) for problem 8.13 is optional
Solutions ps, pdf
 Homework 14 Problems 9.1, 9.4, 10.1, 10.2, 10.3
Due 12/8
Note: Problem 10.2 in cancelled. For 10.3, refer to first two
paragraphs of section 10.3
Also see clarification regarding problem
10.3 in the announcements section.
Solutions ps, pdf
HANDOUTS
Handout 1[pdf]
Solutions [pdf]
Handout 2[pdf]
Solutions [pdf]
Handout 3[pdf]
Solutions [pdf]
Handout 4[pdf]
Solutions [pdf]
Handout 5[pdf]
Solutions [pdf]
Handout 6[pdf]
Solutions [pdf]
Handout 7[pdf]
Solutions [pdf]
Handout 8[pdf]
Solutions [pdf]
Handout 9[pdf]
Solutions [pdf]
Handout 10[pdf]
Solutions [pdf]
MIDTERM 1 MATERIAL
MIDTERM 2 MATERIAL
EXAMS
There will be two midterms and one final. Dates and other details
will be announced in due course.
QUIZZES
There will be a short quiz at the beginning of class on randomly selected
dates. The quiz will consist of a small number of very simple questions
related to the material of the previous class. The two lowest quiz scores
will be dropped. The motivation for the
quizzes is twofold: (1) to encourage you to review the material of each
class before the next class; (2) to encourage ontime arrival at lectures.
ASSESSMENT
Your grade in the class will be determined as follows:
Homeworks 25%; Midterms 20% each; Final 30%; Quizzes 5%.
COURSE POLICIES
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 newsgroup,
ucb.class.cs170.
Hence you must check this website and the newsgroup frequently throughout the
semester. For information on how to access UCB newsgroups, go
here
(see also here
for more).
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.
SOME HELPFUL HINTS
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.