Welcome to the class! A word of caution: Information on this site is not final until the class starts.
Lecturer: Valentin Polishchuk (email)
Schedule 2024
f2f welcome meeting: Tue week 36 ( Sep 2, 2025) 13-15 K21
otherwise no lectures -- watch the videos at your pace and submit the HWs by the deadlines; contact the lecturer with questions whenever you have them
U/G for the labs. Labs test is separate from the exam
U,3,4,5 on the written exam (see Practice exam title page for how many points are needed for the different grades). The exam is separate from the labs test
Homeworks are not graded, but you have to do them to be ready for the exam (the exam problems will be similar to the HW problems; see Practice exam for an example). After you submit a homework, I may schedule a session with your group to speak about your solutions
Group work is allowed (and encouraged); feel free to form the groups as you like (there are no limits on the group size). Please submit one HW (.pdf) per group.
Homework 1 (Shortest Path) recommended to be done in week 37
Homework 2 (MaxFlow) recommended to be done in 38
Homework 3 (VC, Matching, IS) recommended to be done in 39
Homework 4 (DAG, Stable matching) recommended to be done in 40
Homeworks are not mandatory and are not graded. The points for the problems are given only to give you a feel of how many points you may get for similar problems on the exam.
Maximum Flows (video) [Around min 50, I made a mistake working out an example (corrected directly afterwards in the video); I decided to keep it since it's somewhat instructive (an edge must be saturated after pushing extra flow)]
Vertex Cover (Facility location -- Covering), Matching (Distribution -- Packing), Independent Set (Job Scheduling) (video)
Max bipartite matching (time permitting)
Most lectures were recorded during 2020 class, therefore you may hear references to chat, times, etc
Errors in videos are mentioned in square brackets [] after the link to the video
Some lectures refer to other's clips/applets as examples -- you may watch/use them by following the links from the slides
Sorry if YouTube shows ads before the videos -- it's YouTube monetizing, not me. (AdBlockers on laptop and NewPipe on Android may help.)
Dijkstra Example slides -- by our own Oskar and Björn from BLA'20!
A more profound lecture on Dijkstra (LiU ID required)
Stable matching applets: http://sephlietz.com/gale-shapley/ (text only), http://mathsite.math.berkeley.edu/smp/smp.html (with animation)