CS 170 Efficient Algorithms and Intractable Problems a.k.a. Introduction to CS Theory Prof. Tom Henzinger Fall 2002 Tuesdays and Thursdays, 12:30-2:00 p.m. 145 Dwinelle

Announcements

• If you are on a wait list, you must file an appeal in 393 Soda to get into the class. The instructor does not handle enrollment.
• First lecture on Tuesday, August 27.
• First sections on Tuesday, September 3, and Wednesday, September 4.
• The Tuesday 3-4 section (102) has been cancelled.
• September 12: Some TA office hours have changed. See office hours.
• Review Session on Thursday, October 3, at 6:00 p.m. in 306 Soda.
• Professor Henzinger needs to cancel his office hours on October 7, 8, and 14. Instead, the following office hours will be added on October 7: Arindam Chakrabarti 11-1 and 3-4, Irena Nadjakova 2-3, AJ Shankar 4-6, all in 551 Soda.
• First midterm on Tuesday, October 8, in class (12:30-2:00 p.m., 145 Dwinelle).
• Review Session on Monday, November 4, at 6:00 p.m. in 306 Soda.
• Second midterm on Thursday, November 7, in class (12:30-2:00 p.m., 145 Dwinelle).
• Some people have asked for exercise problems. Here are some suggestions, all from CLRS:
  • Recurrences: 4-4, 4-6 (CLR 4-4, 4-7)
  • Graphs: 22-2, 22-3, 23-4, 24-3, 25-1 (CLR 23-2, 23-3, 25-3, 26-1)
  • Probabilities: 5-2, 11-1 (CLR 12-1)
  • Disjoint Sets: 21-3 (CLR 22-3)
  • Amortization: 17-2 (CLR 18-2)
  • Dynamic Programming: 15-4, 15-5, 15-7 (CLR 16-4, 16-5)
  • Greedy: 16-2
  • Linear Programming: 29-1
  • Network Flows: 26-1, 26-3, 26-4 (CLR 27-1, 27-3, 27-4)
  • NP-Completeness: 34-2, 34-3, 34-4 (CLR 36-2)
  • Approximation: 35-1, 35-3, 35-4 (CLR 37-1, 37-3)
• Review Session on Friday, December 13, 1:30-3:30 p.m. in 1 Le Conte Hall.
• Final exam on Tuesday, December 17, 12:30-3:30 p.m. in 237 Hearst Gym.
• Use the form below you view your homework and exam scores. The final exam scores are now available.
  Enter your SID here:

  We do not have everyone's SID. So if the script can't find your SID, please email us at cs170@cory.eecs.berkeley.edu with your name and SID. If you are a concurrent enrollment student, unfortunately you will have to email us for your scores.

Homework Sets and Exams

• Homework 1 [ps] [pdf] (due September 5); solutions [ps] [pdf].
• Homework 2 [ps] [pdf] (due September 12); solutions [ps] [pdf].
• Homework 3 [ps] [pdf] (due September 19); solutions [ps] [pdf].
• Homework 4 [ps] [pdf] (due September 26); solutions [ps] [pdf].
• Homework 5 [ps] [pdf] (due October 3); solutions [ps] [pdf].
• Midterm I [ps] [pdf] (October 8); solutions [ps] [pdf].
• Homework 6 [ps] [pdf] (due October 17); solutions [ps] [pdf].
• Homework 7 [ps] [pdf] (due October 24); solutions [ps] [pdf].
• Homework 8 [ps] [pdf] (due October 31); solutions [ps] [pdf].
• Homework 9 [ps] [pdf] (due November 14); solutions [ps] [pdf].
• Midterm II [ps] [pdf] (November 7); solutions [ps] [pdf].
• Homework 10 [ps] [pdf] (due November 26); solutions [ps] [pdf].
• Homework 11 [ps] [pdf] (due December 5); solutions [ps] [pdf].

Prerequisites

• CS 61B.
• Math 55 or CS 70.

Required Readings

• Lecture notes, available on the web the day before lecture.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, Second Edition, MIT Press, 2001. The first edition (without Cliff Stein) is also ok. All reading assignments are given with references to both editions; we refer to the first edition as CLR, to the second as CLRS.

Grading Summary

• 30% for the homeworks.
• 15% for Midterm I (Tuesday, October 8).
• 15% for Midterm II (Thursday, November 7).
• 40% for the Final Exam (Tuesday, December 17).

Course Information

• Discussion sections.
• Staff office hours.
• Direct your questions to the ucb.class.cs170 newsgroup or send email to cs170@cory.eecs.berkeley.edu. Use the newsgroup if the answer is of interest to all students; use email only if the question is personal. The staff will check the newsgroup regularly, and if you use the newsgroup, other students will be able to help you too. Email to cs170@cory is forwarded to the instructor and all TAs. There are about 60 of you to every one of us, so please reserve email for the questions you can't get answered in office hours, in discussion sections, or through the newsgroup.
• The instructor and TAs will post announcements, clarifications, hints, etc. to this website and to the class newsgroup. Hence you should read the newsgroup regularly whether you post questions to it or not.
• Course policies. Please read this document carefully. It contains answers to most of the questions that students ask during the first few weeks of class.

Lectures

Whereas CS 61B was a bare introduction to the theory of computer science, CS 170 is a full exploration of it. The following is a list of lectures and approximately corresponding reading material. There will be changes as the semester progresses, so check here periodically. Midterm dates may also change.

Discussion Sections

	When	Where	Who
101	Tuesdays 2:00-3:00	4 Evans	Sourav Chatterji
102	Tuesdays 3:00-4:00		CANCELLED
103	Tuesdays 4:00-5:00	285 Cory	AJ Shankar
104	Wednesdays 9:00-10:00	87 Evans	Irena Nadjakova
105	Wednesdays 10:00-11:00	70 Evans	Arindam Chakrabarti
106	Wednesdays 11:00-12:00	310 Hearst Mining	Arindam Chakrabarti
107	Wednesdays 2:00-3:00	310 Hearst Mining	Irena Nadjakova
108	Wednesdays 4:00-5:00	310 Hearst Mining	AJ Shankar

Course Policies

Prerequisites and Enrollment

All enrollment is handled by the CS office in 393 Soda. The prerequisites for CS 170 are CS 61B and one of Mathematics 55 or CS 70. If you have not satisfied all prerequisites, but you have taken a course you feel is very similar to CS 61B or Math 55, or if you are on a wait list, fill out an appeal form in 393 Soda Hall. The instructor does not handle appeals, so please do not attempt to lobby him for admission to the course.

If you are something other than a regular Berkeley undergraduate, then you probably need a signature on a form admitting you to the course. We cannot promise to admit those of you who are not regular Berkeley students. In particular, we will not sign any concurrent enrollment or UC Extension forms until after the second week of classes.

You should be comfortable with mathematical induction, big-O notation, sorting algorithms, basic data structures, and binary heaps. In particular, if you are a transfer student and have not obtained a thorough understanding of binary heaps from CS 61B or a similar course, you should read Chapter 7 of CLR (Chapter 6 of CLRS) in preparation for this course.

Discussion Sections

In addition to the lectures, you should attend a discussion section for one hour each week. The discussions sections are not mandatory, and nothing done in section will directly affect your grade. On the other hand, the discussion sections are your best opportunity to ask questions and learn interactively, and some examples worked out in section will be helpful on the graded assignments. Your section TA will also return and discuss your homeworks and midterms.

Make sure that you are enrolled in a discussion section that has space for you. To find a section that has space, see the online class schedule for discussion section enrollment levels. You may attend a section other than that for which you are registered only if the TA of the section you are attending agrees to it. Outside of your discussion section, you should feel free to attend any of the staff office hours (not just your section TA's) and ask any of us for help.

Homework Assignments

A problem set is handed out each Thursday and is due at 4 p.m. on the following Thursday. All homeworks require mathematical problem solving (algorithm design and analysis); there won't be any programming assignments. You should turn in your problem sets in 283 Soda; there is a drop box for CS 170 that will be emptied at 4 p.m. every Thursday. Late homeworks are not accepted.

Everything you turn in must be written legibly and contain your name, your discussion section number, the homework number, and "CS 170--Fall 2002". 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 the complete bibliographical data of your source(s). Simply copying a proof is not sufficient; you are expected to write it up in your own words, and you must be able to explain it if you are asked to do so. Your proofs may refer to previous course material and to previous homeworks. Except for this, all results you use must be proved explicitly.

Our goal is to get across a maximum amount of understanding in a minimum amount of time. Since you have other courses, we will try to monitor the time you spend on this course. It is easy, however, to misjudge the time required to solve a problem, so we ask you to indicate with each problem set how much time you spent completing the assignment. This is optional, and will not affect your grade. Roughly, you are expected to spend one hour reading and two hours problem solving for every hour of lecture.

Model solutions to the problem sets are handed out and discussed during the discussion sections in the week after a homework is due. The graded problem sets are returned at the same time. Graded problem sets that are not picked up in the discussion section will be kept by your section TA.

It is extremely important that you continuously stay on top of the material, because every new topic and every new homework builds on previous results. If you don't understand the material at the beginning, it will be difficult to catch up later. If you encounter problems, you are encouraged to talk to the course staff as soon as possible. Please do not wait until the last moment to do your homework--start thinking about the problems on the day they are handed out!

Examinations

There will be two in-class midterm exams during the normal lecture time. They are tentatively scheduled for October 8 and November 7. The final exam will take place during the regularly scheduled exam period on December 17 from 12:30 to 3:30 p.m. You must be in town for the final exam to receive a grade different from F for the class.

The midterms will be cumulative, but they will concentrate on new material. The final exam will be comprehensive. All exams are closed-book, but you are allowed to bring one letter-size sheet of hand-written notes (you can write on both sides of the sheet). No other material will be allowed.

If you miss a midterm, you will be assigned a percentage score for that exam equal to the percentage score you earn on the final exam. (There will be no make-up midterms.) If you miss the final exam, you will receive a grade of F in the class unless you miss it because of a circumstance beyond your control, documented by a physician or equivalent authority, or if it conflicts with another scheduled University of California exam. If we decide to forgive your missing the final exam, you will receive an Incomplete grade and have the opportunity to make it up when we choose to give you an alternate exam, quite possibly at the end of the following semester. A course grade of Incomplete will be granted only for dire medical or personal emergencies that cause you to miss the final, and only if your work up to that point has been satisfactory.

Grading

Your final grade will be based on the sum of your problem set, midterm, and final exam scores.

• Each of the 11 weekly problem sets will be worth 30 x (10/9) points. The two lowest homework scores will be dropped. You may also skip handing in two problem sets; in this case, these two will be the two scores that are dropped.
• Each midterm will count 150 points.
• The final exam will be scored out of 400 points.

We will give no credit for written homework turned in after the deadline, so that we can make on-line solutions available promptly and so that you can discuss those solutions in your discussion sections. Please do not ask for extensions for homework, even in case of emergencies; excuses for late or missed homeworks will not be accepted. The two lowest homework grades are dropped, so you can safely miss two. However, the material in this class can only be learned by doing lots of problems, so the homework is very important.

If you believe we have misgraded a homework or midterm exam question, return it to your section TA with a written note on a separate piece of paper explaining the problem. If you're requesting regrade, please staple this paper to the front of the homework or exam. The entire homework or exam will be regraded, so be sure to check the solutions to confirm that your final grade will go up after regrading. All requests for regrades and recording corrections must be made within one week after you receive the graded assignment or exam. By University policy, final exams must not be regraded.

Because of the difficulty of evaluating students in a course where much of the homework is based on proofs, the grading scale (conversion of scores to letter grades) will not be established until the end of the semester.

Academic Integrity

The work you submit in this course must be the result of your individual effort. Cheating on a homework will earn you the maximum negative grade for that assignment. For example, if you cheat on a homework worth 30 points, your grade on that homework will be -30. Cheating on an exam, or cheating twice in any way, will earn you an F in the class. All incidents of cheating will be reported to the Office of Student Conduct, who will maintain records of your academic misconduct throughout your undergraduate career.

We encourage you to help each other learn the material by discussing the work before you do each assignment. For most assignments, explaining the meaning of a question or a way of approaching a solution 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 should write your homework strictly by yourself. If you receive a significant idea from someone in the class, explicitly acknowledge that person in your solution. Not only is this good scholarly conduct, it also protects you from accusations of theft of your colleagues' ideas.

Presenting another person's work as your own constitutes cheating, whether that person is a friend, an unknown student in this class or a previous semester's class, or an anonymous person on the Web who happens to have solved the problem you've been asked to solve. Everything you turn in must be your own doing, and it is your responsibility to make it clear to the graders that it really is your own work. The following activities are specifically forbidden in all graded course work:

• Possession (or theft) of another student's solution or partial solution in any form (electronic, handwritten, or printed).
• Giving a solution or partial solution to another student, even with the explicit understanding that it will not be copied.
• Working together to develop a single solution and then turning in copies (or modified versions) of that solution under multiple names.

In our experience, nobody begins the semester with the intention of cheating. Students who cheat do so because they fall behind gradually and then panic. Some students get into this situation because they 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.

Mail inquiries to cs170@cory.eecs.berkeley.edu.
Last modified by tah on August 26, 2002.