The Art of Linear Programming Tom S 2023-07-04 | A visual-heavy introduction to Linear Programming including basic definitions, solution via the Simplex method, the principle of duality and Integer Linear Programming. #some3More problems: https://slama.dev/youtube/linear-programming-in-python/Made as my entry to SoME3: 3blue1brown.substack.com/p/some3-begins------------------Timetable:0:00 - Introduction0:26 - Basics3:44 - Simplex Method11:47 - Duality14:01 - Integer Linear Programming17:31 - Conclusion------------------Source code: github.com/xiaoxiae/videos/tree/master/18-loptMusic (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/189819Software used:► Manim (animation software): github.com/ManimCommunity/manim► Kdenlive (video cutting): kdenlive.org/en► ffmpeg (audio/video processing): ffmpeg.org► OBS (audio/video recording): obsproject.com/download► arecord (audio recording): linux.die.net/man/1/arecord► sox (audio processing): http://sox.sourceforge.net► Inkscape (vector image editing): inkscape.org► Midjourney (image generation): midjourney.com/appSocial media:► Website (for other things I'm up to): https://slama.dev/► Patreon (if you'd like to support me): patreon.com/YTomSThanks 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 Practicetaylorfrancis.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á optimalizacehttps://iuuk.mff.cuni.cz/~sgall/vyuka/LP/[EN] George B. Dantzig (1982): Reminiscences about the origins of linear programminghttps://apps.dtic.mil/sti/pdfs/ADA112060.pdf
The real difference between BFS and DFS Tom S 2023-07-10 | #shortsWhat is the real difference between BFS and DFS?------------------Source code: github.com/xiaoxiae/videos/tree/master/20-dfs-vs-bfsMusic (in the order it appears in the video):► Thannoid by Blue Dot Sessions: https://app.sessions.blue/browse/track/126782Software used:► Manim (animation software): github.com/ManimCommunity/manim► Kdenlive (video cutting): kdenlive.org/en► ffmpeg (audio/video processing): ffmpeg.org► OBS (audio/video recording): obsproject.com/download► arecord (audio recording): linux.die.net/man/1/arecord► sox (audio processing): http://sox.sourceforge.net► Inkscape (vector image editing): inkscape.org► Midjourney (image generation): midjourney.com/appSocial media:► Website (for other things I'm up to): https://slama.dev/► Patreon (if you'd like to support me): patreon.com/YTomS
The Most Elegant Search Structure | (a,b)-trees Tom S 2023-04-09 | An introduction to (a,b)-trees – definition, operations, usage.------------------Timetable:0:00 - Fever dream?0:28 - Introduction2:04 - Basics3:47 - Search4:33 - Insertion6:06 - Deletion8:51 - Selecting (a, b)10:36 - Usage11:22 - Outro------------------Source code: github.com/xiaoxiae/videos/tree/master/17-abMusic (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/126782Software used:► Manim (animation software): github.com/ManimCommunity/manim► Kdenlive (video cutting): kdenlive.org/en► ffmpeg (audio/video processing): ffmpeg.org► OBS (audio/video recording): obsproject.com/download► arecord (audio recording): linux.die.net/man/1/arecord► sox (audio processing): http://sox.sourceforge.net► Inkscape (vector image editing): inkscape.org► Stable Diffusion (image generation): stablediffusionweb.comSocial media:► Website (for other things I'm up to): https://slama.dev/► Patreon (if you'd like to support me): patreon.com/YTomSThanks to Matěj Kripner, František Voldřich, Jakub Pelc, Hansen Pascal, Patrick Elsen 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:github.com/frozenca/BTree[EN] Other (a,b)-tree-related resources:en.wikipedia.org/wiki/(a,b)-treeen.wikipedia.org/wiki/B%2B_treeen.wikipedia.org/wiki/B-tree
Undirected graphs cant equal a polynomial... or can they? Tom S 2023-02-05 | #shortsA glimpse into the interesting Tutte polynomial.------------------Source code: github.com/xiaoxiae/videos/tree/master/16-tutte-shortMusic:► Cases to Rest by Blue Dot Sessions: https://app.sessions.blue/browse/track/139762Software used:► Manim (animation software): github.com/ManimCommunity/manim► Kdenlive (video cutting): kdenlive.org/en► ffmpeg (audio/video processing): ffmpeg.org► OBS (audio/video recording): obsproject.com/download► arecord (audio recording): linux.die.net/man/1/arecord► sox (audio processing): http://sox.sourceforge.net► Inkscape (vector image editing): inkscape.org► Gimp (raster image editing): gimp.org► Stable Diffusion (AI image generator): stablediffusionweb.comSocial media:► Website (for other things I'm up to): https://slama.dev/► Patreon (if you'd like to support me): patreon.com/YTomSThanks to Honza Černý, Kateřina Sulková, Teodor Țicu, Václav Rozhoň, Tadeáš Semela and Matěj Kripner for valuable feedback.------------------[EN] Handbook of the Tutte Polynomial and Related Topics: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
Theseus and the Minotaur | Exploring State Space Tom S 2023-01-20 | A visual introduction to algorithms that explore the state space (BFS, Dijkstra, A*).@polylog7346's A* video: youtu.be/A60q6dcoCjwAdvent of Code: adventofcode.com/2022------------------Timetable:0:00 - Introduction (BFS)1:18 - Implementation4:52 - Adding the Minotaur8:03 - Robots!10:18 - Pruning10:54 - Prioritization (A*)12:17 - Varying state distances (Dijkstra)14:20 - Outro------------------Source code: github.com/xiaoxiae/videos/tree/master/12-state-spaceMusic:► 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/153362Software used:► Manim (animation software): github.com/ManimCommunity/manim► Kdenlive (video cutting): kdenlive.org/en► ffmpeg (audio/video processing): ffmpeg.org► arecord (audio recording): linux.die.net/man/1/arecord► sox (audio processing): http://sox.sourceforge.net► Inkscape (vector image editing): inkscape.org► Gimp (raster image editing): gimp.org► Midjourney (AI image generator): midjourney.com/home► Stable Diffusion (AI image generator): stablediffusionweb.comSocial media:► Website (for other things I'm up to): https://slama.dev/► Patreon (if you'd like to support me): patreon.com/YTomSInspired by Martin Mareš's Programming 1 Course exercises.Thanks to the guys at Polylog for collaborating on this video: youtube.com/@polylog7346Also thanks to Matěj Kripner for valuable feedback.------------------[EN] Wikipedia: State space searchen.wikipedia.org/wiki/State_space_search[EN] Wikipedia: A* search algorithmen.wikipedia.org/wiki/A*_search_algorithm
What does this weird C program do? Tom S 2022-11-16 | #shortsA very strange C program that adds numbers.------------------Source code:github.com/xiaoxiae/videos/tree/master/14-funfMusic:Cases to Rest by Blue Dot Sessions: https://app.sessions.blue/browse/track/139762Software used:Manim (animation software): github.com/ManimCommunity/manimKdenlive (video cutting): kdenlive.org/enffmpeg (audio/video processing): ffmpeg.orgOBS (audio/video recording): obsproject.com/downloadarecord (audio recording): linux.die.net/man/1/arecordsox (audio processing): http://sox.sourceforge.netVector Magic (image vectorization): vectormagic.comInkscape (vector image editing): inkscape.orgSocial media:Website (for other things I'm up to): https://slama.dev/► Patreon (if you'd like to support me): patreon.com/YTomSInspired by Martin Mareš's Programming 1 Course exercises.
Encoding Numbers using Dots and Parentheses Tom S 2022-11-14 | #shortsA really cool way of encoding numbers using dots and parentheses.------------------Source code:github.com/xiaoxiae/videos/tree/master/13-primes-dotsMusic:Cases to Rest by Blue Dot Sessions: https://app.sessions.blue/browse/track/139762Software used:Manim (animation software): github.com/ManimCommunity/manimKdenlive (video cutting): kdenlive.org/enffmpeg (audio/video processing): ffmpeg.orgOBS (audio/video recording): obsproject.com/downloadarecord (audio recording): linux.die.net/man/1/arecordsox (audio processing): http://sox.sourceforge.netVector Magic (image vectorization): vectormagic.comInkscape (vector image editing): inkscape.orgSocial media:Website (for other things I'm up to): https://slama.dev/► Patreon (if you'd like to support me): patreon.com/YTomSInspired by Martin Mareš's Programming 1 Course exercises.Special thanks to Matěj Kripner for support and feedback.
The Remarkable BEST-SAT Algorithm Tom S 2022-08-16 | A dive into the remarkable BEST-SAT approximation algorithm.Created as a part of SoME2: youtube.com/watch?v=hZuYICAEN9Y------------------Timetable:0:00 - Introduction2:21 - RAND-SAT3:35 - LP-SAT8:49 - BEST-SAT10:11 - Outro------------------Source code:github.com/xiaoxiae/videos/tree/master/10-satMusic:Thannoid by Blue Dot Sessions: https://app.sessions.blue/browse/track/126782Software used:Manim (animation software): github.com/ManimCommunity/manimKdenlive (video cutting): kdenlive.org/enffmpeg (audio/video processing): ffmpeg.orgOBS (audio/video recording): obsproject.com/downloadarecord (audio recording): linux.die.net/man/1/arecordsox (audio processing): http://sox.sourceforge.netVector Magic (image vectorization): vectormagic.comInkscape (vector image editing): inkscape.orgSocial media:Website (for other things I'm up to): https://slama.dev/► Patreon (if you'd like to support me): patreon.com/YTomSThanks to Matěj Kripner for proofreading the script and reviewing the early drafts of the video!------------------[EN] Notes from Jiří Sgall's Approximation Algorithms lecturehttps://slama.dev/lecture-notes/best-sat/
Bathroom Tile Programming Tom S 2021-12-31 | A dive into the unconventional bathroom tile programming model.------------------Other bathroom tile examples that didn't make it into the video:https://slama.dev/youtube/bathroom-tile-programming/------------------Timetable:0:00 - Introduction1:12 - Model Definition1:41 - Example: even input size2:08 - Example: # of ones divisible by 33:22 - Time Complexity4:19 - Example: balanced parentheses5:54 - Computational Power6:54 - To Infinity!7:52 - Outro------------------Source code:github.com/xiaoxiae/videos/tree/master/09-bathroom-tilesMusic:Light Stick by Blue Dot Sessions: https://app.sessions.blue/browse/track/82619Software used:Manim (animations): github.com/ManimCommunity/manimKdenlive (video): kdenlive.org/enffmpeg (video): ffmpeg.orgVector Magic (images): vectormagic.comarecord (audio): linux.die.net/man/1/arecordsox (audio): http://sox.sourceforge.netSocial media:Website (for other things I'm up to): https://slama.dev/Patreon (if you'd like to support me): patreon.com/YTomSSpecial 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-8https://ksp.mff.cuni.cz/h/ulohy/26/reseni4.html#task-26-4-8[EN] Wikipedia - Wang Tiles:en.wikipedia.org/wiki/Wang_tile
Cayleys Formula Tom S 2021-10-06 | A short video about an elegant proof of the number of spanning trees of a complete graph.------------------Timetable:0:00 - Introduction0:13 - Definitions0:34 - Statement1:03 - Proof3:37 - Outro------------------Source code:github.com/xiaoxiae/videos/tree/master/07-cayleyMusic:- Maisie Dreamer by Blue Dot Sessions: https://app.sessions.blue/browse/track/31458Software used:Manim (animations): github.com/ManimCommunity/manimKdenlive (video): kdenlive.org/enffmpeg (video): ffmpeg.orgVector Magic (images): vectormagic.comarecord (audio): linux.die.net/man/1/arecordsox (audio): http://sox.sourceforge.netSocial media:Website (for other things I'm up to): https://slama.dev/Patreon (if you'd like to support me): patreon.com/YTomS------------------[CZ] My notes on Martin Koutecký's Combinatorics and Graphs 1 lecture:https://slama.dev/lecture-notes/kombinatorika-a-grafy-i/
The Blossom Algorithm Tom S 2021-08-23 | An overview of the Blossom algorithm for maximum graph matching.------------------Timetable:0:00 - Introduction0:41 - Definitions1:02 - Augmenting paths1:42 - Maximum tree matching3:06 - Blossoms4:06 - Maximum general graph matching4:59 - Overview5:46 - Outro------------------Source code:github.com/xiaoxiae/videos/tree/master/06-edmonds-blossomMusic:Maisie Dreamer by Blue Dot Sessions: https://app.sessions.blue/browse/track/31458Software used:Manim (animations): github.com/ManimCommunity/manimKdenlive (video): kdenlive.org/enffmpeg (video): ffmpeg.orgVector Magic (images): vectormagic.comarecord (audio): linux.die.net/man/1/arecordsox (audio): http://sox.sourceforge.netSocial media:Website (for other things I'm up to): https://slama.dev/Patreon (if you'd like to support me): patreon.com/YTomS------------------[EN] Proofs: https://web.stanford.edu/~rezab/classes/cme323/S16/projects_reports/shoemaker_vare.pdf- graph has an a.p. if and only if the matching is not maximum: theorem 2.4- graph has an a.p. if and only if compressed graph has an a.p.: theorem 2.9[CZ] My notes on Martin Koutecký's Combinatorics and Graphs lecture:https://slama.dev/lecture-notes/kombinatorika-a-grafy-ii/[EN] Sketchy Notes on Edmonds’ Incredible Shrinking Blossomhttp://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:en.wikipedia.org/wiki/Blossom_algorithm
Weak Perfect Graph Theorem Tom S 2021-06-01 | A proof of the weak perfect graph theorem.------------------Timetable:0:00 - Introduction0:34 - Graph complement0:49 - Clique and independent set1:32 - Induced subgraph1:53 - Chromatic number2:08 - Perfect graph2:24 - Observations3:29 - Lemma 14:55 - Lemma 26:31 - Weak perfect graph theorem9:41 - Strong perfect graph theorem10:23 - Outro------------------Source code:github.com/xiaoxiae/videos/tree/master/04-perfect-graphsMusic:Maisie Dreamer by Blue Dot Sessions: https://app.sessions.blue/browse/track/31458Software used:Manim (animations): github.com/ManimCommunity/manimKdenlive (video): kdenlive.org/enffmpeg (video): ffmpeg.orgarecord (audio): linux.die.net/man/1/arecordsox (audio): http://sox.sourceforge.netSocial media:Website (for other things I'm up to): https://slama.dev/Patreon (if you'd like to support me): patreon.com/YTomSSpecial 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.pdfhttp://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
Vizings Theorem Tom S 2021-04-28 | A proof of Vizing's theorem about graph edge coloring.------------------Timetable:0:00 - Intro0:24 - Theorem1:02 - Lower bound1:12 - Free colors1:42 - Upper bound4:11 - Outro------------------Source code:github.com/xiaoxiae/videos/tree/master/03-vizingMusic:ZigZag Heart by Blue Dot Sessions: https://app.sessions.blue/browse/track/31462Software used:Manim (animations): github.com/ManimCommunity/manimKdenlive (video): kdenlive.org/enffmpeg (video): ffmpeg.orgarecord (audio): linux.die.net/man/1/arecordsox (audio): http://sox.sourceforge.netSocial media:Website (for other things I'm up to): https://slama.dev/Patreon (if you'd like to support me): patreon.com/YTomS------------------[CZ] Martin Koutecký's lecture on Combinatorics and Graph Theory:https://research.koutecky.name/db/teaching:kg22021_prednaska
