CS170: EFFICIENT ALGORITHMS & INTRACTABLE PROBLEMS

#### INSTRUCTOR:

Satish Rao (satishr AT cs.berkeley)
Lectures: Tue/Thu 9:30-11 AM, 306 Soda
Office Hours: M/Th 1:30-2:30 PM, 681 Soda

#### GSIs:

Fares Hedayati (fares_hedayati AT berkeley)
Omid Etesami (etesami AT eecs.berkeley)

#### GSI OFFICE HOURS:

Fares Hedayati: 751 Tuesdays 2-3pm, 711 Soda Thursdays 2-3pm
Omid Etesami: 283E Soda Thursdays 3-4pm, 751 Soda Fridays 1-2pm

#### DISCUSSION SECTIONS:

 Section Time Location GSI 101 Thu 4:00-5:00 PM 6 Evans Omid 102 Fri 10:00-11:00 AM 2 Evans Fares 103 Fri 11:00-12:00 AM 2 Evans Fares 104 Fri 12:00-1:00 PM 5 Evans Omid

### RECENT ANNOUNCEMENTS

Final Exam on Tuesday December 16 (8am - 11am)

Review session on Sunday December 14 (10am-12am 306 Soda Hall)

Solution to sample problems on Approximation Algorithms (Chapter 9).

Solution to midterm 2.  (11/25/2008)

Midterm 2. October 13. One page notes front and back. Review.

In problem 5.12, assume m = n + Omega(m).

·                Solution to 5.9.

·         For 5.3 you are asked to find an edge that when removed does not disconnect the graph, if such an edge does not exit return NULL(10/15)

·         Midterm 1 problems and solutions (10/14)

·         In problem 4.3, a simple cycle of length 4 consists of four distinct nodes u1,u2,u3,u4 such that (u1,u2), (u2,u3) , (u3,u4) , (u4,u1) are all edges of the graph. (10/09).

·         In problem 4.5, assume that arithmetic addition could be done in constant time (10/09).

·          In problem 4.14, by efficient algorithm we mean using Dijkstra at most twice (10/09).

·         In problem 4.20, by efficient algorithm we mean using Dijkstra at most twice (10/09).

·          Here are our readers contact info, in case if you have any question about your hw: <zmw@berkeley.edu>, <tianyu@berkeley.edu>, <leih@berkeley.edu>  (10/04)

·         Review session for Midterm 1 will be on Tuesday 6-8 pm at GBP Building Room 1000 (9/30)

·         The node with the lowest post does not necessarily lie in a sink. Counterexample (9/30)

·         One page of notes (both sides) is permitted.

·         Midterm 1 review pdf (9/28)

·         Last year's midterm draft. ps file pdf file  Solutions pdf file (9/28)

### TEXTBOOK

The textbook for this course is "Algorithms" by Dasgupta, Papadimitriou & Vazirani. You can also access the material online at Algorithms but be aware that it is a slightly different version and exercise numbers may not agree. HW assignments refer to exercise numbers in the printed version.

### TENTATIVE COURSE CALENDAR

 Lesson # Date Topic Readings 1 August 28 Introduction and overview Chapter 0 2, 3 September 2, 4 Arithmetic, primality, RSA Chapter 1.1-1.4 4 September 9 RSA, Hashing Chapter 1.4-1.5 5, 6 September 11, 16 Divide-and-conquer Chapter 2.1-2.5 7 September 18 Fast Fourier transform Chapter 2.6 8, 9 September 23, 25 Graph search Chapter 3 10 September 30 Shortest paths I Chapter 4 11 October 2 Midterm 1 12, 13 October 7, 9 Shortest paths II Chapter 4 14, 15, 16 October 14, 16, 21 Spanning trees and greedy algorithms Chapter 5 17, 18, 19 October 23, 28, 30 Dynamic programming Chapter 6 20, 21 November 4, 6 Linear Programming I Chapter 7 22 November 13 Midterm 2 23 November 18 Linear Programming II Chapter 7 24, 25 November 20,  25 NP-completeness Chapter 8 26, 27, 28 December 2, 4, 9 Coping with NP-completeness Chapter 9

### HOMEWORK

The homework problems will be given every Tuesday in class, and are due the following week at 7 PM Monday in the Soda 283 HW Box, unless otherwise stated. Please staple all sheets together and ensure that the front sheet is labeled with your name, SID number, section number, and "CS170 Fall 2008". You risk receiving no credit for any homework submitted without this information. Please take the time to write clear and concise solutions; we will not grade messy or unreadable submissions. The lowest two homework scores will be dropped. No late homework will be accepted.

Tentative homework schedule:

1. Due: Monday, September 8, 7 PM. (Problems 0.2, 1.14, 1.31.) Solutions
2. Due: Monday, September 15, 7 PM. (Problems 1.11, 1.27, 1.29, 2.5, 2.18; one of 1.39 or 1.44 as extra points. In problem 1.27, find d using Extended-Euclid algorithm.) Solutions
3. Due: Monday, September 22, 7 PM (Problems 2.9(a), 2.15, 2.22, 2.26, 2.28). Solutions
4. Due: Monday, September 29, 7 PM. (Problems 3.6, 3.8, 3.12, 3.18, 3.23). Solutions
5. Due: Monday, October 13, 7 PM. (Problems 4.3, 4.5, 4.13, 4.14, 4.20). Solutions
6. Due: Monday, October 20, 7 PM. (Problems 5.3, 5.5, 5.17, 5.20, 5.32). Solutions
7. Due: Monday, October 27, 7 PM.  (Problems 6.5, 6.8, 6.13, 4.22, 5.34).   Solutions [ For dynamic programming questions, unless specified otherwise, we need only the definition of the "table entries" and the recurrence and a sketch of the running time.  E.g. for Knapsack without repetition a complete solution is as follows.
\$T(W,i) = the highest value of a weight \$W\$ subset of the first \$i\$ elements.\$
\$T(W, i) = \max (T(W,i-1), T(W-w_i, i-1) + v_i).\$
The running time is \$O(n)\$ since there are \$O(n)\$ table entries and each
takes constant time to fill.]
8. Due: Monday, November 3, 7 PM.  Solutions (Problems 6.14, 6.17, 6.20, 6.30, 5.12).
9. Due: Monday, November 10, 7 PM.  Solutions (Problems 7.19 and 7.21).
10. Due: Monday, November 24, 7 PM.  Solutions (Problems 7.8, 7.13, 7.25 (parts (a) and (b) graded), 7.27, 7.30)
11. Due: Monday, December 1, 7 PM.  (Problems 8.2, 8.3, 8.6,8.7)
12. Due: Wednesday, December 10, 7 PM.  (Problems 8.11,8.12,8.14,8.18,8.20)

### EXAMS

There will be two midterms and one final. Dates and other details will be announced in class. Midterms dates in the course calendar above are only tentative.

### ASSESSMENT

Your grade in the class will be determined as follows: Homework 35%; Midterms 16% each; Final 33%.

### COURSE POLICIES

Prerequisites: Formal prerequisites are CS61B and either CS70 or Math55. In particular, you should be comfortable with mathematical induction, big-O notation, basic data structures and binary heaps. If you need to refresh any of this background, you should refer to the relevant portions of the book. It is also assumed that you have experience with programming in a standard imperative language such as C, C++ or Java. Although most homeworks will be pencil-and-paper exercises, you may also be expected to do some small programming assignments.

Contact Information: The instructor and TAs will post announcements, clarifications, hints, etc. to this website and/or to the class and to bspace. Hence you must check this website and the bspace frequently throughout the semester.

If you have a question, your best option is to post a message to the newsgroup. 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.

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

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 an anonymous remailer like this one to avoid revealing your identity.

Collaboration: You are encouraged to work on homework problems in study groups of two to four people; however, you must write up the solutions on your own, and you must never read or copy the solutions of other students. Similarly, you may use books or online resources to help solve homework problems, but you must credit all such sources in your writeup and you must never copy material verbatim. Warning: Your attention is drawn to the Department's Policy on Academic Dishonesty. In particular, you should be aware that copying 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.