Spanning Tree
Spanning Tree
  • Видео 27
  • Просмотров 10 614 154
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.
Просмотров: 126 900

Видео

Understanding B-Trees: The Data Structure Behind Modern Databases
Просмотров 294 тыс.2 месяца назад
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?
Просмотров 82 тыс.4 месяца назад
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
Просмотров 149 тыс.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
Просмотров 77 тыс.Год назад
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
Просмотров 197 тыс.Год назад
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
Просмотров 90 тыс.Год назад
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,4 млн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
Просмотров 839 тыс.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?
Просмотров 182 тыс.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
Просмотров 195 тыс.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 тыс.4 года назад
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
Просмотров 117 тыс.4 года назад
How Google's PageRank Algorithm Works
Understanding Logic Gates
Просмотров 611 тыс.4 года назад
Understanding Logic Gates
How to Send a Secret Message
Просмотров 464 тыс.4 года назад
How to Send a Secret Message
Hamming Codes - How Data Corrects Itself
Просмотров 58 тыс.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
Просмотров 156 тыс.4 года назад
How to Count Dice Rolls - An Introduction to Dynamic Programming
How Do You Calculate a Minimum Spanning Tree?
Просмотров 51 тыс.4 года назад
How Do You Calculate a Minimum Spanning Tree?

Комментарии

  • @iustincobuz561
    @iustincobuz561 2 часа назад

    This is literally what I exactly needed. Concise, super clear, clean explanations and illustrations. Just a big congratulations and Thank you for building this video

  • @timothywong6057
    @timothywong6057 14 часов назад

    Step 1. Continue as usual till the messenger comes back the second time. Step 2. Ignore it. This will make the messenger think the Man in the Middle attack opening the lock. But your lock is still here. Step 3. Let the neighbor add in his lock. Step 4.When the messenger adds another lock and comes back, call your neighbour to tell that the messenger is tricking you into opening it. Step 5. Repeat Step 1 and 2 but when the messenger opens it's lock, the neighbor's lock is still there. Step 6. The messenger will go to your neighbor, and then the neighbor will open the lock and read the secret message.

  • @Katniss218
    @Katniss218 22 часа назад

    doesn't "giving opposite program itself as input" produce infinite recursion or something?

  • @ashb2483
    @ashb2483 День назад

    Great vid!

  • @md.hossain693
    @md.hossain693 День назад

    ❤❤❤❤❤

  • @willabyuberton818
    @willabyuberton818 День назад

    Really nice video! I could watch animations of values getting inserted and deleted on binary trees all day.

  • @samueltaylor4989
    @samueltaylor4989 2 дня назад

    The earth hemisphere problem as you state it is wrong. You said pick 5 points at random. If it’s random, the points could end up in the same continent or even the same square mile. They would all end up in the same hemisphere. Like rolling dice at random, each number is as likely as any other even the same number coming up 100x in a row.

  • @Supernumerary
    @Supernumerary 2 дня назад

    Early in your development you must study machine code, assembly language, if you want to assess the actual processor cost of architecture choices, such as designing search trees. This is an excellent presentation, but in reality there are many essential layers below what is discussed here.

  • @hoangphamduc3928
    @hoangphamduc3928 2 дня назад

    We learned 2 concepts in this video. Thank you so much. I am a software engineer who did not graduated from CS. Your videos are great!

  • @totalme302
    @totalme302 2 дня назад

    What about a program that will tell whether Halt can do work properly or not.

  • @anthonycorado9515
    @anthonycorado9515 2 дня назад

    Thank you for an amazing explanation regarding logic gates.

  • @lehlogonolonare
    @lehlogonolonare 3 дня назад

    Ahhh probability this one

  • @quemaspana
    @quemaspana 3 дня назад

    This is a really great explanation.

  • @Nightowl_IT
    @Nightowl_IT 4 дня назад

    I think the reason for the binary tree is the structure of CPUs.

  • @KA3I772
    @KA3I772 4 дня назад

    i came here because of scrap mechanic

  • @user-xf2xk4lg8i
    @user-xf2xk4lg8i 4 дня назад

    U are a legend! Keep doing good work

  • @darylbeaumont8855
    @darylbeaumont8855 4 дня назад

    Greaty video! Presented well and easy to understand. :)

  • @trevoro.9731
    @trevoro.9731 5 дней назад

    Searching goes into some problematic "feature" of modern processors - the branch misprediction penalty, most of the processors do not have optimizations to reduce that to acceptable minimum. The penalty become a huge limitation when your purpose is to achieve millions of operations per seconds.

  • @jbond5834
    @jbond5834 5 дней назад

    looks like cell split

  • @mrmurpleqwerty4838
    @mrmurpleqwerty4838 5 дней назад

    actually, the "walk" program will stop eventually given -1 as input, due to integer overflow.

  • @mykydragon9265
    @mykydragon9265 5 дней назад

    This videos is soooo good.

  • @yana_k6424
    @yana_k6424 5 дней назад

    Cool video! What do you use to make the animations by the way? They remind me of three.js renders

  • @Seagaltalk
    @Seagaltalk 7 дней назад

    Also how to share wives

  • @tinsaedaniel8773
    @tinsaedaniel8773 7 дней назад

    Nah why am I still confused? The program that we assumed will tell whether a program halts or not is doing is job. And so is the opposite program. Both are doing their jobs correctly. I only see a contradiction in the wording, not the actual job. In other words, let's say the program, instead of doing the opposite, does exactly what the halting program does. There is no contradiction there, is there?

  • @ethnblze
    @ethnblze 7 дней назад

    The chances in getting such a pattern would be 1/7^69,600

  • @tomcruise3003
    @tomcruise3003 7 дней назад

    All of this just to say good morning!? I'd go back to bed at that point

  • @TheMorais69
    @TheMorais69 7 дней назад

    very nice video, love it ♥

  • @jasonandrewismail2029
    @jasonandrewismail2029 8 дней назад

    Excellenct video

  • @Mahm00dM0hanad
    @Mahm00dM0hanad 8 дней назад

    Well explained, thanks a lot

  • @TNewton001
    @TNewton001 8 дней назад

    Thanks!

  • @userou-ig1ze
    @userou-ig1ze 9 дней назад

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

  • @leongthomas4173
    @leongthomas4173 9 дней назад

    He sounds like Brian from cs50x

  • @dieselhead999
    @dieselhead999 9 дней назад

    You are cooked.

  • @sirifail4499
    @sirifail4499 10 дней назад

    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 10 дней назад

    The power of concensus, good old anarchy ♡

  • @kazikmajster5650
    @kazikmajster5650 10 дней назад

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

  • @raiyan22
    @raiyan22 10 дней назад

    sooo cool!!!

  • @Drraghavsethi
    @Drraghavsethi 10 дней назад

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

  • @skejeton
    @skejeton 10 дней назад

    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 10 дней назад

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

  • @mohammadrezadev
    @mohammadrezadev 10 дней назад

    Really useful

  • @downloadableram2666
    @downloadableram2666 11 дней назад

    en passant spotted

  • @joshuaworman4022
    @joshuaworman4022 11 дней назад

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

  • @HuzaifaKhan-iy5qj
    @HuzaifaKhan-iy5qj 12 дней назад

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

  • @ArcherNX1701
    @ArcherNX1701 12 дней назад

    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 12 дней назад

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

  • @0Yorek0
    @0Yorek0 13 дней назад

    PLs make more simple algorithms

  • @brianarsuaga5008
    @brianarsuaga5008 13 дней назад

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

  • @MENSA.lady2
    @MENSA.lady2 13 дней назад

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

  • @tanisharao0704
    @tanisharao0704 13 дней назад

    I loved it ❤