Problem Sets (75%):
There will be 4 problem sets. Here is the schedule:
 Problem Set #1 (Posted Tue Jan 12; due Tue Jan 26 midnight.)
 Problem Set #2 (Posted Tue Jan 26; due
Tue Feb 9 midnight.)
 Problem Set #3 (Posted Tue Feb 9; due Tue Feb 23 midnight.)
 Problem Set #4 (Posted Tue Feb 23; due Tue Mar 8 midnight.)
 Problem Set Policies:
 These are challenging are you are strongly encouraged to form
groups, of up to three students. Each group should turn in a single
writeup (all students of the group receive the same score).
 You can form different groups for different problem sets.
 You can discuss problems with students from other groups
verbally and at a high level only.

Except where otherwise noted, you may refer to your course notes, the
textbooks and research papers listed on the course Web
page only. You cannot refer to textbooks, handouts, or
research papers that are not listed on the course home page. If you
do use any approved sources, make you sure you cite them
appropriately, and make sure that all your words are your own.
 You are strongly encouraged to use LaTex to typeset your writeup.
Here's a LaTeX template that you can use to
type up solutions. Here
and here are good
introductions to LaTeX.
 We expect you to follow
the honor code.
 Submission instructions:
We are using Gradescope for the homework submissions. Go to
www.gradescope.com to either login or create a new
account. Use the
course code 9B3BEM to register for CS261. Only one group member
needs to submit the assignment. When submitting, please remember to
add all group member names onto Gradescope.
 Late Days:
 One late day equals a 24hour extension.
 Each student has two free late days.
 At most two late days can be applied to a single assignment;
after Thursday midnight (following the original due date) no solutions
will be accepted.
 Each late day used after the first two will result in a 25%
penalty.
 Example: a student had one free late day remaining but his/her
group uses two late days on a Problem Set. If the group's writeup
earns p points, the student receives a final score of .75*p points
for the assignment.
 InClass Final Exam (25%):
Date: Monday March 14, 3:306:30 PM. Location: room 300300.
 Roughly half of the questions will be variations on exercise set
questions.
 The exam is closedbook/computer; however, you are allowed
to bring two
doublesided sheets (4 pages) of notes, which you must prepare
by yourself.
PART I: COMBINATORIAL OPTIMIZATION
 Lecture 1 (Tue Jan 5): Course goals. Introduction to the maximum flow problem. The FordFulkerson algorithm.
 Lecture 2 (Thu Jan 7): Proof of the maxflow/mincut theorem. Augmenting on shortest paths (EdmondsKarp). The blocking flow approach (Dinic).
 Lecture 3 (Tue Jan 12): Maximum flow: the pushrelabel approach.
 Lecture 4 (Thu Jan 14): The minimum st cut problem.
Application to image segmentation. Reducing bipartite matching to maximum flow. Hall's theorem.
 Lecture 5 (Tue Jan 19): Minimumcost bipartite matching.
Optimality conditions. The Hungarian (KuhnMunkres/Jacobi) algorithm.
 Lecture 6 (Thu Jan 21):
Finish the Hungarian algorithm.
Survey of efficiently solvable generalizations of maximum flow and
mincost bipartite matching (mincost flow, nonbipartite matching, etc.).
PART II: LINEAR PROGRAMMING AND DUALITY
 Lecture 7 (Tue Jan 26): Introduction to linear
programming. Geometric intuition. Applications: maximum and minimumcost
flow; linear regression; learning a linear classifier, with extensions
to minimizing hinge loss and augmented feature sets.
 Lecture 8 (Thu Jan 28): Linear programming duality.
A recipe for taking duals. The meaning of the dual. Weak duality and
complementary slackness conditions. The maxflow/mincut theorem via
duality.
 Lecture 9 (Tue Feb 2):
An LPduality view of the Hungarian algorithm.
Strong duality. Separating hyperplanes and Farkas's Lemma.
 Lecture 10 (Thu Feb 4):
The minimax theorem for twoplayer zerosum games.
Survey of algorithms for linear programming: the simplex method, the
ellipsoid method, and interior point methods.
PART III: ONLINE ALGORITHMS
 Lecture 11 (Tue Feb 9):
Online decisionmaking. Regret. The multiplicative weights
algorithm. Minimax revisited.
 Lecture 12 (Thu Feb 11):
Applications of multiplicative weights. Linear classifiers revisted.
Minimax revisited (again). Applications to fast approximate flows.
 Lecture 13 (Tue Feb 16):
Online algorithms: minimum makespan scheduling and Steiner tree.
 Lecture 14 (Thu Feb 18):
Online algorithms: an optimal online algorithm for
maximum bipartite matching.
PART IV: ALGORITHMS FOR NPHARD PROBLEMS
 Lecture 15 (Tue Feb 23):
Introduction to approximation algorithms. Scheduling, knapsack,
Steiner tree, set coverage, influence maximization.
 CS161level videos on NPcompleteness (Part XVI) and
approximation algorithms for the knapsack problem
(Part XVIII).
 Lecture 16 (Thu Feb 25):
The Traveling Salesman Problem. Inapproximability in the general case.
The MST heuristic for metric TSP. Christofides's algorithm for metric
TSP. Asymmetric TSP (ATSP) and minimumcost cycle covers.
 Lecture 17 (Tue Mar 1):
Linear programming and approximation algorithms.
The set cover problem. A dual interpretation of the greedy algorithm. LP rounding and primaldual approximation algorithms for the vertex cover problem.
 Lecture 18 (Thu Mar 3):
Five essential tools for the analysis of randomized algorithms
(approximate and otherwise).
Linearity of expectation and a 7/8approximation for MAX 3SAT. Markov
and Chebyshev inequalities. Chernoff bounds. Running example:
analysis of hashing. Randomized rounding for lowcongestion
routing.
 Lecture 19 (Tue Mar 8):
Beating bruteforce search for NPhard problems.
Fixedparameter tractability: vertex cover revisited.
Exact TSP via dynamic
programming. A random search algorithm for 3SAT.
 Lecture 20 (Thu Mar 10):
The maximum cut problem. Semidefinite programming (SDP).
Randomized hyperplane rounding. Top 10 list.