Efficient Algorithms and Intractable Problems
CS 170: Efficient Algorithms and Intractable Problems (aka Intro to CS Theory)
Professors Prasad Raghavendra & Sanjam Garg
Prerequisites: CS 61B and CS 70. You should be comfortable with mathematical induction, big-O notation, data structures, and programming in a standard imperative language (Java, Python, etc.).
Required textbook: Algorithms by Dasgupta, Papadimitriou, and Vazirani.
Announcements: All instructor announcements will be via Piazza. It is your responsibility to read all of them, though we will often direct Piazza to send you an email as a courtesy in important cases.
Contact: The fastest way to get a question answered is to ask on Piazza. For questions directed at the instructors or containing answers/strong hints to homework problems, make sure to post privately on Piazza. To reach an individual instructor, email them directly or go to their office hours. See @16 for more.
Instructor Information
Instructor | |
Prof. Prasad Raghavendra | prasad@cs.berkeley.edu |
Prof. Sanjam Garg | sanjamg@berkeley.edu |
Jimmy Wu (co-head TA) | j.wu@berkeley.edu |
Steven Bi (co-head TA) | chenhsi@berkeley.edu |
Alan Yao | alanyao@berkeley.edu |
Barak Gila | barak.gila@berkeley.edu |
Manish Raghavan | manishraghavan@berkeley.edu |
Matthew Chow | matthewchow@berkeley.edu |
Benjamin Weitz | |
Rudy Laprade | rlaprade@berkeley.edu |
Di Wang | |
Aaron Schild | aschild@berkeley.edu |
Vrettos Moulos | vrettos@berkeley.edu |
Discussion Sections (view as calendar)
Section # | Time | Location | Instructor |
101 | Monday 3-4 PM | 3111 Etcheverry | Di Wang |
102 | Monday 3-4 PM | 136 Barrows | Barak Gila |
103 | Monday 4-5 PM | 104 Barrows | Jimmy Wu |
104 | Monday 5-6 PM | 9 Evans | Alan Yao |
105 | Tuesday 11-12 PM | 210 Wheeler | Rudy Laprade |
106 | Tuesday 1-2 PM | 102 Latimer | Aaron Schild |
107 | Tuesday 2-3 PM | 3105 Etcheverry | Steven Bi |
108 | Tuesday 4-5 PM | 179 Stanley | Matthew Chow |
109 | Tuesday 5-6 PM | 179 Stanley | Benjamin Weitz |
110 | Tuesday 5-6 PM | 83 Dwinelle | Manish Raghavan |
111 | Wednesday 9-10 AM | 179 Stanley | Barak Gila |
112 | Wednesday 10-11 AM | 254 Sutardja Dai | Alan Yao |
113 | Wednesday 11-12 PM | 179 Stanley | Matthew Chow |
114 | Wednesday 12-1 PM | 179 Stanley | Vrettos Moulos |
115 | Wednesday 1-2 PM | 179 Stanley | Vrettos Moulos |
116 | Wednesday 1-2 PM | 106 Moffitt | Manish Raghavan |
117 | Wednesday 12-1 PM | B1 Hearst Annex | Rudy Laprade |
Office Hours (view as calendar)
Instructor | Time | Location |
Alan Yao | Mon 9-11 AM | Soda 283E |
Jimmy Wu | Mon 11-1 PM | Soda 611 |
Prof. Sanjam Garg | Mon 4-5 PM | Soda 685 |
Steven Bi | Mon 5-7 PM | Soda 283E |
Matthew Chow | Tue 9-10:30 AM | Soda 651 |
Benjamin Weitz | Tue 12-2 PM | Soda 651 |
Manish Raghavan |
Tue 4-5 PM Wed 3-4 PM |
Soda 651 Soda 283H |
Barak Gila | Wed 11-1 PM | Soda 411 |
Prof. Prasad Raghavendra | Wed 5-6 PM | Soda 623 |
Rudy Laprade | Thu 12-2 PM | Soda 611 |
Di Wang | Thu 4-6 PM | Soda 611 |
Aaron Schild | Fri 10-12 PM | Soda 611 |
Vrettos Moulos | Fri 12-2 PM |
Soda 283E |
Tentative Schedule
Lectures are MWF 2-3 PM in 155 Dwinelle Hall. We will update this schedule as topics are decided. In general, you can expect us to follow the textbook fairly closely, with some special topics mixed in.
Lesson # | Date | Topics | Relevant Readings | Webcast |
1 | 8/26 | Introduction | Chapter 0 | Link |
2 | 8/28 | Arithmetic algorithms | Sections 1.1, 1.2 | Link |
3 | 8/31 | Primality testing, hashing | Sections 1.3-1.5 | |
4 | 9/2 | Divide-and-conquer (integer and matrix multiplication) | Sections 2.1, 2.5 | |
5 | 9/4 | Divide-and-conquer | Chapter 2 | |
9/7 | NO CLASS (Labor Day) | |||
6 | 9/9 | Divide-and-conquer | Chapter 2 | |
7 | 9/11 | Fast Fourier transform | Section 2.6 | |
8 | 9/14 | Fast Fourier transform | Section 2.6 | |
9 | 9/16 | Fast Fourier transform | Section 2.6 | |
10 | 9/18 | |||
11 | 9/21 | |||
12 | 9/23 | |||
13 | 9/25 | |||
14 | 9/28 | |||
15 | 9/30 | |||
16 | 10/2 | |||
17 | 10/5 | |||
18 | 10/7 | Midterm 1 (7-8:30 PM) | ||
19 | 10/9 | |||
20 | 10/12 | |||
21 | 10/14 | |||
22 | 10/16 | |||
23 | 10/19 | |||
24 | 10/21 | |||
25 | 10/23 | |||
26 | 10/26 | |||
27 | 10/28 | |||
28 | 10/30 | |||
29 | 11/2 | |||
30 | 11/4 | |||
31 | 11/5 | Midterm 2 (7-8:30 PM) | ||
11/6 | LECTURE CANCELLED (grading exams) | |||
32 | 11/9 | |||
11/11 | NO CLASS (Veterans Day) | |||
33 | 11/13 | |||
34 | 11/16 | |||
35 | 11/18 | |||
36 | 11/20 | |||
37 | 11/23 | |||
11/25 | NO CLASS (Thanksgiving holiday) | |||
11/27 | NO CLASS (Thanksgiving holiday) | |||
38 | 11/30 | |||
39 | 12/2 | |||
40 | 12/4 | |||
12/17 | Final Exam (3-6 PM) |
Grading
The weight categories are:
- 30% homework and programming project
- 20% midterm 1
- 20% midterm 2
- 30% final
The class will be curved at the very end of the semester.
Discussion Sections
Attendance at discussion is expected, and sections may cover material not covered in lecture. But it is not mandatory, and you may attend whichever section you wish.
Quizzes
Each discussion will begin with a 5-minute quiz. Quiz scores will be posted to bCourses.
Quizzes appear in your final course grade if and only if you score below 40% out of the 70% combined weight of homework and midterms. In this case, your quiz scores may boost your grade by up to 5%. Otherwise, they have no effect.
Homework
There will be weekly problem sets due every Friday at 5 PM. Out of fairness, no late homeworks will be accepted for any reason. Instead, we will drop your two lowest homework scores. This is to offer peace of mind, and not so you can plan to skip any particular assignments.
For how to do and submit homework, see @17.
Homework Parties
We will hold weekly "homework parties" on Wednesdays 6-9 PM in 540 Cory Hall, with two exceptions:
- The party on September 2 will be from 7-10 PM.
- The party on September 23 is replaced by September 22 (Tuesday), 6-9 PM.
We will send out reminders of the exceptions.
Though instructors will be present to answer questions, these are primarily for you to collaborate with your peers. Past students have found them to be extremely helpful.
Programming Project
Towards the end of the semester, there will be a challenging but fun programming project. It cannot be dropped. Details will be decided and announced when that time approaches.
Academic Integrity
Cheating on homework or exams is taken extremely seriously. To avoid issues, please:
- Give credit. If another student made a significant contribution to your understanding of a homework problem, list them.
- Don't share solutions with others—including collaborators. Working together means clarifying concepts and discussing approaches. Never look at any part of someone else's solution, and never share any part of your own work with another student. For example, splitting up problems among your collaborators, then sharing them afterwards is not allowed.
- Write up your solutions entirely on your own.
- When in doubt, ask. If unsure whether something constitutes cheating, ask an instructor.
The only way to learn algorithms is to practice designing algorithms. As such, looking up solutions online or in other references is not allowed. This goes for algorithms, proofs, etc. Finding solutions from past semesters' materials or students is also not permitted. In short, use only the course textbook, collaboration with peers, Piazza, and instructors' office hours.
Advice
CS 170 is one of the more intensive upper-division courses. Based on our experience, the following will help:
- Come to lecture. The lectures often contain a view of the material not found in the book, and are much easier to follow live.
- Don't fall behind. In a conceptual course like CS 170, it is important to stay on top of the material and allow it time to sink in, rather than cram.
- Do the homework. We carefully craft the homework to help you learn the material deeply, so homework grades and exam grades are highly correlated. Regardless of how you do on the homework, read the sample solutions.
- Don't do homework last-minute. Read the problems as soon as they are released, because inspiration takes time to strike. A solution may occur to you while waiting in line, riding an elevator, or even during sleep.
- Come to office hours. The professors and TAs are expressly here to help you. You will also get more out of office hours if you spend a little time in advance to formulate your questions precisely.
- Actively participate in discussion sections. Discussion sections are not auxiliary lectures. They are opportunities for interactive problem-solving, and thus depend on the willingness of students to participate. Working through problems in discussion is usually very helpful for the homework.
- Form study groups. This saves you time by generating ideas quickly and avoiding getting stuck on problems.
Course Summary:
Date | Details | Due |
---|---|---|