CS 170
Efficient Algorithms and Intractable Problems
a.k.a. Introduction to CS Theory Prof. Elchanan Mossel
 Spring 2014 

General Information

Contact Information:
  Contact address: cs170@inst.eecs
  Web page: http://www-inst.eecs.berkeley.edu/~cs170/

  TuTh 17:10-18:30, 2050 VLSB


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

Office Hours, Emails:

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


Course Policies

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.

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.

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 answer was correct and you should have received full points, please submit a regrade request via Pandagrader. We will only accept regrade requests for up to 3 days 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. Also, keep in mind that partial credit regrade requests for exam problems will rarely succeed, since all exams where graded in a regular fashion.

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

Exams: The midterms will take place on February 20 and March 20. The final exam will take place on May 16. The midterms and final exam are mandatory. If you are unable to attend an exam for any reason, contact the instructor without delay, as we do not plan on holding make-up midterm times.

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!


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

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