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.