TNSL20
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 (tentative)
f2f welcome meeting: Tue, Sep 3 13-15
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
Grading
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
Homeworks
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 36
Homework 2 (MaxFlow) recommended to be done in 37
Homework 3 (VC, Matching, IS) recommended to be done in 38
Homework 4 (DAG, Stable matching) recommended to be done in 39
Homeworks 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.
Slides and Videos
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)
Notes
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.)
Further material
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)