15-850: Advanced Algorithms, Spring 2023
- Lecturer: Anupam
Gupta, GHC 7203, anupamg at cs.
- TAs: TBD
- Office hours: TBD
- Location: Posner 153, MWF
3:30-4:50 (note: 3 days a week).
- Piazza is the best way to contact the course staff.
- Gradescope should be used to submit HWs. Entry code: 3J7YX4
Announcements
- All course announcements will be on Piazza: please make sure you
check that regularly.
- The first lecture is on Wed Jan 18.
We plan to have 3 lectures a week for the first ~10 weeks, see schedule below.
- A tentative
schedule, though things will probably change around.
- Combined lecture notes from
the 2020 version.
- Course offerings in previous years: Fall
20, Fall
18,
Spring
17
and Spring
15.
Homeworks
Lectures
- Week #1: Spanning Trees
- Lecture 1. (Jan 18) MSTs. Recap Prim/Kruskal/Boruvka. The
Fredman-Tarjan \(O(m \log^\star n)\) time algorithm. (draft
notes)
- Lecture 2. (Jan 20) The
Karger-Klein-Tarjan randomized
algorithm. Directed MSTs (aka Arborescences and
Branchings). LP approaches.
(draft notes
for MSTs, arborescences)
Randomized MSTs:
Arborescences:
References on basic LPs and duality:
- Week #2: Shortest-Path Trees
- Lecture 3. (Jan 23) Min-Cost Arborescences using LPs
(finish). Shortest Paths.
(draft
notes, slides)
- Notes
from 210, 451,
and Jeff Erickson
(SSSP, APSP),
covering Dijkstra, Bellman-Ford-(Moore), Floyd-Warshall, and
Johnson's algorithm.
- History
of shortest-path algorithms, by Lex Schrijver. (CMU only)
- Lecture 4. (Jan 25) Shortest Paths using Min-Sum Products. Seidel's algorithm for
(unweighted undirected) APSP using matrix
multiplication. Motivate Low-Sretch Spanning Trees.
(draft notes for shortest paths, LDDs)
- Notes
from 210, 451,
and Jeff Erickson
(SSSP, APSP),
covering Dijkstra, Bellman-Ford-(Moore), Floyd-Warshall, and
Johnson's algorithm.
- R. Seidel. On
the all-pairs-shortest-path problem, STOC 1992. (and on
Wikipedia)
- Alon, Galil, Margalit,
Naor. Witnesses
for Boolean Matrix Multiplication and for Shortest Paths,
FOCS 1992.
- M. Fredman, New
Bounds on the Complexity of the Shortest Path Problem,
SICOMP 1976.
- Lecture 5. (Jan 27) Low-Diameter Decompositions and Low-stretch Trees. Bartal's
construction.
(draft
notes)
- Lecture
notes from our randomized algorithms course
(S11).
- Alon, Karp, Peleg,
West: A
Graph-Theoretic Game and its Application to the k-Server
Problem, SICOMP.
- Bartal: Probabilistic
Approximation of Metric Spaces and its Algorithmic
Applications, FOCS 96
Our presentation pretty
much followed his general construction.
- Fakcharoenphol, Rao,
Talwar, A
tight bound on approximating arbitrary metrics by tree>
metrics, STOC 03.
This paper gives the best
possible algorithm for the metric graph case.
- Abraham,
Neiman: Using
Petal-Decompositions to Build a Low Stretch Spanning
Tree.
This paper gives the current best algorithm
for the general graph case.
Some other low-diameter decomposition schemes:
And applications of low-stretch spanning trees to some problems:
- Week #3: Shortest-Path Trees (Finish), Matchings
- Lecture 6. (Jan 30) A Near-linear-time Algorithm for
Shortest Paths and Negative Edge Weights.
(handwritten notes)
- Lecture 7. (Feb 1) Matchings in Graphs: Combinatorial Algorithms
(draft
notes)
- Lecture 8. (Feb 3) Matchings in Graphs: Algebraic Algorithms
(draft
notes)
Some other papers that explore this approach:
- Week #4: Matchings (Contd)
- Lecture 8. (Feb 6) Matchings in Graphs: Linear Programs and
Integrality of Polytopes
(draft
notes)
Description
An intensive graduate course on the design and analysis of
algorithms. This course is primarily aimed at graduate and advanced
undergraduate students interested in doing research in theoretical
computer science. It is more specialized and in-depth than the
graduate level Algorithms in the Real World course (15-750), and the
undergraduate/masters' level Algorithms course (15-451/651). We will
cover advanced algorithmic ideas (some classical, some very recent),
and the theory behind it (theorems, proofs). For topics that were
covered in 451/750, the goal is to cover advanced content, proofs,
and new techniques.
Syllabus
The current list of potential topics are:
- MSTs. Recap Prim/Kruskal/Boruvka, an \(O(m \log^\star n)\) time
algorithm, a randomized linear-time algorithm, MSTs in directed graphs
- Shortest paths. recall Dijkstra/Bellman-Ford/etc, Seidel's
algorithm using matrix multiplication, recent near-linear time
algorithm with negative-weight edges.
- Matchings: classical matchings using augmenting paths,
matching using matrix inversions (Tutte/Lovasz, Mucha-Sankowski),
matchings using random walks, matchings using matrix balancing.
- The Experts algorithm via multiplicative weights, online gradient
descent.
- Flows: max-flows via electrical flows, Sherman's near-linear time max-flow.
- Linear and Convex Programming
- Solving convex optimization problems via gradient descent,
ellipsoid, interior-point methods
- Using convex optimization to solve combinatorial
problems (maybe)
- High-dimensional geometry: Dimension reduction and singular value
decompositions.
- Fixed-parameter tractable algorithms.
- Streaming algorithms (a.k.a. algorithms for big data)
- Online algorithms
- Approximation Algorithms
- The Sums-of-Squares Paradigm
- Submodular Optimization
Here are the
Fall
20,
Fall
18,
Spring
17
and Spring
15 versions of this course. The topics this year will be similar
(though not identical). I will take a poll in early March about topics to
cover in the last 4-5 lectures.
Effort and Criteria for Evaluation:
We have 3 lectures a week for the first ~10 weeks of the
semester. Attendance is required: it's a fast-moving course, so
if you miss lecture you may find it more difficult to keep up. We
have ~7 HWs (including HW0). Your grade will depend on these HWs,
class participation, and attendance.
We may record the lectures. However, I recommend you attend the
lectures in person when possible, and use these recordings to recap the material,
or to catch up in case you need to miss some lectures.
Textbook:
There is no textbook for the course. Most of our material is not in
textbooks (yet), so we will rely on lecture notes, papers and
monographs. We will provide you with lecture notes; we appreciate
feedback and suggestions for improvements.
Homeworks:
Some of the homeworks, some solved in collaboration (groups of two,
or at most three, please), and the others solved individually.
Homeworks are due at 11:59pm on the due date. They must be submitted
via gradescope. For each homework, there will be a two-day (48
hours) no-questions-asked extension. Students can use this extension
for any valid reason without having to ask the course staff. We do
not plan to provide additional extensions (barring exceptional
circumstances).
Collaboration policy: On solo homeworks (like HW0) you must solve
all the problems yourself. You must not discuss the problems with
others. On other collaboration HWs (like HW1) we permit--in fact, we
encourage--groups of two people (3 if you must). We require that
collaborations be "whiteboard" collaborations, you can discuss
problems and solutions with your group on a "whiteboard". After this
each person should go away and write their own solutions, which they
then submit. That is, collaboration should be limited to *talking*
about the problems, so that your write-up is written entirely by
you. No written work should be shared. Of course, you must also list
all members of your group. In all cases if you use any resources not
on the course webpage, you should cite them. Use Piazza to form groups
if you like.
You should ideally typeset your solutions, it makes grading much
easier for the TAs. But you can write and scan your HWs, as long as
you make them as legible as possible, please. Also, please aim for
clarity and conciseness in your solutions. Please cite all
collaborations and sources.
Prerequisites:
You should know material in standard UG courses in algorithms,
probability, and linear algebra very well. Above all, mathematical
maturity/curiosity and problem-solving skills are a must. That way you
can make up for gaps in your knowledge yourself. It is natural to not
know everything, or for you to get rusty on concepts, but you must
learn how to learn. This may seem vague, so here are concrete
things.
- Here are links to
some
resources for algorithms, probability, and linear algebra.
- You should know material from an undergraduate Algorithms
course, say until Lecture 16 (P/NP) from
our Spring
2018 version of 15-451. You should definitely know dynamic
programming, flows, basics of linear programming and LP duality,
NP-hardness, etc. If not, please pick these up from the 451 lecture
notes/textbooks/Wikipedia/etc (see resources above).
- Same for undergraduate probability and linear algebra
courses. E.g., for LinAlg, see whether you can solve
the first
homework from Steve Vavasis' Optimization course at Waterloo
(you can skip the coding if you want), we will add some more
exercises here. For probability (and
randomized algorithms), I will add some exercises as well, and will give some problems in HW0.
- HW0 will make an attempt to test this preparedness, and to give
you and us feedback.
FAQs:
- Q: Will you give the real-world context for the algorithms you
cover?
Not much. We will focus on the theoretical side (think:
algorithms, techniques, theorems, proofs), so we will not have
much time to motivate the choice of topics or give much
real-world context (of which there is plenty). If you are
looking for the latter, you should consider
taking 15-750: Algos in
the Real World (older
versions here)
which is aimed at a broader audience, and is being offered in
Spring 2023 as well.
- Q: I am on the wait-list: will I get in?
We hope everyone who wants to take the class will get
in. (Usually some students are "shopping around" in the first
couple weeks, and things settle down after that.) Just attend
the lectures, and we will try to get clear the wait-lists
soon. OTOH, if you are on the wait-list because you have too
many credits, or are enrolled for a course with a conflicting
time-slot, you should fix those issues yourself.
- Q: I am struggling with the homework: what should I do?
A little struggle in doing the homework is expected (and
healthy), since these are not trivial problems, you're probably
learning something new. Think about the problem, bounce ideas
around (with your team-mates or the course staff), think some
more, and repeat until you have a solution. Of course, make sure
you are putting in the time to think. Working with others is a
good way to learn too, with the usual caveats. However, if you
are struggling a fair bit, and if the struggle is unpleasant for
you, come talk to us. You may consider taking 15-451 (UG Algos)
or 15-750 (Algos in the Real World) instead of this
course.
- Q: Can I attend via Zoom, or skip lectures and just follow the
course videos instead?
We require synchronous (in-person) attendance in this
course. If you want to get the most out of the course, I
strongly recommend you attend lectures in-person. Please use
the videos as supplemental resources rather than the basic
source of learning. That said, we won't actively take attendance
(unless it becomes necessary), and your missing a lecture or two
will not be held against you. If you have compelling reasons for
missing more than a couple of lectures during the semester,
please come talk to us.
Your Health & Well-being
This is an intensive (and somewhat intense) course: 3 days a week,
studying new/advanced topics, several HWs. One major goal is that you
enjoy taking it and learning this new cool material, as much as I
enjoy teaching it. Part of making sure you have fun involves taking
care of yourself. Do your best to maintain a healthy lifestyle this
semester by eating well, exercising, avoiding drugs and
alcohol, getting
enough sleep and taking some time to relax. This will help you
achieve your goals and cope with stress.
If you or anyone you know experiences any academic stress,
difficult life events, or feelings like anxiety or depression, we
strongly encourage you to seek support. Counseling and Psychological
Services (CaPS) is here to help: call 412-268-2922 and visit
http://www.cmu.edu/counseling/. Consider reaching out to a friend,
faculty or family member you trust for help getting connected to the
support that can help.
Diversity in the Classroom
In this course, we strive to treat everyone with respect, and provide
everyone with the best learning experience we can. We believe that
diversity, equity, and inclusion should be our goals, not only because
they fuel excellence and innovation, but because these are just. Your
suggestions are encouraged and appreciated. Please let us know ways to
improve the effectiveness of the course for you personally, or for
others.
Accommodations for Students with Disabilities:
If you have a disability and are registered with the Office of
Disability Resources, I encourage you to use their online system to
notify me of your accommodations and talk to me to
discuss your needs with me as early in the semester as possible. Since
this is a fast-moving course, we should discuss how to make things work
out. I will work with you to ensure that accommodations are provided as
appropriate. If you suspect that you may have a disability and would
benefit from accommodations but are not yet registered with the Office
of Disability Resources, I encourage you to contact them at
access@andrew.cmu.edu.
Academic Integrity
Honesty and transparency are important features of good
scholarship. Equally importantly, plagiarism and cheating are serious
academic offenses with serious consequences. You should cite any
sources you use, other than the lectures notes we give you. (E.g., if
you refer a reserch paper to solve a problem, you should say that.)
If you are discovered engaging in either behavior in this course, you
will earn a failing grade on the assignment in question, and further
disciplinary action may be taken. For a clear description of what
counts as plagiarism, cheating, and/or the use of unauthorized
sources, please see
the University
Policy on Academic Integrity and
the Carnegie
Mellon Code on Academic Integrity.
Maintained by Anupam Gupta