### Instructors:

Prof. Umesh Vazirani (office hours Wed 1:30-2:30, Soda 671)

### Head TAs:

Cathy Wu (office hours Mon 5-6, Wed 4-5)

### TAs:

Aviad Rubinstein (office hours Mon 2-4)

Barak Gila (office hours Mon 10-11, Fri 9-10)

Cheng Xiang (office hours Fri 4-6)

Chenyang Yuan (office hours Mon 11-12 at Soda 411, Thu 5-6 at Soda 611)

Manish Raghavan (office hours Wed 3-4, Thu 1-2)

Nathan Mandi (office hours Tues 1-3)

Patrick Lutz (office hours Mon 9-10, Fri 10-11)

Wesley Hsieh (office hours Fri 3-4)

### Lectures:

### Sections:

*101.*Wed 9:00-10:00, 289 Cory (Chenyang)

*102.*Wed 11:00-12:00, 122 Barrows (Abhishek)

*103.*Wed 11:00-12:00, 238 Kroeber (Nathan)

*104.*Wed 12:00-1:00, 2030 VLSB (Patrick)

*105.*Wed 12:00-1:00, 2066 VLSB (Wesley)

*106.*Wed 1:00-2:00, 209 Dwinelle (Manish)

*107.*Wed 1:00-2:00, 2062 VLSB (Cheng)

*108.*Wed 2:00-3:00, 283 Dwinelle (Manish)

*109.*Wed 2:00-3:00, 2066 VLSB (Cheng)

*110.*Wed 2:00-3:00, 2062 VLSB (Cathy)

*111.*Wed 3:00-4:00, 103 Moffitt (Cathy)

*112.*Wed 3:00-4:00, 220 Wheeler (Chenyang)

*113.*Wed 4:00-5:00, 2030 VLSB (Abhishek)

*114.*Wed 4:00-5:00, 2032 VLSB (Aviad)

*115.*Wed 5:00-6:00, 2030 VLSB (Patrick)

*116.*Wed 5:00-6:00, 2032 VLSB (Aviad)

*117.*Thu 10:00-11:00, 2030 VLSB (Barak)

*118.*Fri 10:00-11:00, 6 Evans (Barak)

*119.*Thu 9:00-10:00, 320 Soda (Barak)

### Addresses:

Announcements, questions: the class Piazza site.

Feel free to mark your question as private if you don't want other students to see it.

### Lectures:

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

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

Tues 1/19 | Introduction, big-O notation, arithmetic | Chapter 0, Chapter 1.1 |

Thurs 1/21 | Divide-and-Conquer | Chapter 2.1, 2.2, 2.3 |

Tues 1/26 | Divide-and-Conquer | Chapter 2.4, 2.5, 2.6 |

Thurs 1/28 | Fast Fourier Transform | Chapter 2.6 |

Tues 2/2 | Decompositions of graphs | Chapter 3 |

Thurs 2/4 | Paths in graphs | Chapter 4.1, 4.2, 4.3, 4.4 |

Tues 2/9 | Paths in graphs | Chapter 4.4, 4.5, 4.6, 4.7 |

Thurs 2/11 | Greedy Algorithms | Overview of Chapter 5, Chapter 5.4 |

Tues 2/16 | Midterm 1 | |

Thurs 2/18 | Minimum Spanning Trees | Chapter 5.1 |

Tues 2/23 | Greedy Algorithms | Chapter 5.2, 5.3 |

Thurs 2/25 | Dynamic Programming | Chapter 6 |

Tues 3/1 | Dynamic Programming | Chapter 6 |

Thurs 3/3 | Linear Programming | Chapter 7.1 |

Tues 3/8 | Network Flow | Chapter 7.2 |

Thurs 3/10 | Duality | Chapter 7.4 |

Tues 3/15 | Zero-Sum Games | Chapter 7.5 |

Thurs 3/17 | Reductions, Bipartite Matching | Chapter 7.3 |

Tues 3/29 | Midterm 2 | |

Thurs 3/31 | Search Problems | Chapter 8.1 |

Tues 4/5 | NP-Completeness | Chapter 8.2, 8.3 |

Thurs 4/7 | Coping with NP-Completeness | Chapter 9 |

Tues 4/12 | Multiplicative updates | N/A |

Thurs 4/14 | Applications of multiplicative updates | N/A |

Tues 4/19 | Modular arithmetic, Primality Testing | Chapter 1.2, 1.3 |

Thurs 4/21 | Hashing, Sketching, Streaming | Chapter 1.5 + Notes |

Tues 4/26 | Hashing, Sketching, Streaming | Notes |

Thurs 4/28 | Quantum factoring | Chapter 10 |

Fri 5/13 | Final Exam7:00-10:00pm |

### Homeworks:

Homeworks are due Mondays at 11:59 PM.** No late homeworks accepted. See Piazza for the homework and homework submission instructions.**

*Homework Timeline:*
Every Monday evening, homework is posted under the Resources tab. **It is due the following Monday by 11:59 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 assignments.

*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.**

**List your collaborators**on the first page of your submission. If you have no collaborators, you must explicitly list "none".

*How to Respond to Algorithm Problems:*
Oftentimes, a problem will ask you to "give/design/devise/formulate/create/etc. an algorithm" or to "show how" to solve some computational task. In this case, you must respond in the "4-part algorithm format" detailed here.

*How to Submit Homework:*
Homework is submitted via Gradescope.
If Gradescope is experiencing site-wide issues, post on Piazza immediately.

The cutoff for submissions *on Gradescope* may be set later than 11:59 PM at our discretion, but this does not change our official policy: *homework is due by 11:59 PM*. For example, if Gradescope has site-wide issues at 12:05 AM and won't let you submit, your homework will not be accepted. Plan to turn in homework safely in advance.

*Grading:*
You may request a ref (through Gradescope) within one week of homework return. **Read the official solutions; request a regrade only if you were graded inconsistently with the rubric.** Your grade may go up, down, or remain constant; the readers' sole priority is consistency.

*Homework Resubmissions:*
Each week, after solutions are released (shortly after homework is due), you may choose a *single* problem to revise and fix your solution to. Submit your answer to this one problem in a separate Gradescope assignment; the deadline is **11:59 PM on** Tuesday (i.e. you have one day to resubmit). We will grade the resubmitted answer with the regularly-submitted answers.
Resubmitted answers should not copy or paraphrase official solutions, but may incorporate the ideas of the solution in your words.

*Homework parties:*
We will hold a weekly homework party in Cory 540. See Piazza (@21) for the exact time each week.
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. TAs will be present to help you.
If the room is crowded, please, be kind and make room for others
by leaving if you can find an alternative source of assistance.
When the room is not crowded, people from the class are welcome to
just hang out as long as they aren't bothering other people.
For us to be able to continue to offer this service,
you all have to be very responsible in taking care of the room, not
make a mess, and put things back the way they were before you leave.

*Extra credit problems:*
Do the extra credit problems only if you really enjoy working on these
problems and want an extra challenge.
It is likely not the most efficient manner in which to maximize
your score.

*Frequently asked questions:* See @19 on Piazza.

### Discussion Sections

### Reading Quizzes

Reading quizzes must be completed online, before noon each Tuesday.

Do the reading for the upcoming lecture before taking the quiz. Quizzes must be done on your own (no collaboration, and no discussion of the questions or your answers with others). Quizzes will be made available on this web page the Friday before they are due.

- Quiz #3 (due 2/2 noon), Solution.
- Quiz #4 (due 2/9 noon), Solution.
- Quiz #5 (due 2/18 noon), Solution.
- Quiz #6 (due 2/23 noon), Solution.
- Quiz #7 (due 3/1 noon), Solution.
- Quiz #8 (due 3/8 noon), Solution.
- Quiz #9 (due 3/15 noon), Solution.
- Quiz #10 (due 3/31 noon), Solution.
- Quiz #11 (due 4/5 noon), Solution.
- Quiz #13 (due 4/19 noon), Solution.
- Quiz #14 (due 4/26 noon), Solution.

### Exams

There will be two midterms and one final exam.
The midterms will be given on
Tuesdays **February 16** and
**March 29**, both at 7:00-9:00pm.
The final exam will be **Friday, May 13, 7-10 PM**.

All exams are mandatory. There will be no make-up exams. If you will be unable to attend any of these dates, you must contact the instructor (via a message on Piazza) within one week after the first lecture.

### Grading

We will compute grades from a weighted average, as determined by the higher of the following two calculation methods:

Method 1:

- Homeworks: 20%
- Midterm 1: 20%
- Midterm 2: 25%
- Final exam: 35%

Method 2:

- Homeworks: 20%
- Midterm 1: 20%
- Midterm 2: 25%
- Final exam: 30%
- 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
the class Piazza site.
The staff (instructors and TAs) will check the site regularly,
and if you use it, other students will be able to help you too.
**Avoid posting answers or hints on homework
questions before the homework is due.**
If in doubt, mark your question as private.

If your question is personal or not of interest to other students, you are encouraged to mark the question 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. We prefer that use these methods instead of sending us email; email regrettably does not scale well to a class of this size.

**Collaboration:**
For each homework, you may collaborate with at most 4 other students.
We encourage you to collaborate with your fellow students (in small groups)
on the homeworks.
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.
If you are tempted to look at someone else's solutions (this includes over the Internet), keep in mind that the exams carry much more weight than the homeworks, and there is a strong correlation between students' exam scores and the effort they put into the homework.

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. In particular, keep the following in mind:

*Give credit.*You must list any students you worked with, as well as other sources of information you used, on the first page of your homework.*Don't share solutions.*Working together means clarifying concepts and discussing possible approaches. Never look at any part of someone else's solution (including online) and never share any part of your own work with another student.*When in doubt, ask.*If you're not sure whether a particular situation constitutes cheating, ask a TA or the instructor.

We expect that most people can distinguish legitimate
collaboration from cheating, but here are some more details.
Telling someone who is not in your homework group how to solve a
homework problem is not allowed.
Splitting up the problems -- "you solve the first three
problems, I'll solve the last three problems, and we'll tell each
other how to solve them" -- is not collaboration and not allowed.
No matter what, *you must write up your solutions
entirely on your own*.
For homeworks, you must **never** read, see, or copy
the solutions of other students, and you must not allow other
students to see your solutions.
You must never share your solutions, or partial solutions,
with another student -- not even with the explicit understanding
that they won't be copied; not even with students in your
homework group.
You must not receive help on homeworks from students
who have taken the course in previous years.
You must not review homework solutions from previous years.
You must not search the Internet for a solution to the exact problem
we gave you on a homework.
The only way to learn algorithms to practice, practice, practice, so
we want you to solve the problems on your own, not rely on other sources
as a crutch.

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. If you use Github, 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**
In order to minimize the distraction that lecture usage of electronics (e.g. laptops) poses to other students,
we are limiting electronics usage to the back of the lecture hall (the last few rows).

**Discussion sections:**
Attendance at discussion sections is expected,
and sections may cover important material not covered in lecture. You may attend any discussion section.
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.

**Re-grading policies:**
Regrading of homeworks or exams will only be
undertaken in cases where you believe there has been
a genuine error or misunderstanding.
Any requests for grade changes or re-grading must be made within
one week of when the work was returned.
Submit re-grade requests via Gradescope.
We will only accept homework regrade requests if you
believe that your answer on that problem is 100% correct and you should
have received full credit; we will not regrade homeworks in cases where
you believe that you should have received more partial credit.
We also will not accept regrade requests for 0.01-point deductions;
those exist as a way to give you constructive feedback on your
solutions, to help you improve, without affecting your grade.

Bear in mind that our primary aim in grading is consistency, so that all students are treated the same; for this reason, we will not adjust the score of one student on an issue of partial credit unless the score allocated clearly deviates from the grading policy we adopted for that problem.

**Late homework policy:**
We will give no credit for homework turned in after the deadline.
Please don't ask for extensions.
We don't mean to be harsh, but we prefer to make model
solutions available shortly after the due date, which makes it
impossible to accept late homeworks.

**Extra credit opportunities:**
The instructor reserves the right to offer optional activities
that provide a small number of extra credit, for those eager for
a tougher challenge.
We recommend you do them only if you enjoy these problems, as spending
effort on them is likely not the most efficient way to maximize your
final course grade.

**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 a professor 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.
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:

*Don't fall behind!*In a conceptual class such as this, it is particularly important to maintain a steady effort throughout the semester, rather than hope to cram just before homework deadlines or exams. This is because it takes time and practice for the ideas to sink in. Make sure you allocate a sufficient number of hours every week to the class, including enough time for reading and understanding the material as well as for doing assignments. (As a rough guide, you should expect to do at least one hour of reading and two hours of problem solving for each hour of lecture.) Even though this class does not have any major projects, you should plan to spend as much time on it as your other technical classes.*Do the homeworks!*The homeworks are explicitly designed to help you to learn the material as you go along. Although the numerical weight of the homeworks is small, there is usually a strong correlation between homework scores and final grades in the class. (The most common denominator among people who do poorly in the class is that they skipped several homework assignments or multiple homework problems.)

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. (In science people learn a lot from emulating the approach of more experienced scientists.)*Don't wait until the last minute to start homeworks!*My best advice is to read through the homework problems as soon as they are available, and let them percolate in your brain. Think through possible approaches while you are waiting in line, or stuck in an elevator, or whatever. Sleeping on a problem has often helped people to come up with a creative approach to it. Definitely do not wait until the night before it is due to start working on the homework.*Make use of office hours!*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). You will also likely get more out of an office hour if you have spent a little time in advance thinking about the questions you have, and formulating them precisely. (In fact, this process can often lead you to a solution yourself!)*Take part in discussion sections!*Discussion sections are*not*auxiliary lectures. They 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. I strongly advise you to 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. Make sure you work through all problems yourself. I've seen a few groups that split up the problems ("you do Problem 1, I'll do Problem 2, then we'll swap notes"); not only is this a punishable violation of our collaboration policies, it also ensures you will learn a lot less from this course.