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
write-up (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 write-up.
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 24-hour 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 write-up
earns p points, the student receives a final score of .75*p points
for the assignment.
- In-Class Final Exam (25%):
Date: Monday March 14, 3:30-6:30 PM. Location: room 300-300.
- Roughly half of the questions will be variations on exercise set
questions.
- The exam is closed-book/computer; however, you are allowed
to bring two
double-sided 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 Ford-Fulkerson algorithm.
- Lecture 2 (Thu Jan 7): Proof of the max-flow/min-cut theorem. Augmenting on shortest paths (Edmonds-Karp). The blocking flow approach (Dinic).
- Lecture 3 (Tue Jan 12): Maximum flow: the push-relabel approach.
- Lecture 4 (Thu Jan 14): The minimum s-t cut problem.
Application to image segmentation. Reducing bipartite matching to maximum flow. Hall's theorem.
- Lecture 5 (Tue Jan 19): Minimum-cost bipartite matching.
Optimality conditions. The Hungarian (Kuhn-Munkres/Jacobi) algorithm.
- Lecture 6 (Thu Jan 21):
Finish the Hungarian algorithm.
Survey of efficiently solvable generalizations of maximum flow and
min-cost bipartite matching (min-cost flow, nonbipartite matching, etc.).
PART II: LINEAR PROGRAMMING AND DUALITY
- Lecture 7 (Tue Jan 26): Introduction to linear
programming. Geometric intuition. Applications: maximum and minimum-cost
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 max-flow/min-cut theorem via
duality.
- Lecture 9 (Tue Feb 2):
An LP-duality view of the Hungarian algorithm.
Strong duality. Separating hyperplanes and Farkas's Lemma.
- Lecture 10 (Thu Feb 4):
The minimax theorem for two-player zero-sum 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 decision-making. 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 NP-HARD PROBLEMS
- Lecture 15 (Tue Feb 23):
Introduction to approximation algorithms. Scheduling, knapsack,
Steiner tree, set coverage, influence maximization.
- CS161-level videos on NP-completeness (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 minimum-cost 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 primal-dual 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/8-approximation for MAX 3SAT. Markov
and Chebyshev inequalities. Chernoff bounds. Running example:
analysis of hashing. Randomized rounding for low-congestion
routing.
- Lecture 19 (Tue Mar 8):
Beating brute-force search for NP-hard problems.
Fixed-parameter 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.