CS 170 |

**Addresses:**

Contact address:
cs170@inst.eecs

Web page:
http://www-inst.eecs.berkeley.edu/~cs170/

**Lectures:**

MWF, 3:00-4:00, 100 Lewis

**Sections:**

*101.* Tu 10:00-11:00, 3105 Etcheverry (Preda)

*102.* Tu 11:00-12:00, 85 Evans (Rabkin)

*103.* Tu 2:00-3:00, 6 Evans (Abernethy)

*104.* Tu 3:00-4:00, 121 Wheeler (Abernethy)

*105.* Tu 4:00-5:00, 3105 Etcheverry (Rabkin)

*106.* W 9:00-10:00, 3102 Etcheverry (Preda)

*107.* Tu 5:00-6:00, 75 Evans (Abernethy)

*108.* Tu 2:00-3:00, 79 Dwinelle (Rabkin)

*109.* Tu 3:00-4:00, 242 Dwinelle (Preda)

**Office Hours:**

Jake Abernethy: Wed 4-6pm (751 Soda)

Daniel Preda: Mon 2-3pm (711 Soda), Wed 10-11am (711 Soda)

Ari Rabkin: Mon 5-6pm (711 Soda), Thu 4-5pm (711 Soda)

David Wagner: Mon 4-5pm (629 Soda), Fri 4-5pm (100 Lewis / 629 Soda)

- Office hours for the week of Mon May 11-15 are as follows. Abernethy: none. Preda: Mon 2-3pm (711 Soda), Wed 10-11am (711 Soda). Rabkin: Mon 5-6pm (711 Soda), Thu 4-5pm (711 Soda). Wagner: Mon 4-5pm (100 Lewis / 629 Soda), Fri 4-5pm (629 Soda).
- Please check the course newsgroup, ucb.class.cs170, for announcements.

The following schedule is tentative and subject to change.

Topic
| Readings
| |

1/21 | Introduction, reasoning about algorithms | Chapter 0.1 |

1/23 | Efficiency analysis, asymptotic running time, big-O notation | Chapter 0.2, 0.3 |

1/26 | Divide-and-conquer algorithms | Chapter 2.1 |

1/28 | Recurrence relations | Chapter 2.2, 2.3 |

1/30 | Median-finding | Chapter 2.4 |

2/2 | Fast Fourier transform | Chapter 2.6 |

2/4 | Fast Fourier transform | Chapter 2.6 |

2/6 | Graph search | Chapter 3.1, 3.2 |

2/9 | Depth-first search | Chapter 3.3 |

2/11 | Topological sorting | Chapter 3.3 |

2/13 | Strongly connected components | Chapter 3.4 |

2/16 | (no class) | |

2/18 | Breadth-first search | Chapter 4.1, 4.2 |

2/20 | BFS and shortest paths | Chapter 4.2, 4.3 |

2/23 | Dijkstra's algorithm | Chapter 4.4 |

2/25 | Shortest paths: Bellman-Ford | Chapter 4.6 |

2/27 | Directed acyclic graphs | Chapter 4.7 |

3/2 | Midterm review | |

3/4 | Minimal spanning trees, Prim's algorithm | Chapter 5.1.0, 5.1.2, 5.1.5 |

3/6 | MST, Kruskal's algorithm, greedy algorithms | Chapter 5.1.1, 5.1.3 |

3/9 | Union-find data structure | Chapter 5.1.4 |

3/11 | Greedy algorithms: Horn clauses | Chapter 5.3 |

3/13 | Greedy algorithms: Huffman codes | Chapter 5.2 |

3/16 | Dynamic programming | Chapters 6.1, 6.2 |

3/18 | Dynamic programming: edit distance | Chapter 6.3 |

3/20 | Dynamic programming: knapsack problems | Chapter 6.4 |

3/23 | (no class) | |

3/25 | (no class) | |

3/27 | (no class) | |

3/30 | Dynamic programming: bio-computing applications | (Chapter 6.3) |

4/1 | Dynamic programming: shortest paths | Chapter 6.6 |

4/3 | Midterm review | |

4/6 | Midterm 2 | |

4/8 | Linear programming | Chapter 7.1 |

4/10 | Network flow | Chapter 7.2 |

4/13 | Network flow, cont. | Chapter 7.2 |

4/15 | Min-cut problems; applications of network flow | Optional: Lecture notes |

4/17 | Matching | Chapter 7.3 |

4/20 | Search problems | Chapter 8.1 |

4/22 | 2-party zero-sum games | Chapter 7.5 |

4/24 | P, NP | Chapter 8.2, 8.3 |

4/27 | Reductions; NP-completeness; 3SAT is NP-complete | Chapter 8.2, 8.3 |

4/29 | Reductions; NP-complete problems | Chapter 8.3 |

5/1 | SAT solvers | Chapter 9.1 |

5/4 | Coping with NP-completeness: Approximation algorithms | Chapter 9.2 |

5/6 | Coping with NP-completeness: heuristics | Chapter 9.3 |

5/8 | PageRank | (none) |

5/11 | Finite-state machines | (none) |

No late homeworks will be accepted. Out of a total of approximately 12 homework assignments, the lowest two scores will be dropped. Homeworks will be made available the Friday evening before they are due.

- Homework 1 (due 1/30) (revised 1/28); solutions.
- Homework 2 (due 2/6) (revised 2/3); solutions.
- Homework 3 (due 2/13); solutions.
- Homework 4 (due 2/20); solutions.
- Homework 5 (due 2/27); solutions.
- Homework 6 (due 3/6); solutions.
- Homework 7 (due 3/13); solutions.
- Instructions for writing up homework.
- Homework 8 (due 3/20); solutions.
- Homework 9 (due 4/3); solutions.
- Homework 10 (due 4/17), reference code: Java, Ruby; solutions; contest results.
- Homework 11 (due 4/24) (revised 4/19), solutions.
- Homework 12 (due 5/1), solutions.
- Homework 13 (due 5/8), solutions; Sudoku code: Java, Ruby.

Quizzes must be completed online once a week, before 10am on each Monday. The quizzes will check your progress so far, so you should be doing 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 #1 (due 1/26 10am), solution.
- Quiz #2 (due 2/2 10am), solution.
- Quiz #3 (due 2/11 10am), solution.
- Quiz #4 (due Wed 2/18 10am), solution.
- Quiz #5 (due 2/23 10am), solution.
- Quiz #6
**(optional - not graded!)**, (due 3/2 10am). - Quiz #7 (due Mon 3/9 10am), solution.
- Quiz #8 (due Mon 3/16 10am), solution.
- Quiz #9 (due Tue 3/31 10am), solution.
- Quiz #10
**(optional - not graded!)**, (due 4/8 10am). - Quiz #11 (due Mon 4/13 2pm), solution.
- Quiz #12 (due Mon 4/20 10am), solution.
- Quiz #13 (due Mon 4/27 10am), solution.
- Quiz #14 (due Tue 5/5 10am), solution.

A: 90-100 | A-: 82-90 | |||

B+: 74-82 | B: 67-74 | B-: 60-67 | ||

C+: 50-60 | C: 45-50 | C-: 40-45 | ||

D: 30-40 | F:0-30 |

**Contact information:**
If you have a question, the best way to contact us is via the class newsgroup,
ucb.class.cs170.
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.
Please avoid posting answers to homework questions before the homework
is due.
Information on how to access the class newsgroup can be found
here and
here.
A RSS feed
of the newsgroup is also available.

If your question is personal or not of interest to other students, send email to cs170@inst.eecs. Email to this address is forwarded to the instructor and all TAs. We prefer that you use this group 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.

**Announcements:**
The instructor and TAs will periodically post announcements,
clarifications, etc. to the newsgroup.
Hence it is important that you check the newsgroup frequently
throughout the semester.

**Prerequisites:**
The prerequisites for CS 170 are CS 61B and either CS 70 or Math 55.
It is important that you be comfortable with mathematical
induction, big-O notation, basic data structures,
and programming in a standard imperative language (e.g., Java or C).
You will need to be familiar with the Unix operating system and basic tools.
If you need help, the CSUA runs
help sessions.

**Collaboration:** You are encouraged to work on homework problems
in study groups of two to four people; however, you must **always**
write up the solutions on your own.
You must **never** read or copy
the solutions of other students, and you must not share your own
solutions with other students.
Similarly, you may use books or online
resources to help solve homework problems, but you must always
credit all such sources in your writeup and you must never
copy material verbatim.
We believe that most students can distinguish between helping other
students and cheating. Explaining the meaning of a question, discussing a
way of approaching a solution, or collaboratively exploring how to solve
a problem within your group is an interaction that we encourage. On the
other hand, you should never read another student's solution or partial
solution, nor have it in your possession, either electronically or on
paper. You must never share your written solutions, or a partial solutions,
with another student, even with the explicit understanding that it will
not be copied.
You should write your homework solution strictly by yourself. You
must explicitly acknowledge everyone who you have worked with or who
has given you any significant ideas about the homework. Not only is this
good scholarly conduct, it also protects you from accusations of theft
of your colleagues' ideas.

**Warning:** Your attention is drawn to the Department's
Policy on Academic Dishonesty.
In particular, you should be aware that
copying or sharing 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.

**Computer accounts:**
We will use 'named' accounts this semester.
If you do not already have an instructional account,
go to a Unix machine in 273 Soda and login as 'newacct' (password: 'newacct')
to receive a named account
(further
information is available).
After you have obtained your account,
you will need to register with our grading software.

**Textbook:**
We will use *Algorithms* (Dasgupta, Papadimitriou, and Vazirani)
as our textbook.
An earlier
draft of the textbook is available online; however, the chapter and
exercise numbers may differ.
All chapter numbers and exercise numbers in this course
refer to the official paper textbook, not the online version.

**Discussion sections:**
Please enroll in a discussion section via Telebears, if you have
not already. You may only enroll in a discussion section that has
space available; see the online schedule.
You may switch discussion sections only with the approval of the TA
of the section you want to switch to, and only if that section is not
full.
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.

**Grading policies:**
On homeworks, we insist that you provide a clear explanation of
your algorithm. 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 will not grade messy or unreadable submissions.

**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.
If you believe that your homework or exam answer was correct and you
should have received full points, prepare a written note explaining which
question you believe was misgraded and justify your opinion, staple this
to the cover of your homework, and return it to your section TA.
We will not accept verbal regrade requests or regrade requests without
a cover sheet stapled on. We will not regrade your homework on the spot;
we will regrade it in batch mode.
We will only accept regrade requests for up to one week after your graded
solution is returned to you.
For homework grading appeals,
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.

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.

**Homeworks:**
Your homework solutions must be written legibly and contain your name,
your TA's name, your discussion section time,
and the homework number.
*You might receive no credit for assignments that are turned
in without this information.* We do not attempt to grade messy and
unreadable solutions. If a problem can be interpreted in more than
one way, clearly state the assumptions under which you solve the
problem.
In writing up your homework you are allowed to consult any book,
paper, or published material. If you do so, you are required to cite
your source(s).
Model solutions will be made available after the due date.
Grade problem sets will be returned in discussion section.

**Late homework policy:**
We will give no credit for homeworked turned in after the deadline.
No exceptions. 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.

**Exams:**
The midterms and final exam are mandatory.
If you are unable to attend for any
reason, contact the instructor without delay.

**Don't be afraid to ask for help:**
Are you struggling? We'd rather you approached us for help, rather
than falling behind gradually 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!

**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 not huge, 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. 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!)

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

*Mail inquiries to*
`cs170@inst.eecs.berkeley.edu`.