CS 170 Efficient Algorithms and Intractable Problems a.k.a. Introduction to CS Theory Prof. Christos Papadimitriou Prof. Umesh Vazirani Spring 2004 Tuesdays and Thursdays, 9:30-11:00 a.m. 50 Birge http://inst.cs.berkeley.edu/~cs170/

Announcements

• (06/10) The grades were submitted to the registrar last week, but it may take them some time (probably a couple more weeks) to process them, due to various administrative delays, both on our part and theirs. Until then, the Bearfacts transcript for everyone will show a blank in the "Grade" field for CS170. This does not indicate anything about the specific grade you received in the class. If you need to find out your grade before the grades are processed by the registrar, please email your TA.
• (05/16) Two PDF versions of the midterm 2 solutions have (finally) been posted below; your reader may not work on one or both of them, due to technical problems. Please let us know if you can't get either of these to work.
• (05/16) Sam and Shyam will be combining their OHs tomorrow and making them EALIER IN THE DAY, from 11am - 2pm in the Wozniak Lounge (430-438 Soda).
• (05/13) David will hold office hours on Sunday the 16th from 1-3PM in 751 Soda.
• (05/13) The following is an incomplete, unedited draft of our solutions to the final review problems: [ps] [pdf]
• (05/13) For the final exam, you may bring 1 sheet of notes, using both sides.
• (05/10) Notes for the quantum computing lectures are now posted.
• (05/10) The CS170 website was moved to a different server temporarily early this morning due to technical problems. These problems have now been resolved and the website is back here, at its normal URL. If you never noticed the change, just ignore this announcement.
• (05/08) The review problems for the final exam are now posted:
  Final review problems: [ps] [pdf] [tex]
  These problems will be the focus of the review sessions, but you are strongly encouraged to try to do them before then, and to work on them individually rather than in groups. Keep in mind that on the final, unlike on the homeworks, we will not allow groupwork.
• (05/02) REVIEW SESSIONS are scheduled as follows:
  Wednesday 05/12 and Thursday 05/13
  6-9pm in 306 Soda on both days.
  
• (04/20) More clarifications for HW10:
  • In Problem (2), assume that the edge costs are integers. For part 2(e), the question is whether or not the optimal solution to the dual LP is always an integer (and why). (To answer this, it may be helpful to find an example for part 2(c) that has a fractional optimal objective function value.)
  • In Problem (4), part (d), the question should be restated: "Do you think that there is a different LP for vertex cover that has an optimal solution that is always integral? Why or why not?"
• (04/19) Questions 2 and 4 in HW10 are about formulating optimization problems as integer programs and then considering a linear relaxation. Here is the underlying philosophy that might help you better understand these questions. In question 2, the variable x_e should be interpreted as the fractional extent to which the edge e is chosen to be in the tree. Of course, we would actually like to either select edge e (set x_e = 1) or not pick it at all (set x_e = 0). However, this would require imposing the additional constraint that x_e can only take on integer values. As we will soon see, integer programming is NP-complete. Therefore we have to settle for the linear relaxation of the problem, where x_e can take on fractional values. Question 4 asks you to carry out this process for vertex cover. i.e. assume that your variables x_v take on values that are integers --- how do you write a set of linear constraints on the x_v and a linear objective function that expresses the fact that the x_v represent the optimal vertex cover.
• (04/19) Correction: HW10, problem 2: The constraints in the LP apply to all subsets S of V, except the empty set and V itself.
• (04/15) This week's section exercises: [ps] [pdf] [tex]
• (04/12) Last week's section exercises: [ps] [pdf] and rough solutions: [ps] [pdf]
• (04/06) Lecture notes for linear programming are now posted. Also, lecture notes for dynamic programming, MSTs, and greedy algorithms have been updated. Consider reviewing the new lecture notes to prepare for the final.
• (04/05) Shyam's office hours are cancelled for Tuesday, April 6. He is still available by appointment.
• (03/31) Rough MT2 review materials available [ps] [pdf]
• (03/30) Discussion sections will not meet this week; they will resume next week (4/8-4/9).
• (03/29) Review sessions will be held in 306 Soda on Tuesday and Wednesday nights between 6 and 8pm.
• (03/17) David's 10am section on Friday is cancelled for this week only; students in that section should attend any of the other sections. Sam will be substituting for David in his 11am section.
• (03/17) This week's section problems are now available: [ps] [pdf] [tex]
• (03/16) Midterm 1 solutions have been posted below.
• (03/11) As announced in class on Tuesday, we will be accepting written appeals of midterm grades. If you are sure that there is a substantive error in your midterm grade (such as incorrect addition of sub-scores or failure to give credit for a complete correct answer), you may appeal your grade by stating your appeal in writing, stapling it to your midterm, and putting it in the homework submission box. The deadline to appeal Midterm 1 grades will be Friday, 03/19, at 5pm. In order to prevent abuse of this system, we reserve the right to take several points off your grade if your appeal is completely gratuitous. As with all grade appeals, we also reserve the right to regrade any part of the midterm, which may thus result in a lower total score.
• (03/09) Midterm 2 will be held in-class on Thursday, April 1st, the week after spring break. This date is final.
• (03/07) Hint for problem 4, homework 6-1. You may think of the new graph as follows: delete some vertices from V to obtain V', and now delete all edges that have at least one endpoint among the deleted vertices. The challenge is to find the correct set of vertices to delete. Think about using a heap in the same way that Dijkstra's algorithm does. Ideally your algorithm should have the same running time as Dijkstra.
• (03/07) Prof. Papadimitriou will not hold office hours this week (03/09 and 03/10). As always, if you cannot make it to any other scheduled staff office hours, please email us and we can try to set up an appointment.
• (03/03) Tuesday, 03/09, in lecture, there will be a short, anonymous mid-term course evaluation survey. We hope that this would be a good opportunity to give more frank feedback to the course staff since, unlike "Problem 0" questions on homework, your name will not appear anywhere on the survey. Please try to come to class that day so we can get feedback even from those of you who don't always make it to lecture.
• (03/03) Homework 6, Part 1, has been reposted (11:11am), so please check to make sure you have the current version.
• (02/25) The problems from the Midterm I review sessions have now been posted.
• (02/23) Reminder: as stated in class, Homework 5 will be due at 5pm on Wednesday rather than at 11:59pm.
• (02/22) Clarifications for problem 3 of Homework 5: All the graphs in this problem are undirected. You may assume that all the graphs involved have 3 or more nodes.
• (02/22) There was an error in problem 4 of homework 5. The problem statement should read:

  ...We now construct a graph G=(V,E) such that V={x_1,...,x_n,not x_1,...,not x_n) and E={(u,v)|either (not u or v) or (v or not u) is a clause in phi}.

  The original version incorrectly had "...or (u or not v)" instead of "...or (v or not u)." The posted files have been updated to reflect this change.
• (02/21) Homeworks 1 and 2 have been graded and passed back in section. If you skip a discussion section, or forget to put your section number on a homework, you will from now on be able to pick up your homework in a box right outside Prof. Papadimitriou's office, 689 Soda.
• (02/17) Midterm I will be held in-class next Thursday, February 26th. It will cover the material from lectures 1 through 9. There will be two review sessions early next week. The exam will be closed-book and closed-notes, but you may bring a 1-page handwritten "cheat sheet" — that is, 1 standard-sized sheet of paper, with handwritten notes on 1 side only.
• (02/10) If you plan to do programming assignments for this class, and do not have a UNIX account on EECS instructional systems, you can get a "named account" — these will last until you graduate if you are an EECS or L&S CS major, or until the end of the semester if you're not. See here for details.
• (02/10) Sam's office hours on Monday are moved permanently to 2:30-3:30pm and will overlap for half an hour with shyam's office hours; her office hours on Tuesday remain the same (2-3pm).
• (02/03) If you want to compile the LaTeX source we post, you will also need to get some other files. See here for details.
• (01/27) More instructions for accessing the newsgroup from outside Berkeley's network are now linked to below.
• (01/21) This class will have an "honors" discussion section. The meeting time and place will be announced shortly. Please see the course policies for details.

Homework Sets and Exams

• Homework 1 : [ps] [pdf] [tex] / Solutions : [ps] [pdf] [tex] (deadline moved to 5pm, January 30th)
• Homework 2 : [ps] [pdf] [tex] / Solutions : [ps] [pdf] (deadline moved to 5pm, February 6th)
• Homework 3 : Version A [ps] [pdf] [tex] Version B [ps] [pdf] [tex] / Solutions (draft): [ps] [pdf] (Do one or the other; deadline moved to 5pm, February 13th)
• Homework 4 : [ps] [pdf] [tex] / Solutions: [ps] [pdf]
• Homework 5 : [ps] [pdf] [tex] (Due at 5pm on Wednesday instead of 11:59pm) / Solutions: [ps] [pdf]
• Homework 6 : Part 1 [ps] [pdf] [tex]; Part 2 [ps] [pdf] [tex]; (You must do BOTH parts) / Solutions: [ps] [pdf]
• Homework 7 : [ps] [pdf] [tex] Solutions: [ps] [pdf]
• Midterm 1: Solutions [ps] [pdf]
• Homework 8 : [ps] [pdf] [tex] (Due at 11:59pm on Tuesday, March 30) Solutions: [ps] [pdf]
• Homework 9 : [ps] [pdf] [tex] Solutions: [ps] [pdf]
• Homework 10 : [ps] [pdf] [tex] Solutions: [ps] [pdf]
• Homework 11 : [ps] [pdf] [tex] Solutions: [ps] [pdf]
• Midterm 2: Solutions [ps] [pdf1] [pdf2]
• Homework 12 : [ps] [pdf] [tex] Solutions: [ps] [pdf]

Lectures

Whereas CS 61B was a bare introduction to algorithms, CS 170 is a full exploration of it. The following is a list of lectures and approximately corresponding reading material. All dates and topics are tentative. Lecture notes may be updated, in which case they will be marked clearly. In general, there will be changes as the semester progresses, so check here periodically. Midterm dates may also change.

Course Information

Prerequisites

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

Readings

• Lecture notes, available on the web the day or more before lecture. For many students these notes will provide suffient converage of the material. There are a number of books on algorithms that you can use for supplementary reading:
• The course has no required textbook. If you would like to read more about the course material we recommend:
  • 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.
  • Udi Manber, Introduction to Algorithms.
  • Dexter Kozen, The design and analysis of algorithms.
  • Robert Sedgewick, Algorithms in Java. This is a more programming-oriented approach.

Grading Summary

• 30% for the homeworks.
• 20% for Midterm I (Final date: Thursday, February 26th, in class).
• 20% for Midterm II (Final date: Thursday, April 1st, in class).
• 30% for the Final Exam (Tuesday, May 18th, 2004, 8am-11am, location TBA; Exam Group 9).

Previous semesters of CS170: Fall 2003, Spring 2003, Fall 2002, Fall 2001, Spring 2001, Spring 1999

Discussion Sections (tentative)

	When	Where	Who	Comments
101	Thursday 1:00-2:00pm	310 Hearst Mining	Sam Riesenfeld
102	Thursday 2:00-3:00pm	71 Evans	Sam Riesenfeld
103	Thursday 3:00-4:00pm	81 Evans	Shyam Lakshmin
104	Thursday 4:00-5:00pm	3113 Etcheverry	Shyam Lakshmin
105	Thursday 5:00-6:00pm	3 Evans	Alex Fabrikant
	Friday 9:00-10:00am			CANCELLED
107	Friday 10:00-11:00am	75 Evans	David Ratajczak
108	Friday 11:00-12:00pm	6 Evans	David Ratajczak
106	Friday 12:00pm-1:00pm	6 Evans	Instructors alternate	Honors section

Contact Information

If you have a question, your best option is to post a message to the ucb.class.cs170 newsgroup. To access the newsgroup from outside the Berkeley network, please see these instructions by CNS. From within the Berkeley network, you can just point your favorite Usenet (NNTP) client to agate.berkeley.edu. There's also more information, provided by EECS IESG, here and here.

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 off-topic discussions, and please do not post answers to homework questions before the homework is due. It is also common courtesy to check previous messages before posting your question, in case your question has already been answered.

If your question is personal or not of interest to other students, you may send email to csNNN@inst.eecs.berkeley.edu, where NNN=170 (apologies for the obfuscated e-mail; this is for SPAM avoidance). Email to this address is forwarded to the instructors and all TAs. We prefer that you use the this address, rather than emailing directly the instructors 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. There are about 50 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.

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 a third-party anonymous remailer to send us email without revealing your identity, like this one.

Staff Office Hours and Addresses