CS 170 |

**Contact Information:**

Contact address: cs170@inst.eecs

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

Piazza

**Lectures:**

TuTh 17:10-18:30, 2050 VLSB

**Sections:**

101 | 6 Evans | Mon 10-11am | Ben Weitz |

102 | 4 Evans | Mon 11am-12pm | Ben Weitz |

103 | 6 Evans | Mon 12-1pm | Ning Tan |

104 | 75 Evans | Mon 1-2pm | Ning Tan |

105 | 6 Evans | Mon 2-3pm | Yun Park |

106 | 4 Evans | Mon 3-4pm | Yun Park |

107 | 75 Evans | Mon 4-5pm | Atif Rahman |

108 | 4 Evans | Mon 5-6pm | Atif Rahman |

109 | 5 Evans | Tue 11am-12pm | Lewin Gan |

110 | 85 Evans | Tue 12-1pm | Lewin Gan |

111 | 3105 Etcheverry | Mon 1-2pm | Rudy Dai |

112 | 310 Soda | Mon 11am-12pm | Rudy Dai |

113 | 320 Soda | Mon 4-5pm | Edwin Liao |

Elchanan Mossel | Tue/Thur 7-8pm, 411 Soda | mossel at stat.berkeley.edu |

Rudy Dai | Fri 10-11am, 611 Soda Fri 11am-12pm, 411 Soda | rudydai at berkeley.edu |

Lewin Gan | Thur 12-2pm, 611 Soda | lewin.cs170 at gmail.com |

Edwin Liao | Thur 10am-12pm, 751 Soda | edliao.9.16 at gmail.com |

Yun Park | Wed 3-5pm, 611 Soda | yun_park at berkeley.edu |

Atif Rahman | Mon 1-3pm, 748 Evans | atif at eecs.berkeley.edu |

Ning Tan | Tue 9-10am, 611 Soda Tue 4-5pm, 611 Soda |
ntan at berkeley.edu |

Ben Weitz | Fri 12-2pm, 651 Soda | bsweitz at eecs.berkeley.edu |

- All announcements will be posted to Piazza. You are responsible for staying up-to-date with announcements made on Piazza.

**Contacting Course Staff:** The staff (instructor and TAs) will
check Piazza regularly, and important announcements will be made
there. Moreover, other students will be able to help you too.
Please avoid posting answers or hints to homework questions before
the homework is due. If in doubt, make a private post to the
instructors. The course staff reserves the right to delete posts
and comments that are not constructive (e.g. questions that are
clearly answered in the problem statement, repeated questions,
etc...)

If your question is personal or not of interest to other students, post a private message on Piazza for the course staff. You may also email cs170@inst. This will go to the course staff. 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 Piazza.

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

**Grading:** The lowest 2 homework scores will be dropped. Each
homework set will receive full credit it's grade is 70-100, 0.5
credit if the grade is 30-69, 0 credit it the grade is 0-29. The
final grade will be computed using the following weighted average:
10% for homeworks, 25% for Midterm 1, 25% for Midterm 2, 40% for
the final exam. The instructor reserves the possibility of awarding
2% for participation on Piazza, in contest and/or in-class/online
quizzes.

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

**Textbook:** We will use *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.

**Homeworks:** Homeworks will be posted on
the CS170 Piazza
Group. They are due on Fridays at 6:00 p.m. and must be
submitted via Pandagrader. For each
homework assignment, you must submit a pdf that is at most 3 MB
in size.

You may prepare your homework by writing it on paper and scanning
it. Some information on scanning at the libraries is here. To
compress an image on Linux, you can use the 'convert'
command. On Windows you can use Microsoft Office Picture
Manager, (youtube tutorial for
compression). On OS X, you can run ImageMagick. You can also
use LaTeX, or any
other legible means. It should be converted to pdf. 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.

Make sure to include your name and the homework number prominently on the
first page of each submission. Each problem should begin on a new
page. Each page should be clearly labelled with the problem number
and the page number. 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.

On homeworks, we insist that you provide a clear explanation of
your algorithms. 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. 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.

No late homeworks will be accepted. 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. Out of a total of
approximately 12 homework assignments, the lowest two scores will
be dropped.

The course staff may choose to grade a subset of the homework
problems.

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

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