Computers need to store real-numbered values, but how do they do it? There are multiple choices for how we could represent real-numbered values, but the floating-point representation standardized in IEEE 754 is the most common choice. Here, we explore how that representation works, the difference between single- and double-precision values, and what the tradeoffs are. *** Spanning Tree is an educational video series about computer science and mathematics. See more at https://spanningtree.me To be notified when a new video is released, sign up for the Spanning Tree mailing list at https://spanningtree.substack.com/ You can support the Spanning Tree channel at https://ko-fi.com/spanningtree Spanning Tree is created by Brian Yu. https://brianyu.me/ Email me at [email protected] to suggest a future topic.

Many of the ideas that are central to artificial intelligence have their roots in ideas developed hundreds of years ago. In this video, we explore a few key mathematicians and their ideas — Carl Friedrich Gauss searching for a missing planet, Gottfried Wilhelm Leibniz studying functions and how they change, and Augustin-Louis Cauchy trying to optimize orbital models — and understand how their work laid the foundation for the techniques we use in machine learning today, through the development of the method of least squares, the chain rule, and the gradient descent algorithm. This is Part 2 of Teaching Computers to Learn, a series on the development of artificial intelligence. See Part 1 at https://youtu.be/HzLom8rk2zo. *** Spanning Tree is an educational video series about computer science and mathematics. See more at https://spanningtree.me You can support the Spanning Tree channel at https://ko-fi.com/spanningtree To be notified when a new video is released, sign up for the Spanning Tree mailing list at https://spanningtree.substack.com/ Spanning Tree is created by Brian Yu. https://brianyu.me/ Email me at [email protected] to suggest a future topic. 0:00 A Missing Planet 1:37 Parameters 2:53 Method of Least Squares 6:04 Calculus 6:50 Chain Rule 9:51 Gradient Descent

As we continue to make new advances in artificial intelligence and machine learning, this series takes a look back at the story of how we taught computers to learn. What are the ideas that made modern AI tools possible? Where did the ideas come from? And what's the logic behind how they work? *** Spanning Tree is an educational video series about computer science and mathematics. See more at https://spanningtree.me To be notified when a new video is released, sign up for the Spanning Tree mailing list at https://spanningtree.substack.com/ You can support the Spanning Tree channel at https://ko-fi.com/spanningtree Spanning Tree is created by Brian Yu. https://brianyu.me/ Email me at [email protected] to suggest a future topic.

How can two computers share a piece of secret information without anyone else knowing? Diffie-Hellman key exchange is one of the core algorithms in cryptography for solving this problem. In this video, we build an intuition for how the algorithm works and why it's secure. *** Spanning Tree is an educational video series about computer science and mathematics. See more at https://spanningtree.me To be notified when a new video is released, sign up for the Spanning Tree mailing list at https://spanningtree.substack.com/ You can support the Spanning Tree channel at https://ko-fi.com/spanningtree Spanning Tree is created by Brian Yu. https://brianyu.me/ Email me at [email protected] to suggest a future topic.

B-trees are a popular data structure for storing large amounts of data, frequently seen in databases and file systems. But how do they really work? What makes them efficient? In this video, we explore the inner workings of the B-tree, aiming to understand the properties that make them useful and the elegant algorithms that make working with them possible. *** Spanning Tree is an educational video series about computer science and mathematics. See more at https://spanningtree.me To be notified when a new video is released, sign up for the Spanning Tree mailing list at https://spanningtree.substack.com/ You can support the Spanning Tree channel at https://ko-fi.com/spanningtree. Spanning Tree is created by Brian Yu. https://brianyu.me/ Email me at [email protected] to suggest a future topic.

For computers to be able to perform billions of operations per second, they need strategies to make calculations quickly. Carry-lookahead adders make addition much more efficient by reducing the amount of time circuits spend waiting for carries to be calculated. *** Spanning Tree is an educational video series about computer science and mathematics. See more at https://spanningtree.me To be notified when a new video is released, sign up for the Spanning Tree mailing list at https://spanningtree.substack.com/ Spanning Tree is created by Brian Yu. https://brianyu.me/ Email me at [email protected] to suggest a future topic. 0:00 Ripple Carry Adders 2:40 Carry-Lookahead 7:40 Combining CLAs

In 1997, a contest began to develop a new encryption algorithm to become the Advanced Encryption Standard. After years of debate, one algorithm was chosen as the AES. But how does AES work? And what makes for a secure encryption algorithm? *** Spanning Tree is an educational video series about computer science and mathematics. See more at https://spanningtree.me To be notified when a new video is released, sign up for the Spanning Tree mailing list at https://spanningtree.substack.com/ Spanning Tree is created by Brian Yu. https://brianyu.me/ Email me at [email protected] to suggest a future topic. *** 0:00 The Contest 1:02 Encryption 3:57 Confusion and Diffusion 5:44 Block Cipher 6:55 KeyExpansion 7:34 AddRoundKey 8:14 Substitution Cipher 8:55 SubBytes 11:30 MixColumns 12:53 ShiftRows 13:21 The Algorithm

The halting problem is an important problem in computer science that asks whether we can construct an algorithm to determine whether a computer program will run forever. It turns out that the halting problem can't be solved, and in this video, we look at the proof to understand why. *** Spanning Tree is an educational video series about computer science and mathematics. See more at https://spanningtree.me To be notified when a new video is released, sign up for the Spanning Tree mailing list at https://spanningtree.substack.com/ Spanning Tree is created by Brian Yu. https://brianyu.me/ Email me at [email protected] to suggest a future topic.

An introduction to Minimax, an algorithm that can be used to find the best move to play in an adversarial game like Tic-Tac-Toe, Chess, Go, and more. We explore how the algorithm works and some techniques we can use to make the algorithm more efficient. 0:00 Introduction 0:24 Minimax 5:12 Algorithm Pseudocode 8:42 Game Trees 10:28 Alpha-Beta Pruning 12:19 Evaluation Functions *** Spanning Tree is an educational video series covering topics related to computer science and mathematics. Sign up for the Spanning Tree mailing list to be notified when a new video is released: https://spanningtree.substack.com/ Email me at [email protected] to suggest a future topic. by Brian Yu https://brianyu.me/

An introduction to propositions, truth tables, and logical equivalence, and logical operators — including negation, conjunction, disjunction, and implication. *** Spanning Tree is a collection of educational videos covering topics related to computer science and mathematics. https://spanningtree.me/ Suggest a topic by emailing [email protected]. Sign up for the Spanning Tree mailing list to be notified whenever a new video is released. https://spanningtree.substack.com/ by Brian Yu https://brianyu.me/ 0:00 Logic 0:54 Propositions 1:35 Negation (Not) 1:59 Conjunction (And) 2:26 Disjunction (Or) 3:01 Truth Tables 4:21 Exclusive Or (Xor) 4:50 Implication 7:00 Equivalence 9:19 Biconditional 9:55 Conclusion

If you played the game perfectly, could you always win a game of Tetris? Or is there some sequence of blocks that could force you to lose the game, no matter how good at the game you are? Here, we take a look at some of the mathematics behind a theoretical game of Tetris and reason through whether it's possible to win. For the full proof described in this video, see Heidi Burgiel's "How to Lose at Tetris": https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55.8562&rep=rep1&type=pdf *** Spanning Tree is a collection of educational videos covering topics related to computer science and mathematics. https://spanningtree.me/ Sign up for the Spanning Tree mailing list to be notified whenever a new video is released. https://spanningtree.substack.com/ by Brian Yu https://brianyu.me/

In theory, a 1-kilogram computer could process no more than 1.36 × 10⁵⁰ bits per second. This is Bremermann's limit: a limit on the maximum rate at which computers can process information. But where does the limit come from? And are there computations that are still impractical, even for a computer that could reach the limit? This video is part of the MegaFavNumbers video series. *** #MegaFavNumbers *** Spanning Tree is a collection of educational videos covering topics related to computer science and mathematics. https://spanningtree.me/ Sign up for the Spanning Tree mailing list to be notified whenever a new video is released. https://spanningtree.substack.com/ by Brian Yu https://brianyu.me/ *** Earth texture: https://www.solarsystemscope.com/textures/

Dijkstra's Algorithm allows us to find the shortest path between two vertices in a graph. Here, we explore the intuition behind the algorithm — what information we need to keep track of, in what order we need to explore vertices, and what the limitations of the algorithm are. *** Spanning Tree is a collection of educational videos covering topics related to computer science and mathematics. https://spanningtree.me/ Sign up for the Spanning Tree mailing list to be notified whenever a new video is released. https://spanningtree.substack.com/ by Brian Yu https://brianyu.me/

When's the right time to launch a spacecraft from Earth to Mars? Ideally, we want to find the perfect launch window when the planets are aligned for a journey that will minimize the amount of fuel needed. In celebration of NASA's launch of Perseverance and the 8th anniversary of the landing of Curiosity, we explore some orbital mechanics, the Hohmann transfer orbit, and what it takes to get a spacecraft to Mars. *** Spanning Tree is a collection of educational videos covering topics related to computer science and mathematics. https://spanningtree.me/ Sign up for the Spanning Tree mailing list to be notified whenever a new video is released. https://spanningtree.substack.com/ by Brian Yu https://brianyu.me/ *** Images textures courtesy of https://www.solarsystemscope.com/

The Pigeonhole Principle is a simple-sounding mathematical idea, but it has a lot of various applications across a wide range of problems. Learning to recognize pigeons and pigeonholes as they appear in different problems can help in discovering possible solutions. 0:00 Pigeonhole Principle 1:39 Chessboard Puzzle 4:07 Planet Puzzle 6:12 Compression 7:47 Pigeons and Pigeonholes *** Spanning Tree is a collection of educational videos covering topics related to computer science and mathematics. https://spanningtree.me/ Sign up for the Spanning Tree mailing list to be notified whenever a new video is released. https://spanningtree.substack.com/ by Brian Yu https://brianyu.me/ *** Earth texture courtesy of https://www.solarsystemscope.com/textures/

By arranging enough dominos into just the right structure, we can build a computer. But how do we arrange dominos in such a way that they can perform computation? Here, we explore the process of building domino logical circuits by carefully arranging dominos into configurations that can compute logical functions. 0:00 A Domino Computer 0:56 OR 1:39 XOR 2:47 AND 4:30 Half Adder 6:06 Full Adder 7:20 The Circuit I first saw this concept in Matt Parker's 10,000 Domino Computer (https://www.youtube.com/watch?v=OpLU__bhu2w), which I'd absolutely recommend watching: computer simulations make for great visualizations, but building the physical domino circuit is an entirely different type of impressive. *** Spanning Tree is a collection of educational videos covering topics related to computer science and mathematics. https://spanningtree.me/ Sign up for the Spanning Tree mailing list to be notified whenever a new video is released. https://spanningtree.substack.com/ by Brian Yu https://brianyu.me/

What does it mean for something to be "random"? We might have an intuitive idea for what randomness looks like, but can we be a bit more precise about our definition for what we would consider to be random? It turns out there are multiple definitions for what's random and what isn't, but a particularly interesting idea is that of Kolmogorov randomness. Here, we take a look at Kolmogorov randomness (defined in terms of Kolmogorov complexity) to understand what the intuition behind it is and to develop a sense for what it really means for a sequence of values to be random. 0:00 Randomness 1:18 Kolmogorov Complexity 3:52 Kolmogorov Randomness *** Spanning Tree is a collection of educational videos covering topics related to computer science and mathematics. https://spanningtree.me/ Sign up for the Spanning Tree mailing list to be notified whenever a new video is released. https://spanningtree.substack.com/ by Brian Yu https://brianyu.me/

Binary heaps are very practical data structures used in a variety of algorithms — including graph searching algorithms, compression algorithms, and more. Here, we explore how binary heaps work: what they're used for, how to add new data into them, and how to remove data from them once we're done. 0:00 Priority Queues 1:31 Binary Heaps 2:99 Insertion 6:04 Deletion *** Spanning Tree is a collection of educational videos covering topics related to computer science and mathematics. Brian Yu https://brianyu.me/ https://spanningtree.me/

When two programs both need access to some shared data, how do we ensure that they don’t try to manipulate the data at the same time? This is the mutual exclusion problem, and it’s often solved with hardware. But even without any special hardware, Dekker’s Algorithm offers a way to ensure that programs can only access the shared data one at a time. Here, we take a visual look at Dekker’s Algorithm: what’s the intuition behind it? How does it work? And why does it prevent race conditions? 0:00 Mutual Exclusion 2:24 Signaling 4:05 Dekker’s Algorithm *** Spanning Tree is a collection of educational videos covering topics related to computer science and mathematics. Brian Yu https://brianyu.me/ https://spanningtree.me/

This year, I'm participating in Getting Unstuck 2020, a project run by the Harvard Graduate School of Education's Creative Computing Lab. It's 10 days of 10 Scratch projects, and it's an opportunity for creating, sharing, and learning in Scratch — a block-based visual programming language. If computer science and education is of interest to you, I'd encourage you to sign up at https://gettingunstuck.gse.harvard.edu/! Thank you to Karen, Paulina, and the rest of the Getting Unstuck team for making this event possible! This video is made by me, a participant in the program, and is not an official video from the Creative Computing Lab. *** Brian Yu

What algorithm should an elevator follow to decide which floor to visit next? What if there are multiple elevators? What should the elevators prioritize? In this video, we take a look at some of the algorithms and priorities that elevator systems might take into account. 0:00 The Elevator 2:09 Multiple Elevators 3:24 A Modern Approach Interested in reading more about the science of elevators? Check out this Popular Mechanics article, which served as one of the inspirations for this video. https://www.popularmechanics.com/technology/infrastructure/a20986/the-hidden-science-of-elevators/ *** Spanning Tree is a collection of educational videos covering topics related to computer science and mathematics. Brian Yu https://brianyu.me/ https://spanningtree.me/

Python Enhancement Protocol (PEP) 622 proposes introducing support for structural pattern matching into Python 3.10, much like other functional programming languages like Haskell and ML. It's still a draft, and Python 3.10 is still more than a year away from an official release, but there's a working implementation to try! Here, I take a look at pattern matching in action. 0:00 PEP 622 0:46 Structural Pattern Matching 2:23 Extracting Values from Patterns 5:41 Guards 6:41 Maximum 8:56 Closing

Why are bloom filters such useful data structures? How do they work, and what do they do? This video is an introduction to the bloom filter data structure: we'll explore what they are, how they work, and build an understanding for why they're so efficient.

Google's PageRank algorithm is one of the most important algorithms on the Internet. The algorithm attempts to rank pages according to their importance. But what does it mean for a web page to be "important"? In this video, we explore the "random surfer" model, which allows us to calculate a page's PageRank by simulating a random surfer who browses the web one page at a time. 0:00 PageRank 1:39 Random Surfer Model 3:40 Damping Factor *** Spanning Tree is a channel of animated educational videos covering topics in computer science and mathematics. Brian Yu https://brianyu.me/ https://spanningtree.me/

We take a look at the fundamentals of how computers work. We start with a look at logic gates, the basic building blocks of digital circuits. These gates include NOT, AND, OR, NAND, NOR, XOR, and XNOR. 0:00 Transistors 1:21 NOT 2:13 AND and OR 3:28 NAND and NOR 5:17 XOR and XNOR

How do you send a secret message if someone might be eavesdropping? How can you give someone a locked box to open without giving them the key? Here, we take a look at the three-pass protocol and man-in-the-middle attacks. 0:00 Locks and Keys 1:20 Three-Pass Protocol 3:28 Man in the Middle

What happens if a mistake happens when data is transferred? With Hamming codes, we give data the ability to correct its own mistakes. Here, we explore how that works. 0:00 Errors in Data 0:56 Parity Bits 2:14 Correcting Errors 3:38 Hamming Code

Elections might seem like they produce results people want, but that isn't always the case. This video describes the McKelvey-Schofield Chaos Theorem. To learn more, you can find the original explanation and proof of the theorem at http://www.sciencedirect.com/science/article/pii/0022053176900405/pdf?md5=a5e53112c59f6ad74f3e1557ea759db2&pid=1-s2.0-0022053176900405-main.pdf. 0:00 Transitivity 0:22 Voter Preferences 1:22 The Agenda-Setters 2:25 A Mathematical Approach 4:27 Choosing the Agenda

Dynamic programming is a common technique in computer science for solving problems more efficiently. Here, we introduce the ideas and motivations for dynamic programming by counting the number of ways to roll dice. 0:00 Counting Dice 1:21 Brute-Force Methods 2:32 Recursive Problem Solving 5:53 Lookup Tables

A story based on Kruskal's Algorithm