![Spanning Tree](/img/default-banner.jpg)
- Видео 27
- Просмотров 10 614 154
Spanning Tree
США
Добавлен 23 ноя 2019
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/
Spanning Tree is created by Brian Yu. brianyu.me/
Email me at brian@spanningtree.me to suggest a future topic.
Support the channel: ko-fi.com/spanningtree
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/
Spanning Tree is created by Brian Yu. brianyu.me/
Email me at brian@spanningtree.me to suggest a future topic.
Support the channel: ko-fi.com/spanningtree
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.
***
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!
How Google's PageRank Algorithm Works
Просмотров 117 тыс.4 года назад
How Google's PageRank Algorithm Works
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?
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
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.
doesn't "giving opposite program itself as input" produce infinite recursion or something?
Great vid!
❤❤❤❤❤
Really nice video! I could watch animations of values getting inserted and deleted on binary trees all day.
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.
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.
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!
What about a program that will tell whether Halt can do work properly or not.
Thank you for an amazing explanation regarding logic gates.
Ahhh probability this one
This is a really great explanation.
I think the reason for the binary tree is the structure of CPUs.
i came here because of scrap mechanic
U are a legend! Keep doing good work
Greaty video! Presented well and easy to understand. :)
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.
looks like cell split
actually, the "walk" program will stop eventually given -1 as input, due to integer overflow.
This videos is soooo good.
Cool video! What do you use to make the animations by the way? They remind me of three.js renders
Also how to share wives
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?
The chances in getting such a pattern would be 1/7^69,600
All of this just to say good morning!? I'd go back to bed at that point
very nice video, love it ♥
Excellenct video
Well explained, thanks a lot
Thanks!
It might be more interesting to do this in the real world without mod functions, as in actually exchange a physical key
He sounds like Brian from cs50x
You are cooked.
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.
The power of concensus, good old anarchy ♡
I don't like this. Just add nodes by layers.
sooo cool!!!
every other video explaining B trees must be deleted to save space and time. This is perfect explanation.
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.
Phenomenal teaching! please do more computer programming related concepts, love this!
Really useful
en passant spotted
amazing video. wish we could have this for litterally everything.
I didn't even completed minute of the video yet, i've subscribed the channel.
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?
Nice video. Think you can greatly improve audio with some sound deadening 😁
PLs make more simple algorithms
Huh, I knew and studied this, technically, but this made it less "black magic" where the math was concerned. Thanks!
If it's a Secret why would you want to share it. if you do it is no longer a secret.
I loved it ❤