Spanning Tree
Spanning Tree
  • 27
  • 10 555 306
Diffie-Hellman Key Exchange: How to Share a Secret
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 spanningtree.me
To be notified when a new video is released, sign up for the Spanning Tree mailing list at spanningtree.substack.com/
You can support the Spanning Tree channel at ko-fi.com/spanningtree
Spanning Tree is created by Brian Yu. brianyu.me/
Email me at brian@spanningtree.me to suggest a future topic.
Переглядів: 116 286

Відео

Understanding B-Trees: The Data Structure Behind Modern Databases
Переглядів 279 тис.Місяць тому
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 s...
How do computers add numbers so quickly?
Переглядів 81 тис.3 місяці тому
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 spanningtree.me To be notified when a...
AES: How to Design Secure Encryption
Переглядів 146 тис.10 місяців тому
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 spanningtree.me To be notified when a new video is released,...
Understanding the Halting Problem
Переглядів 76 тис.Рік тому
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 spanningtree.me ...
Minimax: How Computers Play Games
Переглядів 196 тис.Рік тому
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 a...
An Introduction to Propositional Logic
Переглядів 89 тис.Рік тому
An introduction to propositions, truth tables, and logical equivalence, and logical operators - including negation, conjunction, disjunction, and implication. Spanning Tree is an educational video series about computer science and mathematics. See more at spanningtree.me To be notified when a new video is released, sign up for the Spanning Tree mailing list at spanningtree.substack.com/ Spannin...
Can You Always Win a Game of Tetris?
Переглядів 510 тис.3 роки тому
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...
How Fast Could a Computer Be?
Переглядів 51 тис.3 роки тому
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. #MegaFavNumber...
How Dijkstra's Algorithm Works
Переглядів 1,3 млн3 роки тому
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 an educational video series about computer science and mathematics. See more at spanningtree.me To be n...
When to Launch a Mars Mission
Переглядів 48 тис.3 роки тому
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 s...
What Is the Pigeonhole Principle?
Переглядів 3,4 млн3 роки тому
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 Computer Built With Dominos
Переглядів 838 тис.3 роки тому
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...
Randomness and Kolmogorov Complexity
Переглядів 101 тис.3 роки тому
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 randomn...
What Is a Binary Heap?
Переглядів 181 тис.3 роки тому
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 Note that the tree shapes prese...
Race Conditions and How to Prevent Them - A Look at Dekker's Algorithm
Переглядів 194 тис.3 роки тому
Race Conditions and How to Prevent Them - A Look at Dekker's Algorithm
Getting Unstuck 2020 - 10 days of Scratch projects!
Переглядів 4,5 тис.3 роки тому
Getting Unstuck 2020 - 10 days of Scratch projects!
The Science Behind Elevators
Переглядів 328 тис.3 роки тому
The Science Behind Elevators
Pattern Matching in Python?
Переглядів 18 тис.4 роки тому
Pattern Matching in Python?
What Are Bloom Filters?
Переглядів 118 тис.4 роки тому
What Are Bloom Filters?
How Google's PageRank Algorithm Works
Переглядів 116 тис.4 роки тому
How Google's PageRank Algorithm Works
Understanding Logic Gates
Переглядів 605 тис.4 роки тому
Understanding Logic Gates
How to Send a Secret Message
Переглядів 463 тис.4 роки тому
How to Send a Secret Message
Hamming Codes - How Data Corrects Itself
Переглядів 57 тис.4 роки тому
Hamming Codes - How Data Corrects Itself
The Mathematical Danger of Democratic Voting
Переглядів 1 млн4 роки тому
The Mathematical Danger of Democratic Voting
How to Count Dice Rolls - An Introduction to Dynamic Programming
Переглядів 155 тис.4 роки тому
How to Count Dice Rolls - An Introduction to Dynamic Programming
How Do You Calculate a Minimum Spanning Tree?
Переглядів 50 тис.4 роки тому
How Do You Calculate a Minimum Spanning Tree?

КОМЕНТАРІ

  • @userou-ig1ze
    @userou-ig1ze 11 годин тому

    It might be more interesting to do this in the real world without mod functions, as in actually exchange a physical key

  • @leongthomas4173
    @leongthomas4173 13 годин тому

    He sounds like Brian from cs50x

  • @dieselhead999
    @dieselhead999 13 годин тому

    You are cooked.

  • @sirifail4499
    @sirifail4499 23 години тому

    My first Electrical Engineering job out of college was at a large company with a three initial name. We had an annual “confidential” Employee Satisfaction Survey. They’d find the thing “people wanted changed most” and make it a priority. It’s easiest to describe the failure of this pathetic attempt at pandering with a real example. Real Question: What would you most like to see? A. A raise B. More parking C. More vacation Somewhere around half picked A and half picked C. Not a single person at the facility chose B. But 50/50 A/C somehow, kinda maybe, averages to B. So they expanded the parking lot. Oh, and your manager was likely to discuss your answers to the “confidential” survey with you.

  • @EatTheRichAndTheState
    @EatTheRichAndTheState День тому

    The power of concensus, good old anarchy ♡

  • @kazikmajster5650
    @kazikmajster5650 День тому

    I don't like this. Just add nodes by layers.

  • @raiyan22
    @raiyan22 День тому

    sooo cool!!!

  • @Drraghavsethi
    @Drraghavsethi День тому

    every other video explaining B trees must be deleted to save space and time. This is perfect explanation.

  • @skejeton
    @skejeton День тому

    Dont forget that even though halting problem in *general* is not solvable, this contradiction only applies to this particular case. Other practical cases may be solvable.

  • @richardwilliamsmusic
    @richardwilliamsmusic День тому

    Phenomenal teaching! please do more computer programming related concepts, love this!

  • @mohammadrezadev
    @mohammadrezadev День тому

    Really useful

  • @downloadableram2666
    @downloadableram2666 2 дні тому

    en passant spotted

  • @joshuaworman4022
    @joshuaworman4022 2 дні тому

    amazing video. wish we could have this for litterally everything.

  • @HuzaifaKhan-iy5qj
    @HuzaifaKhan-iy5qj 2 дні тому

    I didn't even completed minute of the video yet, i've subscribed the channel.

  • @ArcherNX1701
    @ArcherNX1701 2 дні тому

    Thanks for making the explanation so simple. Would you make another vid that explians how quantum computing can break this? And any solution post-quantum?

  • @timleferink
    @timleferink 3 дні тому

    Nice video. Think you can greatly improve audio with some sound deadening 😁

  • @0Yorek0
    @0Yorek0 3 дні тому

    PLs make more simple algorithms

  • @brianarsuaga5008
    @brianarsuaga5008 4 дні тому

    Huh, I knew and studied this, technically, but this made it less "black magic" where the math was concerned. Thanks!

  • @MENSA.lady2
    @MENSA.lady2 4 дні тому

    If it's a Secret why would you want to share it. if you do it is no longer a secret.

  • @tanisharao0704
    @tanisharao0704 4 дні тому

    I loved it ❤

  • @rani-4351
    @rani-4351 4 дні тому

    berkat Pak Pri saya menonton video ini, terimakasih Pak Pri :)

  • @floppy8568
    @floppy8568 4 дні тому

    Convole!

  • @ASE_Ridern123
    @ASE_Ridern123 4 дні тому

    THE SEQUEL OF HOW TO SEND A SECRET MESSAGE

  • @crw662
    @crw662 5 днів тому

    Do you really think our politicians are smart enough to pull this off? Is there any actual evidence of “agenda setters” using this strategy?

  • @maquih
    @maquih 6 днів тому

    i wonder how this might map to physical storage. a large warehouse might take a few minutes to grab an item, but checking if it's the one you want might only take a few seconds.

  • @antonkal
    @antonkal 6 днів тому

    Thanks Brian, watching this video because I'm solving a puzzle to implement xor using only and and not gates..

  • @adituta8660
    @adituta8660 6 днів тому

    If you want to delete an element from the bloom filter, you have to remake the filter

  • @sarthak-salunke
    @sarthak-salunke 6 днів тому

    ❤❤

  • @sobevj
    @sobevj 7 днів тому

    It's very concise and you learn a lot in a short time, and if you want to learn the source code, it'll be easier!

  • @AhmedBelal-zc7hw
    @AhmedBelal-zc7hw 7 днів тому

    great!!♥

  • @gabirican4813
    @gabirican4813 7 днів тому

    Thanks!

  • @ismyname_jep1394
    @ismyname_jep1394 7 днів тому

    Wait why does his voice sound recognizably similar to that guy on CS50.

  • @pummimintu
    @pummimintu 8 днів тому

    STOP THE MUSIC!!!!!!!!!!!!!

  • @victoriamatrone2564
    @victoriamatrone2564 8 днів тому

    how can be 1+1=1🫠?

  • @wutdahack285
    @wutdahack285 9 днів тому

    Great video <3

  • @jameslovering9158
    @jameslovering9158 10 днів тому

    Thank you, that was easy to follow !

  • @cxa24
    @cxa24 10 днів тому

    I escaped the secret (why you should run away)

  • @abaniahmadbani
    @abaniahmadbani 10 днів тому

    College ❌️ UA-cam ✅️

  • @labCmais135
    @labCmais135 11 днів тому

    Why is C still tagged as 3? Isn’t A F C = 4?

  • @DearB_
    @DearB_ 11 днів тому

    I have studied this in my class but that wasn't clear but now l understood . Thank you ♥️

  • @baranxlr
    @baranxlr 11 днів тому

    Weird thing is, if you restrict the program size, like "for a program with less than 500 characters, decide if it halts" then the problem IS solvable, at least on paper: You just make a lookup table for every possible program and the answer Yes/No. The unsolvability is because we're trying to make a program that solves halting for any sized program.

  • @cdvgter
    @cdvgter 12 днів тому

    This is explained so well!

  • @ShongachanAsare
    @ShongachanAsare 12 днів тому

    What is this 😢

  • @dragonlordsaviour7005
    @dragonlordsaviour7005 12 днів тому

    absolutely beautiful explanation

  • @ahmadmahagna1255
    @ahmadmahagna1255 12 днів тому

    respect

  • @sai2849
    @sai2849 13 днів тому

    To understand this theorem, you need to push Dijkstra aside. Gently.

  • @malekabdoh8639
    @malekabdoh8639 13 днів тому

    Could it work if a condition is you can’t use the output to decide if something is going to loop

  • @VVayVVard
    @VVayVVard 13 днів тому

    I watched some other videos first but ended up feeling confused since none of them explained the point of the various steps of the algorithm. Now everything makes more sense.

  • @nishantsethi6625
    @nishantsethi6625 14 днів тому

    ua-cam.com/users/shortsV8QD98eONCw?si=oPkUsUPHVdfzDKaG This is way too helpful

  • @nishantsethi6625
    @nishantsethi6625 14 днів тому

    Fake comments. Nt at all helpful