Spanning Tree
Spanning Tree
  • 27
  • 10 485 150
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.
zhlédnutí: 96 597

Video

Understanding B-Trees: The Data Structure Behind Modern Databases
zhlédnutí 262KPřed měsícem
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?
zhlédnutí 81KPřed 3 měsíci
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
zhlédnutí 142KPřed 9 měsíci
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
zhlédnutí 75KPřed rokem
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
zhlédnutí 194KPřed rokem
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
zhlédnutí 89KPřed rokem
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?
zhlédnutí 509KPřed 3 lety
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?
zhlédnutí 51KPřed 3 lety
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
zhlédnutí 1,3MPřed 3 lety
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
zhlédnutí 47KPřed 3 lety
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?
zhlédnutí 3,4MPřed 3 lety
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
zhlédnutí 838KPřed 3 lety
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
zhlédnutí 101KPřed 3 lety
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?
zhlédnutí 179KPřed 3 lety
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
zhlédnutí 193KPřed 3 lety
Race Conditions and How to Prevent Them - A Look at Dekker's Algorithm
Getting Unstuck 2020 - 10 days of Scratch projects!
zhlédnutí 4,4KPřed 3 lety
Getting Unstuck 2020 - 10 days of Scratch projects!
The Science Behind Elevators
zhlédnutí 328KPřed 3 lety
The Science Behind Elevators
Pattern Matching in Python?
zhlédnutí 18KPřed 3 lety
Pattern Matching in Python?
What Are Bloom Filters?
zhlédnutí 117KPřed 3 lety
What Are Bloom Filters?
How Google's PageRank Algorithm Works
zhlédnutí 115KPřed 3 lety
How Google's PageRank Algorithm Works
Understanding Logic Gates
zhlédnutí 597KPřed 3 lety
Understanding Logic Gates
How to Send a Secret Message
zhlédnutí 463KPřed 4 lety
How to Send a Secret Message
Hamming Codes - How Data Corrects Itself
zhlédnutí 57KPřed 4 lety
Hamming Codes - How Data Corrects Itself
The Mathematical Danger of Democratic Voting
zhlédnutí 1MPřed 4 lety
The Mathematical Danger of Democratic Voting
How to Count Dice Rolls - An Introduction to Dynamic Programming
zhlédnutí 155KPřed 4 lety
How to Count Dice Rolls - An Introduction to Dynamic Programming
How Do You Calculate a Minimum Spanning Tree?
zhlédnutí 49KPřed 4 lety
How Do You Calculate a Minimum Spanning Tree?

Komentáře

  • @ahmadmahagna1255
    @ahmadmahagna1255 Před 2 hodinami

    respect

  • @sai2849
    @sai2849 Před 11 hodinami

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

  • @malekabdoh8639
    @malekabdoh8639 Před 13 hodinami

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

  • @VVayVVard
    @VVayVVard Před dnem

    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 Před dnem

    czcams.com/users/shortsV8QD98eONCw?si=oPkUsUPHVdfzDKaG This is way too helpful

  • @nishantsethi6625
    @nishantsethi6625 Před dnem

    Fake comments. Nt at all helpful

  • @yashmehta9299
    @yashmehta9299 Před dnem

    * for a digital classical computer

  • @aliframdani_
    @aliframdani_ Před dnem

    really easy to understand. You guys are great, thank you

  • @toshevislombek
    @toshevislombek Před dnem

    5:55 I create new bloom filter for deleted items, and I look for deleted BF if it is negative, I assume item is not deleted yet

  • @mercurialpoirot5551

    You are not analysing democratic voting. A democratic voting system would require a veto option on the ballot. If a majority choose to veto, the election is re-run. In a pr system % veto = % empty seats. What you are analysing is an elected oligarchic system. Where we choose rulers, not representatives.

  • @Anythiny
    @Anythiny Před 2 dny

    its always fun to watch ur explaination

  • @shalinluitel1332
    @shalinluitel1332 Před 2 dny

    Great Video!!!

  • @NicolasMiari
    @NicolasMiari Před 2 dny

    Subscribing because the robots are cute 😂

  • @oelwechsel
    @oelwechsel Před 3 dny

    why no a Star? :(

  • @harsh9558
    @harsh9558 Před 3 dny

    Very interesting

  • @halladba101
    @halladba101 Před 3 dny

    Hey I love Scratch :D

  • @powerHungryMOSFET
    @powerHungryMOSFET Před 3 dny

    What about watchdog timer?

  • @pjn2001
    @pjn2001 Před 3 dny

    Might be a bit simplistic but would like to request a video on hole punching (networking). Maybe if combined with some other networking concept it could be a bit more viable. Thank you

  • @YoutubSosetXui
    @YoutubSosetXui Před 4 dny

    Boring

  • @nigorazakirova4230
    @nigorazakirova4230 Před 4 dny

    Simple-but great!🎉🎉🎉🎉🎉😂😂😂😂😊😊😊😊😊

  • @nigorazakirova4230
    @nigorazakirova4230 Před 4 dny

    :/

  • @bmk2561
    @bmk2561 Před 5 dny

    4:13 if there is a carry input, then there would be a carry output but 4:19 there is no carry input but why it still propagate a carry?

  • @FerventApathy
    @FerventApathy Před 5 dny

    You have no clue how helpful this is, and how extremely useful it is for what I work on. Thanks!

  • @Kaiylre
    @Kaiylre Před 5 dny

    This was excellent!

  • @SunShine-xc6dh
    @SunShine-xc6dh Před 5 dny

    If program opposite runs on the input the of its own output how will it create an output to begin with. The program that says feed program opposite its own output is broken this says nothing about program halt. A working halt program would tell you program opposite fed its own input a non halting program

  • @SomeGuyWatchingYoutube

    DNS is the flaw 😅

  • @hvnterblack
    @hvnterblack Před 5 dny

    good material

  • @Pepsiandmilkbutalsopalindrome

    3⁴ = 8x3?

  • @user-ek2bw6ml5s
    @user-ek2bw6ml5s Před 6 dny

    ceid moment

  • @guoard
    @guoard Před 6 dny

    Great job!

  • @ToyTherapist
    @ToyTherapist Před 6 dny

    Ok but how do you decrypt it?

  • @pleappleappleap
    @pleappleappleap Před 6 dny

    One usually uses their own left vs right, as opposed to the tree's.

  • @devrajsingh2879
    @devrajsingh2879 Před 6 dny

    thanks it was helpful

  • @tirana.1887
    @tirana.1887 Před 6 dny

    Best explanation out there! Came here after watching several videos on the matter. This was the best by far. Thanks!

  • @jakob5481
    @jakob5481 Před 7 dny

    I feel like this would also be a good moment to make a video about the euler phi function since it massively simplifies such calculations

  • @rajasekharreddy7943

    Thank you little bros

  • @thefrub
    @thefrub Před 7 dny

    This is a great explanation! I wish I had this when I was taking my cryptography class last year

  • @NeverMyRealName
    @NeverMyRealName Před 7 dny

    you should also include the code slowly building as you explain each aspect of the algorithm steps.

  • @alex_zetsu
    @alex_zetsu Před 7 dny

    Is this a follow up to the three pass protocol video?

  • @alex_zetsu
    @alex_zetsu Před 7 dny

    Is there a difference between using 1 hash function that maps to a space N^3 (say 1,000,000,000) and using 3 hash functions that map to space N (say 1,000)?

  • @foobarf8766
    @foobarf8766 Před 7 dny

    You touched on the discrete log problem, so compression functions and their special case of one way hashing next please!

  • @ATOM-vv3xu
    @ATOM-vv3xu Před 7 dny

    Why (if at all) is this preferable to asymmetric encryption?

  • @nguyenthanhtrung9897

    thanks

  • @usptact
    @usptact Před 7 dny

    Thanks for the visual explanation! It was very clear how it works!

  • @tentimesful
    @tentimesful Před 7 dny

    a big company(nasdaq company) didnt have encryption at all. just this multiplication I saw lol... well one of my coworker told me they make for big companies that have secure wifi or else its there problem...

  • @sis_sos
    @sis_sos Před 8 dny

    Why do all tech people have the mark zuckerberg voice

  • @krituos
    @krituos Před 8 dny

    Much better then any course I took on the subject 🎉

  • @slobberingdog72
    @slobberingdog72 Před 8 dny

    Nice and easy explanation. Great job !!

  • @sirhuman560
    @sirhuman560 Před 8 dny

    amazing explanation, well done

  • @marcellopz50
    @marcellopz50 Před 8 dny

    AES walks in like 😡