Efficient Algorithms and Intractable Problems

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