Videos
I occasionally create videos about math/computer science that I put up on my YouTube channel. They are created mainly using Manim and their source code can be found here.
This page contains a list of all of the released ones (by category and date). Click on the short description to expand!
[newest] The Art of Linear Programming
Graph Theory
-trees/thumbnail.webp)
2023/04/09 – The Most Elegant Search Structure | (a,b)-trees [YouTube]
An introduction to (a,b)-trees -- definition, operations, usage.
------------------ Timetable: 0:00 - Fever dream? 0:28 - Introduction 2:04 - Basics 3:47 - Search 4:33 - Insertion 6:06 - Deletion 8:51 - Selecting (a, b) 10:36 - Usage 11:22 - Outro ------------------ Source code: https://github.com/xiaoxiae/videos/tree/master/17-ab/ Music (in the order it appears in the video): ► The Big Ten by Blue Dot Sessions: https://app.sessions.blue/browse/track/170869 ► Cases to Rest by Blue Dot Sessions: https://app.sessions.blue/browse/track/139762 ► Maisie Dreamer by Blue Dot Sessions: https://app.sessions.blue/browse/track/31458 ► Thannoid by Blue Dot Sessions: https://app.sessions.blue/browse/track/126782 Software used: ► Manim (animation software): https://github.com/ManimCommunity/manim/ ► Kdenlive (video cutting): https://kdenlive.org/en/ ► ffmpeg (audio/video processing): https://ffmpeg.org/ ► OBS (audio/video recording): https://obsproject.com/download ► arecord (audio recording): https://linux.die.net/man/1/arecord ► sox (audio processing): http://sox.sourceforge.net/ ► Inkscape (vector image editing): https://inkscape.org/ ► Stable Diffusion (image generation): https://stablediffusionweb.com/ Social media: ► Website (for other things I'm up to): https://slama.dev/ ► Patreon (if you'd like to support me): https://www.patreon.com/TomasSlama Thanks to Matěj Kripner, František Voldřich, Jakub Pelc, Hansen Pascal, and guys at @polylog7346 for valuable feedback. ------------------ [CZ] Martin Mareš: Průvodce labyrintem algoritmů: http://pruvodce.ucw.cz/ [EN] Effect of Node Size on the Performance of Cache-Conscious B+-trees: https://pages.cs.wisc.edu/~jignesh/publ/cci.pdf [EN] frozenca/BTree: open-source C++ B-tree implementation: https://github.com/frozenca/BTree [EN] Other (a,b)-tree-related resources: https://en.wikipedia.org/wiki/(a,b)-tree https://en.wikipedia.org/wiki/B%2B_tree https://en.wikipedia.org/wiki/B-tree
2021/10/06 – Cayley’s Formula [YouTube]
An elegant proof of the number of spanning trees of a complete graph.
------------------ Timetable: 0:00 - Introduction 0:13 - Definitions 0:34 - Statement 1:03 - Proof 3:37 - Outro Source code: https://github.com/xiaoxiae/videos/tree/master/07-cayley Music: - Maisie Dreamer by Blue Dot Sessions: https://app.sessions.blue/browse/track/31458 Software used: Manim (animations): https://github.com/ManimCommunity/manim/ Kdenlive (video): https://kdenlive.org/en/ ffmpeg (video): https://ffmpeg.org/ Vector Magic (images): https://vectormagic.com/ arecord (audio): https://linux.die.net/man/1/arecord sox (audio): http://sox.sourceforge.net/ ------------------ [CZ] My notes on Martin Koutecký's Combinatorics and Graphs 1 lecture: https://slama.dev/lecture-notes/kombinatorika-a-grafy-i/
2021/08/23 – The Blossom Algorithm [YouTube]
An overview of the Blossom algorithm for maximum graph matching.
------------------ Proofs: [EN] http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/tarjan-blossom.pdf - graph has an a.p. if and only if the matching is not maximal: theorem 2.4 - graph has an a.p. if and only if compressed graph has an a.p.: theorem 2.9 Timetable: 0:00 - Introduction 0:41 - Definitions 1:02 - Augmenting paths 1:42 - Maximum tree matching 3:06 - Blossoms 4:06 - Maximum general graph matching 4:59 - Overview 5:46 - Outro Source code: https://github.com/xiaoxiae/videos/tree/master/06-edmonds-blossom Music: Maisie Dreamer by Blue Dot Sessions: https://app.sessions.blue/browse/track/31458 Software used: Manim (animations): https://github.com/ManimCommunity/manim/ Kdenlive (video): https://kdenlive.org/en/ ffmpeg (video): https://ffmpeg.org/ Vector Magic (images): https://vectormagic.com/ arecord (audio): https://linux.die.net/man/1/arecord sox (audio): http://sox.sourceforge.net/ ------------------ [CZ] My notes on Martin Koutecký's Combinatorics and Graphs 2 lecture: https://slama.dev/lecture-notes/kombinatorika-a-grafy-ii/ [EN] Sketchy Notes on Edmonds’ Incredible Shrinking Blossom http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/tarjan-blossom.pdf [EN] Amy Shoemaker and Sagar Vare's report on the blossom algorithm: https://web.stanford.edu/~rezab/classes/cme323/S16/projects_reports/shoemaker_vare.pdf [EN] Blossom algorithm on Wikipedia: https://en.wikipedia.org/wiki/Blossom_algorithm
2021/06/01 – Weak Perfect Graph Theorem [YouTube]
A proof of the weak perfect graph theorem.
------------------ Timetable: 0:00 - Introduction 0:34 - Graph complement 0:49 - Clique and independent set 1:32 - Induced subgraph 1:53 - Chromatic number 2:08 - Perfect graph 2:24 - Observations 3:29 - Lemma 1 4:55 - Lemma 2 6:31 - Weak perfect graph theorem 9:41 - Strong perfect graph theorem Source code: https://github.com/xiaoxiae/videos/tree/master/04-perfect-graphs Music: Maisie Dreamer by Blue Dot Sessions: https://app.sessions.blue/browse/track/31458 Software used: Manim (animations): https://github.com/ManimCommunity/manim/ Kdenlive (video): https://kdenlive.org/en/ ffmpeg (video): https://ffmpeg.org/ arecord (audio): https://linux.die.net/man/1/arecord sox (audio): http://sox.sourceforge.net/ Special thanks to Jakub Medek, Matěj Kripner and Martin Koutecký for help with catching errors and providing feedback. ------------------ [CZ] Martin Koutecký's lecture on Combinatorics and Graph Theory: https://research.koutecky.name/db/teaching:kg22021_prednaska [EN] Padraic Bartlett's notes on the perfect graph theorem: http://web.math.ucsb.edu/~padraic/mathcamp_2011/perfectgraphs/MC2011_perfectgraphs_wk1_day4.pdf http://web.math.ucsb.edu/~padraic/mathcamp_2011/perfectgraphs/MC2011_perfectgraphs_wk1_day5.pdf [EN] The Strong Perfect Graph Theorem proof: http://www.columbia.edu/~mc2775/perfect.pdf
2021/04/28 – Vizing’s Theorem [YouTube]
A proof of Vizing's theorem about graph edge coloring.
------------------ Timetable: 0:00 - Intro 0:24 - Theorem 1:02 - Lower bound 1:12 - Free colors 1:42 - Upper bound 4:11 - Outro Source code: https://github.com/xiaoxiae/videos/tree/master/03-vizing Music: ZigZag Heart by Blue Dot Sessions Software used: Manim (animations): https://github.com/ManimCommunity/manim/ Kdenlive (video): https://kdenlive.org/en/ ffmpeg (video): https://ffmpeg.org/ arecord (audio): https://linux.die.net/man/1/arecord sox (audio): http://sox.sourceforge.net/ ------------------ [CZ] Martin Koutecký's lecture on Combinatorics and Graph Theory: https://research.koutecky.name/db/teaching:kg22021_prednaska
Other
2023/07/03 – The Art of Linear Programming [YouTube]
A visual-heavy introduction to Linear Programming including basic definitions, solution via the Simplex method and the principle of duality.
More problems: https://slama.dev/youtube/linear-programming-in-python/ ------------------ Timetable: 0:00 - Introduction 0:26 - Basics 3:44 - Simplex Method 11:47 - Duality 14:01 - Integer Linear Programming 17:31 - Conclusion ------------------ Source code: https://github.com/xiaoxiae/videos/tree/master/18-lopt/ Music (in the order it appears in the video): ► Cases to Rest by Blue Dot Sessions: https://app.sessions.blue/browse/track/139762 ► Thannoid by Blue Dot Sessions: https://app.sessions.blue/browse/track/126782 ► ZigZag Heart by Blue Dot Sessions: https://app.sessions.blue/browse/track/31462 ► Maisie Dreamer by Blue Dot Sessions: https://app.sessions.blue/browse/track/31458 ► Night Light by Blue Dot Sessions: https://app.sessions.blue/browse/track/189819 Software used: ► Manim (animation software): https://github.com/ManimCommunity/manim/ ► Kdenlive (video cutting): https://kdenlive.org/en/ ► ffmpeg (audio/video processing): https://ffmpeg.org/ ► OBS (audio/video recording): https://obsproject.com/download ► arecord (audio recording): https://linux.die.net/man/1/arecord ► sox (audio processing): http://sox.sourceforge.net/ ► Inkscape (vector image editing): https://inkscape.org/ ► Midjourney (image generation): https://www.midjourney.com/app/ Social media: ► Website (for other things I'm up to): https://slama.dev/ ► Patreon (if you'd like to support me): https://www.patreon.com/TomasSlama Thanks to Matěj Kripner, Martin Balko, Lucia Zhang, Václav Rozhoň (@polylog), Kateřina Sulková, Mohit Shrestha, Teo Tuicu and Tomáš Sláma (my dad, not me) for valuable feedback. ------------------ [EN] Gerard Sierksma; Yori Zwols (2015). Linear and Integer Optimization: Theory and Practice https://www.taylorfrancis.com/books/mono/10.1201/b18378/linear-integer-optimization-gerard-sierksma-gerard-sierksma-yori-zwols [CZ] Přednáška Jiřího Sgalla: Lineární programování a kombinatorická optimalizace https://iuuk.mff.cuni.cz/~sgall/vyuka/LP/ [EN] George B. Dantzig (1982): Reminiscences about the origins of linear programming https://apps.dtic.mil/sti/pdfs/ADA112060.pdf
2023/01/20 – Thesesus and the Minotaur | Exploring State Space [YouTube]
A visual introduction to algorithms that explore the state space (BFS, Dijkstra, A*).
@polylog7346's A* video: https://youtu.be/A60q6dcoCjw Advent of Code: https://adventofcode.com/2022/ ------------------ Timetable: 0:00 - Introduction (BFS) 1:18 - Implementation 4:52 - Adding the Minotaur 8:03 - Robots! 10:18 - Pruning 10:54 - Prioritization (A*) 12:17 - Varying state distances (Dijkstra) 14:20 - Outro ------------------ Source code: https://github.com/xiaoxiae/videos/tree/master/12-state-space/ Music: ► Thannoid (Normal + Swinging) by Blue Dot Sessions: https://app.sessions.blue/browse/track/126782 ► Cases to Rest (Normal + Minimal) by Blue Dot Sessions: https://app.sessions.blue/browse/track/139762 ► Are We Loose Yet (All Piano) by Blue Dot Sessions: https://app.sessions.blue/browse/track/153364 ► Slider by Blue Dot Sessions: https://app.sessions.blue/browse/track/153362 Software used: ► Manim (animation software): https://github.com/ManimCommunity/manim/ ► Kdenlive (video cutting): https://kdenlive.org/en/ ► ffmpeg (audio/video processing): https://ffmpeg.org/ ► arecord (audio recording): https://linux.die.net/man/1/arecord ► sox (audio processing): http://sox.sourceforge.net/ ► Inkscape (vector image editing): https://inkscape.org/ ► Gimp (raster image editing): https://gimp.org/ ► Midjourney (AI image generator): https://www.midjourney.com/home/ ► Stable Diffusion (AI image generator): https://stablediffusionweb.com/ Social media: ► Website (for other things I'm up to): https://slama.dev/ ► Patreon (if you'd like to support me): https://www.patreon.com/TomasSlama Inspired by Martin Mareš's Programming 1 Course exercises. Thanks to the guys at Polylog for collaborating on this video: https://www.youtube.com/@polylog7346 Also thanks to Matěj Kripner for valuable feedback. ------------------ [EN] Wikipedia: State space search https://en.wikipedia.org/wiki/State_space_search [EN] Wikipedia: A* search algorithm https://en.wikipedia.org/wiki/A*_search_algorithm
2022/08/16 – The Remarkable BEST-SAT Algorithm [YouTube]
A dive into the remarkable BEST-SAT approximation algorithm.
Created as a part of SoME2: https://www.youtube.com/watch?v=hZuYICAEN9Y ------------------ Timetable: 0:00 - Introduction 2:21 - RAND-SAT 3:35 - LP-SAT 8:49 - BEST-SAT 10:11 - Outro ------------------ Source code: https://github.com/xiaoxiae/videos/tree/master/10-sat Music: Thannoid by Blue Dot Sessions: https://app.sessions.blue/browse/track/126782 Software used: Manim (animation software): https://github.com/ManimCommunity/manim/ Kdenlive (video cutting): https://kdenlive.org/en/ ffmpeg (audio/video processing): https://ffmpeg.org/ OBS (audio/video recording): https://obsproject.com/download arecord (audio recording): https://linux.die.net/man/1/arecord sox (audio processing): http://sox.sourceforge.net/ Vector Magic (image vectorization): https://vectormagic.com/ Inkscape (vector image editing): https://inkscape.org/ Social media: Website (for other things I'm up to): https://slama.dev/ Patreon (if you'd like to support me): https://www.patreon.com/TomasSlama Thanks to Matěj Kripner for proofreading the script and reviewing the early drafts of the video! ------------------ [EN] Notes from Jiří Sgall's Approximation Algorithms lecture https://slama.dev/lecture-notes/best-sat/
2021/12/31 – Bathroom Tile Programming [YouTube]
A dive into the unconventional bathroom tile programming model.
------------------ Other bathroom tile examples that didn't make it into the video: https://slama.dev/bathroom-tile-programming/ ------------------ Timetable: 0:00 - Introduction 1:12 - Model Definition 1:41 - Example: even input size 2:08 - Example: # of ones divisible by 3 3:22 - Time Complexity 4:19 - Example: balanced parentheses 5:54 - Computational Power 6:54 - To Infinity! 7:52 - Outro ------------------ Source code: https://github.com/xiaoxiae/videos/tree/master/09-bathroom-tiles Music: Light Stick by Blue Dot Sessions: https://app.sessions.blue/browse/track/82619 Software used: Manim (animations): https://github.com/ManimCommunity/manim/ Kdenlive (video): https://kdenlive.org/en/ ffmpeg (video): https://ffmpeg.org/ Vector Magic (images): https://vectormagic.com/ arecord (audio): https://linux.die.net/man/1/arecord sox (audio): http://sox.sourceforge.net/ Social media: Patreon (if you'd like to support me): https://www.patreon.com/TomasSlama Website (for other things I'm up to): https://slama.dev/ Special thanks to Martin Mareš, Matěj Kripner, Kateřina Sulková, Vašek Končický and Jirka Kalvoda for providing feedback! ------------------ [CZ] KSP 26 - Dlaždičky (zadání + řešení): https://ksp.mff.cuni.cz/h/ulohy/26/zadani4.html#task-26-4-8 https://ksp.mff.cuni.cz/h/ulohy/26/reseni4.html#task-26-4-8 [EN] Wikipedia - Wang Tiles: https://en.wikipedia.org/wiki/Wang_tile
Shorts
2023/07/10 – The real difference between BFS and DFS [YouTube]
What is the real difference between BFS and DFS?
------------------ Source code: https://github.com/xiaoxiae/videos/tree/master/20-dfs-vs-bfs/ Music (in the order it appears in the video): ► Thannoid by Blue Dot Sessions: https://app.sessions.blue/browse/track/126782 Software used: ► Manim (animation software): https://github.com/ManimCommunity/manim/ ► Kdenlive (video cutting): https://kdenlive.org/en/ ► ffmpeg (audio/video processing): https://ffmpeg.org/ ► OBS (audio/video recording): https://obsproject.com/download ► arecord (audio recording): https://linux.die.net/man/1/arecord ► sox (audio processing): http://sox.sourceforge.net/ ► Inkscape (vector image editing): https://inkscape.org/ ► Midjourney (image generation): https://www.midjourney.com/app/ Social media: ► Website (for other things I'm up to): https://slama.dev/ ► Patreon (if you'd like to support me): https://www.patreon.com/TomasSlama
2023/02/04 – Undirected graphs can’t equal a polynomial… or can they? [YouTube]
A glimpse into the interesting Tutte polynomial.
------------------ Source code: https://github.com/xiaoxiae/videos/tree/master/16-tutte-short/ Music: ► Cases to Rest by Blue Dot Sessions: https://app.sessions.blue/browse/track/139762 Software used: ► Manim (animation software): https://github.com/ManimCommunity/manim/ ► Kdenlive (video cutting): https://kdenlive.org/en/ ► ffmpeg (audio/video processing): https://ffmpeg.org/ ► OBS (audio/video recording): https://obsproject.com/download ► arecord (audio recording): https://linux.die.net/man/1/arecord ► sox (audio processing): http://sox.sourceforge.net/ ► Inkscape (vector image editing): https://inkscape.org/ ► Gimp (raster image editing): https://gimp.org/ ► Stable Diffusion (AI image generator): https://stablediffusionweb.com/ Social media: ► Website (for other things I'm up to): https://slama.dev/ ► Patreon (if you'd like to support me): https://www.patreon.com/TomasSlama Thanks to Honza Černý, Kateřina Sulková, Teodor Țicu, Václav Rozhoň and Matěj Kripner for valuable feedback. ------------------ [EN] Handbook of the Tutte Polynomial and Related Topics: https://www.taylorfrancis.com/books/edit/10.1201/9780429161612/handbook-tutte-polynomial-related-topics-iain-moffatt-joanna-ellis-monaghan [CZ] poznámky z přednášky Kombinatorika a Grafy II: https://slama.dev/poznamky/kombinatorika-a-grafy-ii/#tutte%C5%AFv-polynom
2022/11/16 – What does this weird C program do? [YouTube]
A very strange C program that adds numbers.
------------------ Source code: https://github.com/xiaoxiae/videos/tree/master/14-funf/ Music: Cases to Rest by Blue Dot Sessions: https://app.sessions.blue/browse/track/139762 Software used: Manim (animation software): https://github.com/ManimCommunity/manim/ Kdenlive (video cutting): https://kdenlive.org/en/ ffmpeg (audio/video processing): https://ffmpeg.org/ OBS (audio/video recording): https://obsproject.com/download arecord (audio recording): https://linux.die.net/man/1/arecord sox (audio processing): http://sox.sourceforge.net/ Vector Magic (image vectorization): https://vectormagic.com/ Inkscape (vector image editing): https://inkscape.org/ Social media: Website (for other things I'm up to): https://slama.dev/ Patreon (if you'd like to support me): https://www.patreon.com/TomasSlama Inspired by Martin Mareš's Programming 1 Course exercises.
2022/11/14 – Encoding Numbers using Dots and Parentheses [YouTube]
A really cool way of encoding numbers using dots and parentheses.
------------------ Source code: https://github.com/xiaoxiae/videos/tree/master/13-primes-dots/ Music: Cases to Rest by Blue Dot Sessions: https://app.sessions.blue/browse/track/139762 Software used: Manim (animation software): https://github.com/ManimCommunity/manim/ Kdenlive (video cutting): https://kdenlive.org/en/ ffmpeg (audio/video processing): https://ffmpeg.org/ OBS (audio/video recording): https://obsproject.com/download arecord (audio recording): https://linux.die.net/man/1/arecord sox (audio processing): http://sox.sourceforge.net/ Vector Magic (image vectorization): https://vectormagic.com/ Inkscape (vector image editing): https://inkscape.org/ Social media: Website (for other things I'm up to): https://slama.dev/ Patreon (if you'd like to support me): https://www.patreon.com/TomasSlama Inspired by Martin Mareš's Programming 1 Course exercises. Special thanks to Matěj Kripner for support and feedback.