### Instructors:

Professor Luca Trevisan (OH Wednesday 1:30-3p in 625 Soda)

*All TA/reader office hours are at Soda 411.*

### TAs:

Allen Tang (OH Thursday 1-2p)

Barak Gila (OH Monday 1-2p, Friday 12-1p)

Elan Frenkel (office hours Thursday 11-1p)

Liuxiao (Betty) Zhang (OH Friday 11-12p)

Mike Ambrose

Nathan Mandi (OH Tuesday 1-2p, Thursday 2-3p)

Peter Manohar (OH Monday 11-1p)

Rudy Laprade (OH Friday 1-2p)

Tony Duan (OH Monday 3-4p)

Wesley Hsieh (OH Wednesday 3-5p)

### Readers:

Albert Pham

Aurelia Guy (OH Friday 12-1p)

Devyn Krevat

Jerry Cheng (OH Friday 12-1p)

Kevin Arifin (OH Thursday 2-3p, Friday 11-12p)

Nikhil Sharma

Patrick Yang (OH Friday 11-1p)

Richard Qian

Sabrina Shie (OH Monday 3-4p)

Sukyun Chung

Tina Zheng (OH Wednesday 3-5p)

Yuchen Jiang

#### TA office hours by day:

Tuesday: 1-2p, 3-5p

Wednesday: 3-5p

Thursday: 12-3p

Friday: 11a-2p, HW Party 2p-5p

### Lectures:

### Sections:

You may go to any section, regardless of your registration.

Time | # | Location | TA |
---|---|---|---|

Wed 9a | 101 | Etcheverry 3111 | Allen |

Wed 10a | 103 | Moffitt Library 103 | Liuxiao (Betty) |

Wed 11a | 104 | Hearst Field Annex B5 | Tony |

Wed 12p | 105 | Soda 320 | Aaron |

Wed 12p | 106 | Soda 405 | Wesley |

Wed 1p | 107 | Soda 310 | Rudy |

Wed 2p | 108 | Soda 405 | Barak |

Wed 2p | 117 | Soda 310 | Rudy |

Wed 3p | 113 | Soda 310 | Barak |

Wed 4p | 109 | Soda 405 | Allen |

Wed 4p | 115 | Latimer 105 | Elan |

Wed 4p | 116 | Barrows 104 | Liuxiao (Betty) |

Wed 5p | 102 | Etcheverry 3111 | Elan |

Wed 5p | 110 | Soda 405 | Nathan |

Wed 7p | 118 | Soda 320 | Tony |

Th 3:30p | 111 | Soda 310 | Nathan |

Th 4:30p | 112 | Soda 405 | Aaron |

Th 5p | 114 | Soda 320 | Wesley |

### Schedule:

The lecture schedule is subject to change and will be revised as the course progresses.

# | Date | Topic | Readings |
---|---|---|---|

1 | 8/25 | Introduction, big-O notation, divide and conquer | Chapter 0, Chapter 2.1, 2.2, 2.3 |

2 | 8/30 | Divide and Conquer | Chapter 2.4, 2.5, 2.6 |

3 | 9/1 | Fast Fourier Transform | Chapter 2.6 |

4 | 9/6 | Graphs | Chapter 3 |

5 | 9/8 | Graphs | Chapter 4 |

6 | 9/13 | Greedy algorithms intro Minimum Spanning Trees | Chapter 5.1 |

7 | 9/15 | Greedy algorithms | Chapter 5.2, 5.3, 5.4 |

8 | 9/20 | No lecture -- Midterm 1 | |

9 | 9/22 | Dynamic Programming | Chapter 6 |

10 | 9/27 | Dynamic Programming | Chapter 6 |

11 | 9/29 | Dynamic Programming | Chapter 6 |

12 | 10/4 | Dynamic Programming | Chapter 6 |

13 | 10/6 | Linear Programming: intro + simplex overview | Chapter 7.1 |

14 | 10/11 | LP: simplex algorithm and duality | Chapter 7.4, 7.6 |

15 | 10/13 | LP: Network Flow | Chapter 7.2; lecture notes |

16 | 10/18 | LP: Reductions and bipartite matching | Chapter 7.3 |

17 | 10/20 | Zero-sum games | Chapter 7.5 |

18 | 10/25 | Multiplicative weights | lecture notes |

19 | 10/27 | Parallelism | lecture notes |

20 | 11/1 | No lecture -- Midterm 2 | |

21 | 11/3 | Gradient descent | lecture notes |

22 | 11/8 | Search Problems | Chapter 8.1 |

23 | 11/10 | NP-Completeness | Chapter 8.2, 8.3 |

24 | 11/15 | Coping with NP-Completeness | Chapter 9 |

25 | 11/17 | Coping with NP-Completeness | Chapter 9 |

26 | 11/22 | Streaming | lecture notes, part 1 |

27 | 11/24 | No lecture -- Thanksgiving | |

28 | 11/29 | Streaming | lecture notes, part 2 |

29 | 12/1 | Last lecture |

### Homeworks:

*How to Format Homework:*
You can write your homework one of the following ways:

- Typeset your answers using LaTeX.
- Type your answers using a mainstream word processor.
- Neatly handwrite, then use a flatbed scanner or smartphone app (such as CamScanner) to produce a PDF. Do not simply take a photo and dump it into a PDF.

*How to Respond to Algorithm Problems:*
Oftentimes, a problem will ask you to find an algorithm. In this case, write your solution in the 4-part algorithm format detailed here.

*How to Submit Homework:*
Submit homework via Gradescope; we will not accept it via any other format. The Gradescope homework cutoff may be set later than 10:00 PM at our discretion, but this grace period does not change our official policy: if you encounter an issue at 10:05 PM and Gradescope doesn't let you submit the homework, it will not be accepted. Thus, you should submit your homework well in advance to reduce the risk of technical issues. (You can even submit an incomplete homework as backup, if you're working on the homework all the way up until the deadline.)

*Grading:*
You may request a regrade request (through Gradescope) within one week of when we release homework grades. Read the solutions carefully beforehand, and request a regrade only if you were graded inconsistently with the rubric. Make sure to clearly and politely explain why your solution was graded incorrectly. We reserve the right to regrade the whole homework assignment when you request a regrade, which could cause your score to change in either direction.

*Homework solutions:*
The staff posts detailed solutions of the homework problems each week, often with multiple solution approaches and commentary. Make it a priority to carefully read the solutions and compare them with your own work. Thoroughly understanding the solutions is a critical step to mastering the material. As an added incentive, we will draw from the homework problems when we write the exams.

*Homework parties:*
We will hold a weekly homework party in the Woz Lounge in Soda Hall, on Fridays from 2-5 PM.
Homework parties are completely optional.
This is an opportunity to find a group of other students
to work together on the homework. Students are expected to
form ad-hoc "pickup" homework groups, in the style of a pickup basketball game,
and help others in their group. Most students do better at and learn more from the homework when they work in groups, and the HW party is a great opportunity to meet homework partners. In addition, course staff will be present to answer questions and help you.

*Redemption files:*
It is important that you carefully read the posted solutions, even for problems you got right. To encourage this, you have the option of submitting a *redemption file*, a few paragraphs in which you explain, for each problem you choose to cover, what you did wrong and what the right idea was in your own words (not cutting and pasting from the solution!), and appending it to your homework. These will not be checked routinely, but we promise to look at them if they would make a difference in your grade (ie, you're close to a grade border. For example, as you review your solutions to HW1, you realize you had misunderstood question 3 and answered it incorrectly. You would write down what you just learned, and then submit it in your HW2 assignment the following week. Because these are mainly for your benefit, feel free to format them however is most useful for you.

### Quizzes

We'll have weekly reading quizzes, due Tuesday at noon. We'll post a link to the quiz on Piazza at least a few days before the quiz is due. This semester, we're piloting Google Forms for our quizzes, so please bear with us if there are any initial technical difficulties. Quizzes should be done individually (not in groups like the homework), and they should not take very much time if you've read the textbook. The goal of the quizzes is to incentivize you to read the textbook before the lecture, which we've found helps students get the most out of lecture.

### Exams

There will be two midterms and one final exam.
The midterms will be given on
Tuesdays **September 20** and
**November 1**, both at **6:30-8:30pm**.
The final exam will be **Thursday, 12/15, 11:30-2:30pm**.

All exams are mandatory. If you will be unable to attend any of these dates, you must contact the instructors via Piazza within one week of the first lecture. (We are currently aware of, and will accomodate, the conflicting final time with CS 161).

### Grading

We will compute grades from a weighted average, as follows:

- Homeworks: 30%
- Midterm 1: 15%
- Midterm 2: 15%
- Final exam: 35%
- Reading quizzes: 5%

### Course Policies

**Announcements:**
All announcements will be posted to Piazza. You are responsible
for staying up-to-date with announcements made on Piazza.

**Contact information:**
If you have a question, the best way to contact us is via
Piazza.
The staff (instructors, TAs, and readers) will check the site regularly,
and if you use it, other students will be able to help you too.
However, be very careful when asking about homework to avoid posting potential answers or hints. Please read the Homework FAQ post on Piazza before posting about homework.
If in doubt, mark your question as private.

If your question is personal or not of interest to other students, mark it as private on Piazza. If you wish to talk with one of us individually in person, you are welcome to come to any of our office hours.

**Collaboration:**
For each homework, we encourage you to collaborate in groups of at most 4 students total (It's OK to work informally with more students at a homework party). If you don't have a group to work with, come to the homework parties and
form one!
Clarifying concepts and discussing possible approaches to problems are
good forms of collaboration.
However, you must write up all solutions on your own, without ever
looking at or copying any other student's solutions.

**External sources:**
The textbook (including supplemental notes we will provide) as well as lecture should provide sufficient information to solve the homework problems. You may use the internet, other textbooks, etc. to provide context/supplementary information, but you should never attempt to look up solutions to the homework problems. If you find something useful from a source other than the textbook/notes (for example, a related theorem or explanation of a related problem), you must cite it in your solution (provide the URL). Of course, you should never copy or paraphrase any external source in your own solutions.

Cheating on homeworks or exams will be taken seriously. We refer you to the department's policy on academic dishonesty and the the campus honor code. We expect that most people can distinguish legitimate collaboration from cheating. If you're not sure whether a particular situation is cheating, ask an instructor. To be clear, the following behaviors are cheating:

- Using ideas from any external source without citing it.
- Splitting up the problems; for example, "You solve the first three problems, I'll solve the last three problems, and we'll tell each other how to solve them."
- Sharing your solutions, or partial solutions, with another student, even with the explicit understanding that they won't be copied or with students in your homework group.
- Receiving help on homeworks from students who have taken the course in previous semesters.
- Reviewing homework solutions from previous semesters.
- Searching the Internet for a solution to the exact problem we gave you on a homework.

You must ensure that your solutions will not be visible to other students. If you use Github or another source control system to store your solutions electronically, you must ensure your account is configured so your solutions are not publicly visible. Github offers free student accounts that allow you to keep your solutions private; please use one.

**Prerequisites:**
The prerequisites for CS 170 are CS 61B and CS70.
You will need to be comfortable with mathematical induction,
big-O notation, basic data structures, and programming in a standard imperative language (e.g., Java or C).

**Textbook:**
The required textbook is
Algorithms
(Dasgupta, Papadimitriou, and Vazirani) as our textbook.
All chapter numbers and exercise numbers in this course refer to the official paper textbook, not the online version.

**Electronics Policy:**
No cell phone, laptop, or other electronics use will be allowed in lecture: if you must use your phone or other device, please step outside. Academic studies have shown that students learn better when taking notes by hand rather than through a keyboard. The fact that it's impossible to write down everything the professor says is a feature, not a bug: it helps you learn by synthesizing the most important information.

**Discussion sections:**
Attendance at discussion sections is expected,
and sections may cover important material not covered in lecture. You may attend any discussion section, regardless of your registration.
Outside of your discussion section, you should feel free to attend any
of the staff office hours (not just your section TA's office hours)
and ask any of us for help.

**Don't be afraid to ask for help:**
Are you struggling? We'd much rather you approached us for help
than gradually fall behind over the semester until things become
untenable.
Sometimes this happens when students are afraid of an unpleasant
conversation with an instructor if they admit to not understanding
something. We would much rather deal with your misunderstanding
early than deal with its consequences later. Even if you are
convinced that you are the only person in the class that doesn't
understand the material, and that it is entirely your fault for
having fallen behind, please overcome your feeling of guilt and ask
for help as soon as you need it. Remember that the other students
in the class are working under similar constraints -- they are taking
multiple classes and are often holding down outside employment.
In past semesters, TAs have met with
many students for many reasons, like working through test-taking stress or
getting extra help on specific topics. Don't hesitate to ask us for help -- helping you learn the material is what we're paid to do, after all!

**Advice:**
The following tips are offered based on our experience with CS 170:

*Do the homeworks:*The effort you spend on the homework assignments is the largest factor in your mastery of the material, and thus performance in the class as a whole.

Also, regardless of how well you did on the homework,*read the sample solutions*, even for the problems you got right. You may well learn a different way of looking at the problem, and you may also benefit from emulating the style of the solutions.*Don't wait until the last minute to start homeworks!*Read through the homework problems as soon as they are available, and let them percolate in your brain. Schedule multiple times throughout the week to attempt the problems. Often, the solution will only come to you the second or third time you try a problem. Definitely do not wait until the night before it is due to start working on the homework. If you do this (alas, procrastination is all too common), (a) the stress will make it harder to be creative and solve the problems; (b) you will be tempted to ask your homework group for too many hints (or outright solutions) to the problems, which is cheating and impedes your learning, and (c) the stress will sap the joy of finding algorithms!*Make use of office hours and discussion sections:*The instructor and TAs hold office hours expressly to help you. You are free to attend as many office hours as you wish (you are not constrained just to use the office hours of your section TA).

Discussion sections are an opportunity for interactive learning. The success of a discussion section depends largely on the willingness of students to participate actively in it. As with office hours, the better prepared you are for the discussion, the more you are likely to get out of it.*Form study groups!*As stated above, you are encouraged to form small groups (two to four students) to work together on homeworks and on understanding the class material on a regular basis. In addition to being fun, this can save you a lot of time by generating ideas quickly and preventing you from getting hung up on some point or other. Of course, it is your responsibility to ensure that you contribute actively to the group; passive listening will likely not help you much. And recall the caveat above that you*must*write up your solutions on your own. Spend some time on your own thinking about each problem before you meet with your study partners; this way you will be in a position to compare ideas with your partners, and it will get you in practice for the exams.