Fireship was helping programmers to add tech to their resumes with 100 second series, now he is helping interviewer with new questions for the interviews.
For the sleep sort one, what if we take the biggest element and scale all elements down by that number. Then, it would take atmost 1 second to sort. Though still it would leave the sorting to the CPU scheduler.
My favorite algorithm is probably Perlin Noise. You touched on procedural generation in your wavefunction collapse portion, but the fact that the result is _deterministic_ (based on the initial seed) and independent of the order of the observations is just mind-blowning.
As a mechanical engineer that later became software developer, it's nice for once to see concepts i actually studied like thermodynamics or metallurgy being related to programming
Videos like this show why developers really need to pay more attention to the *history* of computer science - Simulated Annealing was a cool new idea in *1983*, Boyer-Moore is from the late 70s, Marching Cubes is from 1987 - I recently coded up the Shoelace Formula for something because I learned it from an architect doing concrete-foundation estimation back in the 1980s, but it goes back to 1769 :-)
Diffusion was not first developed at openai. Diffusion as we know it as an image generation technique started as the Denoising Diffusion Probabilistic Models (DDPM) paper that came out from UC Berkley with Ho et al in 2020. Dall-e 1 wasn't even diffusion, it wasn't until far later that openai joined the diffusion scene.
@@en9717 My other comment seems to have been deleted, so I wont try to link the paper again. But the original image generating diffusion model has the arxiv code of arXiv:2006.11239 There have been previous diffusion models before that too, but not to the same extent as the DDPM paper. Regardless, none of them were through OpenAI.
Pieter Abbeel, the doctoral advisor of Ho was one of the main advisors of OpenAI. While diffusion models were developed in Berkeley, it didn’t take long for openAI to join the party even though dalle took some time to release
@@awiewahh Links in TH-cam comments tend to get auto-filtered out, and if they aren't seen by the creator within 30 days and approved, get deleted as spam. Generally it's best to avoid links entirely and try to reference things without them (as you've done above)
My favorite algorithms ATM are ones for video games. You see, video games are in the category of “real time simulation” meaning what you see is actually being computed live. That means that there really isn’t a bunch of resources to use; algorithms must be highly effective. The work of optimization is handled by trying to pre-compute things or fake things. My favorite example are oceans. The best water simulation (like in Sea of Thieves) is faked by pulling past data from real science buoys and essentially replaying real water (lol). Otherwise computing water in real time is terribly expensive. It’s a hack but an example of how a resource constrained environment produces creative solutions.
I hope the field will make a huge leap once generative AI has been incorporated into NPC behavior, 3D texture generation, on-the-fly adjustments of the vibe/music/storyline/difficulty levels etc. Soon games could come out that may play out in ways totally unexpected to the developerts due to the increased degrees of freedom.
@@yoloswaginator A.I model-training combined with the algorithms behind 3D photogrammetry/light-fields has been leading to some magical results lately.
Just a footnote for anyone who sees it, real world wavefunction collapse isn’t dependent on looking at particles. The word observation is used but that’s a catch all term for some form of physical interaction with the particle. Human vision and perception doesn’t have the ability to magically cause collapse, but if we want to look at it, it has to first collapse.
Apprently a guy named Oded Regev just discovered a major improvement to Shor's algorithm. Shor himslef agreed that it vastly improved on his original method.
Right, the TH-cam channel "Quanta Magazine" just released a video about Computer Science Breakthroughs of 2023 and this improvement was one of them. But like mentioned in both videos, it is not yet practical from what I could understand.
wave form collaps is not really related to quantum physics but is cool anyway. An algorithm that i miss is the stochastic gradient descent algorithm, what propelled us into the AI area.
Yeah it's just monte carlo sampling of a distribution defined implicitly in terms of local consistency rules. The quantum BS probably helped its marketing though.
Pedantry warning: SGD is an amazing optimization algorithm, but it is not correct to say that SGD is what propelled us into the current AI era - that would be backpropagation. If you want to assign credit to a single algorithm, it would be more appropriate to assign it to backprop, since backprop is what allows SGD to solve the credit assignment problem in the first place. Without backpropagation, a network cannot learn. Backprop is the algorithm that SGD relies on in neural networks to actually train them. So, it's not SGD but backprop that let us do AI. That being said, the real winner is raw compute power. Things like SGD and backprop have been around for 40+ years (backprop over 50) and were already used in AI as far back as the 1980's. The problem is that you couldn't handle anything with any meaningful depth until the mid-to-late 2000's because the compute power and memory just weren't there. The explosive advancement of AI really is just a matter of hardware advancement, especially anything that allows for parallel computing. Thank you, video games, for getting someone to invent discrete GPUs.
One of your most fascinating videos yet! The fact that you relate so many of these to other fields (quantum physics, medicine, thermodynamics, metallurgy) is really cool. I'd love to see more videos of you relating computer science/programming concepts to other fields and real-world phenomena!
I actually did invent a simpler improved variant of the marching cubes algorithm, while sleeping. And the dream was so vivid I thought I had programmed it, but I could not find the code when awake. So I had to write the code again while awake, and it was so easy the second time.
In the lecture 'Logic of living systems' that included Boids we also covered so called 'Core Wars'. Basically its about different assembler code fighting over memory via replication and 'killing' other code. Maybe you are also interested in this subject 😊
What determines which code wins? I mean is it always going to end the same regardless of architecture or is there something system related that influences the outcome? I tried to find the lecture but there are many with that same name... I could see uses for a system like code snippets fighting over memory...
I DID have dreams about extracting polygonal meshes from isosurfaces when I was 15! Worked on a destructible pseudo-infinite 3D landscape first-person "game" at the time. Marching tetrahedrons was the answer.
I was listening to this on my car on my way back home. This was the kind of stuff that made me love learning computer science and made me go to masters and then PhD (which I never finished). Nowadays I work doing bullshit software that I hate 99% of the time. Doing enterprise software development is atrocious for the mind and soul.
@@o0QuAdSh0t0o I was with heavy clinical depression and probably burn out, too. I was completely disillusioned with the bureaucracy of research grants, the "office politics " at the university, the way my supervisors didn't support or supervise, having to teach first year students (which I liked) while doing all else, including review papers that were supposed to be reviewed by my supervisor... Everything was just too much.
You can add spice to software development too, I used to do that. Finding an excessively elegant way to do something, only comment what it does without any clue to how, and leave it there. Not a very good example but you can check if password rules are followed (mostly) with one quite short regex. Comment it with 'password rule check' and leave it to beaver to then at some later point try to figure out what the password rules actually are, most people don't know regex ;-). You'll have someone ask at some point later, possibly, but they may have a sleepless night over it first. Leave easter eggs that are very hard to find. Use convoluted data models that are defensible as justifiable. Etc ;-).
I think i'm gonna start using sleep sort in my production apps, wpuld work wonders to minimize the CPU usage of my apps. I currently use quantum bogosort, but it's a little too CPU intensive.
when it comes to the factorization problem and other mathematical problems that most modern cryptographic systems use, there are already out there new algorithms that will replace what is currently in use and that are not breakable/exploitable by paralell/quantum computing (these new algorithms use lattice theory).
You should be given some kind of an award man. For years now you have been producing high quality content and your meme choices are just absolutely perfect.
One day, after watching a video from the Veritasium channel, I was inspired to create the same formula they demonstrated in the video. The next day, I woke up in a cold sweat from a nightmare. In the dream, I was writing the same line repeatedly, unable to stop, as if my hands were glued to the keyboard. It was a creepy experience.
Here's a string search algo faster that Boyer-Moore: the FM-index. For searching pattern P in text T, Boyer-Moore has runtime O(|P|+|T|) but FM-index is O(|P|). That's right, it doesn't depend on the length of the text. You can search gigabytes of text just as fast as kilobytes, provided that you've built the FM-index for it.
I remember reading a comment on some other CS related vid that said that back in the old days of coding, programs were like masterful works of art kind of like Baroque music - meant to fulfill a certain task as efficiently and basically not be touched after creation. Probably this led to some really great algorithms being created during that time (though I’m not saying we should revert back to unmaintainable obscure “art” code)
The figure at 6:22 is incorrect. A tensor is not a 3d matrix, it's a more general concept. A scalar is a type of tensor. A vector is a type of tensor. A matrix is a type of tensor. A 3d array is a type of tensor. Tensors are, very informally, objects with n indices that satisfy certain transformation rules.
You're confusing the definitions for math and computer science. They are all essentially arrays of numbers in programming and are just given the names scaler, vector and tensor because they are representations of those objects. In math, a matrix is a linear transformation, and a tensor is a multilinear map (given a basis). The "informal" definition you mentioned is the one usually given in physics and it's only for the components of a tensor (which is typically all you have to worry about since physics should be background independent) but not the object itself.
@@Jang09 No, I am not. First of all, there isn't really a "definition" of tensor specific for computer science, since the term was just lifted from math and physics without much thought and no further theory was developed, and secondly, even if there was, it would still be the case that a tensor has an arbitrary number of indices _because that is the practice where the term tensor is used_ e.g. in machine learning. If you really want to drop the transformation properties, go ahead, but it's pretty silly to come up with a synonym for array. What you cannot do is say it must be 3d, because nobody uses it that way and that's a definition used only by you. " it's only for the components of a tensor" That is incorrect. It is the definition of the object. A single component of a tensor is not a very useful object.
@isodoubIet The transformation law is for the components of a tensor the indices are labeling the components this is pretty standard in physics. The word tensor in computer science is used for multidimensional arrays.
@@Jang09 "The "informal" definition you mentioned is the one usually given in physics and it's only for the components of a tensor " Is what you said above. You said it's _only_ for the components and not for the whole object, which is definitively incorrect. The transformation laws obviously operate on the components, but that's not what you said, nor is it something relevant or useful to bring up. "The word tensor in computer science is used for multidimensional arrays." I literally just explained this. 1. The word tensor is not used productively, its just a cute word that people who don't understand what tensors are decided to use for multidimensional arrays 2. computer science already had multidimensional arrays and 3. "multidimensional" means with an arbitrary number of indices, not just 3, precisely as I stated. You're trying to be absurdly pedantic, which I can appreciate, but you're also failing miserably. Just stop.
@isodoubIet I'm literally just stating that the same word is used in different fields to mean different things 😅 so your first comment doesn't make sense since your trying to use the physics definition on a CS video. And yes the transformation law only refers to the components of the tensor as the tensor itself is invariant to a change of basis.
I actually used Wave Function Collapse recently, helping a friend with his project. It was a machine learning class, and the project involved training a neural network to create the *rules* for wave function collapse to do its thing. It wasn't very successful 😆
6:06 I don't know specifics but I remember my professor saying that there are already algorithms in the making that are theoretically safe from quantum computers.
man, your channel is one of the best on TH-cam. Thanks for not wasting my time with long as pointless intros begging for likes and subs. Your shit rocks.
Weird algorithms summary: Wave Function Collapse (0:43): Procedurally generates maps for video games by collapsing possibilities upon observation. Represents an initial map in superposition, selecting tiles based on consistent rules. Diffusion Algorithm (1:41): Derived from thermodynamics, reverses the process of spreading particles to generate coherent images. Used in image generators like DALL·E and Stable Diffusion, with potential for audio and video generation. Simulated Annealing (2:40): Optimization algorithm inspired by metallurgy, balances exploration and exploitation. Offers a metaphor for a developer's journey from exploring diverse technologies to specializing in one. Sleep Sort (3:40): Unconventional sorting algorithm that delegates sorting to the CPU scheduler through thread sleep times. Genius yet impractical, as it relies on the scheduler to execute the sorting process. Quantum BOGO Sort (4:19): Theoretical sorting algorithm leveraging quantum mechanics and multiverse theory. Hypothetically relies on observing parallel universes to find a pre-sorted array, requiring a portal gun. Shor's Algorithm (4:59): Quantum algorithm for integer factorization, potentially threatening RSA encryption. Leverages quantum concepts like qubits, superposition, and entanglement to perform parallel calculations. Marching Cubes Algorithm (0:00 & 6:10): 3D mesh generation algorithm used for rendering MRI data in 3D. Processes a 3D scalar field to create a mesh by considering neighboring points and predefined polygons. Practical Byzantine Fault Tolerance (PBFT) (6:48): Distributed consensus algorithm essential for maintaining network integrity in the face of node failures. Enables nodes to reach a consensus on executing changes despite up to one-third of nodes behaving unpredictably. Boyd's Artificial Life Program (7:46): Simulates flocking behavior of birds using three simple rules: avoid crowding, align with the average heading, and move towards the center of mass. Demonstrates emergent complexity and beauty arising from simple rules, reflecting natural phenomena. Boyer-Moore String Search Algorithm (8:17): Efficient string search algorithm that becomes faster with larger search strings. Scans text from right to left, utilizing pre-processed tables for skipping characters based on bad character rules and mismatch occurrences.
* Marching Cubes Algorithm (timestamp: 2:42): Used to extract a 3D mesh from a 3D image (like an MRI scan). * Wave Function Collapse (timestamp: 3:12): Used for procedural generation, like creating a map for a video game. * Diffusion (timestamp: 4:01): Machine learning algorithm used to generate images by starting with random noise and gradually refining it. * Simulated Annealing (timestamp: 5:01): Optimization algorithm to find the best solution in a complex problem. * Sleep Sort (timestamp: 5:46): Joke sorting algorithm that uses threads. * BOGO Sort (timestamp: 6:01): Joke sorting algorithm that works by randomly guessing until the array is sorted. * RSA (timestamp: 6:10): Public key cryptography system essential for digital security. * Shor's Algorithm (timestamp: 6:38): Quantum algorithm that can break RSA encryption (theoretical). * Byzantine Generals Problem (timestamp: 7:14): Algorithm used in distributed systems to ensure all computers agree on the state of the system. * Boyds-Cobbins Algorithm (timestamp: 7:40): Simulates flocking behavior of birds. * Boyer-Moore String Search (timestamp: 8:22): Efficient string searching algorithm for long texts.
AFAIK, grep was originally written by Ken Thompson. Yes, the one that was involved in Unix and C and make a significant contribution to running regular expressions.
The one used in Quake III Arena? It's dark magic, the original code even has a line in this function that's commented out with a note that says // 2nd iteration, this can be removed.
Wow. 6:50, I didn't know about the Byzantine stuff, but I reached a similar conclusion when talking about plain crashes, and how I would code its sensors.
The input to the marching cubes algorithm is a *scalar* field, not a *scaler* field. A scalar field is just a set of numbers associated to points in space. Each scalar can be a vector, like if you knew the measurements of wind speed and direction at regular intervals within a 3D area you'd be dealing with scalar fields. If it's about 3D modeling the number could be 1 or 0 to represent the presence of an object, or a quantity representing its color or texture, etc. A scaler is something that scales (resizes) something.
Hey Jeff, since you mentioned weird algorhitms any ideas about extraciting readings in a base-plate of prefabulated aluminite surmounted by a malleable logarithmic casing?
That bird flocking 3 rules system, I heard it was 3 different rules: 1. Flock together 2. Keep equidistant apart 3. Avoid predators. This last one is what creates the spectacular patterns we see when a large crowd looks almost like smoke from a distance.
Cool upload! I've been working on a new digital image Steganography idea that doesn't rely on an algorithm, but leaves the target image untouched and applies a given co-ordinate reference to the target bytes for extraction in the correct sequence. So technically, I could extract a 300KB GIF image of a fishing boat from a 124KB Jpeg image of a wedding dress. So basically you could never extract the boat bytes without the coordinate sequence. Because the boat has not been algoritmically 'worked into' the target image (wedding dress). I'm pretty excited about my findings...
1:25 I just implemented a background to my racing game that moves down and then when it reaches the bottom move up and I have 2 of them so they never see any blank space so idk what kind of algorithm that is.
For my major at uni I studied the WFC, Simulated Annealing, Marching Cubes and boids. I never thought I would hear about those ever again but here we are.
I HAVE "woken up in the middle of the night in a panic wondering how to extract a a polygonal mesh of an isosurface from a three dimensional discrete scalar field". I wrote a Java program that displayed molecular orbits that used the marching cube algorithm. That required lots of patience and discipline. Amazing algorithm, though. Your a different programmer after you implement it. Great subject for a video!
I recently had a conversation with someone who was shocked that I don't think I'm clever. This video proves my point. I am pretty sure if I spent the time I could understand everything in this video, but would I ever invent anything like it.. nah Thank you so much for all these great videos!
3:42 For those not getting why this is funny, algorithmic complexity (basically how good an algorithm is at handling lots of data) if measured using big-O notation, where bubble sort is O(n²) (quadratic: really bad), quick sort is O(n log n) (good), and this abomination is, technically, O(n) (the holy grail of sorting algorithms). The only problem is that big-O only cares about growth, not actual speed, so taking (at least) an entire second per element is favoured because even quicksort would, eventually, be overtaken by it, at least in theory
I remember how Wave Function Collapse was theme of my first course work i ever made. It's so much easier to understend then other generative algorithms
I don't always understand everything being talked about. I just appreciate being exposed to the knowledge.
U can get far then mate
that's the mindset
that's because you only watch it once, watch it one time on a faster speed then again on a slower. now you actually understand
Same here😅
Don't worry, probably there is a parallel universe where you understand this video.
Fireship was helping programmers to add tech to their resumes with 100 second series, now he is helping interviewer with new questions for the interviews.
🤣 I literally thought of asking these questions in interviews
Better than memorizing leetcode
Or maybe the programmer can do a reverse uno on the interviewer.
0:00 - Intro
0:43 - Wave Function Collapse
1:41 - Diffusion
2:40 - Simulated Annealing
3:40 - Sleep Sort
4:19 - Quantum Bogosort
4:59 - Shor's
6:10 - Marching Cubes
6:48 - Byzantine Fault Tolerance
7:46 - Boids
8:17 - Boyer Moore
thanks a lot
Ahh so much better with your comment thank you so much ❤❤❤
Video isn't that big that you need timestamp tho
Here is the other legend, thanks a lot
For the sleep sort one, what if we take the biggest element and scale all elements down by that number. Then, it would take atmost 1 second to sort. Though still it would leave the sorting to the CPU scheduler.
My favorite algorithm is probably Perlin Noise. You touched on procedural generation in your wavefunction collapse portion, but the fact that the result is _deterministic_ (based on the initial seed) and independent of the order of the observations is just mind-blowning.
simplex noise is far better
Perlin (and Simplex) Noise work by using a pseudo random generator such as Mersenne Twister.
Haaa yes here we have a minecraft enjoyer.
Using a seed for procedural generation is mind blowing?
@@sjoerdev Ken Perlin invented them both.
As a mechanical engineer that later became software developer, it's nice for once to see concepts i actually studied like thermodynamics or metallurgy being related to programming
same
Same here
Mechanical engineers work as anything but mechanics.
actually, every engineering problem/topic can be somehow be related to programming
Videos like this show why developers really need to pay more attention to the *history* of computer science - Simulated Annealing was a cool new idea in *1983*, Boyer-Moore is from the late 70s, Marching Cubes is from 1987 - I recently coded up the Shoelace Formula for something because I learned it from an architect doing concrete-foundation estimation back in the 1980s, but it goes back to 1769 :-)
Diffusion was not first developed at openai. Diffusion as we know it as an image generation technique started as the Denoising Diffusion Probabilistic Models (DDPM) paper that came out from UC Berkley with Ho et al in 2020. Dall-e 1 wasn't even diffusion, it wasn't until far later that openai joined the diffusion scene.
Wrong
@@en9717 My other comment seems to have been deleted, so I wont try to link the paper again. But the original image generating diffusion model has the arxiv code of arXiv:2006.11239
There have been previous diffusion models before that too, but not to the same extent as the DDPM paper. Regardless, none of them were through OpenAI.
@@awiewahh yeah i don't think someone that only replied "wrong" knows what they're talking about, just a troll
Pieter Abbeel, the doctoral advisor of Ho was one of the main advisors of OpenAI. While diffusion models were developed in Berkeley, it didn’t take long for openAI to join the party even though dalle took some time to release
@@awiewahh Links in TH-cam comments tend to get auto-filtered out, and if they aren't seen by the creator within 30 days and approved, get deleted as spam. Generally it's best to avoid links entirely and try to reference things without them (as you've done above)
Happy to see you covering algorithms! I feel like that is an area of software engineering / computerscience that deserves more love!
🍻 Thinking it's about time the Cooley-Tukey FFT algorithm had its own special commemorative day, with festivities! 😎✌️
*Algorithm* (noun) :
Word that programers use when they don't want to explain what they are doing
These days it's getting increasingly common that the programmer doesn't know either
LMAO
@@capta1nseal
@@capta1nseal"that's what they taught us to do, I don't know why it works..."
I might have to memorise all these algorithms in case it comes up in an interview
its never a problem if you never knew, but its a problem now that you know these exist but cant remember when need comes to be
@@abhijeetas7886 soo , it's better to have it and not need it, than need it and not have it?
doubt you will ever understand this algos, let alone remember...
I'll just use the boyer moore algorithm to searh this channel for the word 'algorithm' @@abhijeetas7886
If you get these algorithms asked in the interview, you're either secretly getting hired by the Illuminati or you're not getting hired at all
My favorite algorithms ATM are ones for video games. You see, video games are in the category of “real time simulation” meaning what you see is actually being computed live. That means that there really isn’t a bunch of resources to use; algorithms must be highly effective.
The work of optimization is handled by trying to pre-compute things or fake things. My favorite example are oceans. The best water simulation (like in Sea of Thieves) is faked by pulling past data from real science buoys and essentially replaying real water (lol). Otherwise computing water in real time is terribly expensive. It’s a hack but an example of how a resource constrained environment produces creative solutions.
That's actually hilarious, so often nowadays we just forget the simplest solution.
That acerolas video on it is amazing
I hope the field will make a huge leap once generative AI has been incorporated into NPC behavior, 3D texture generation, on-the-fly adjustments of the vibe/music/storyline/difficulty levels etc. Soon games could come out that may play out in ways totally unexpected to the developerts due to the increased degrees of freedom.
I used a similar hack for my mobile 2d game
@@yoloswaginator A.I model-training combined with the algorithms behind 3D photogrammetry/light-fields has been leading to some magical results lately.
Sleep-Sort made me pause, smile, and go “f*king genius” 😂😂😂
Honestly laughed my ass off at that one
It's basically Spaghetti Sort, but slower 😂
Loving the consistency of these videos. Keep up the good work.
I like the idea that there’s a universe where pogosort works every single time and nobody knows why
I've actually had bogosort run successfully a couple of times and even showed it to others, but for some reason nobody seems to remember that...
Just choose n = 1 then to repeat your success :)
that graphic you showed which explains the difference between scalers, vectors, matrices, and tensors is incredibly underrated.
scalar* (even though the video itself made this typo several times!)
@@binarymystic scales
Just a footnote for anyone who sees it, real world wavefunction collapse isn’t dependent on looking at particles. The word observation is used but that’s a catch all term for some form of physical interaction with the particle. Human vision and perception doesn’t have the ability to magically cause collapse, but if we want to look at it, it has to first collapse.
This might be my favorite Fireship video to date. The quality, the explanations, the humor, the subject, they are all near-perfect!
I agree - high quality, low bs! How TH-cam should be. 11 -> fire ship info/density algo
Let's see Paul Allen's favourite fireship video
Based ena pfp
same
because its ai ,its hard for humans .WAKE UP FROM THE MATRIX!!!!!
Apprently a guy named Oded Regev just discovered a major improvement to Shor's algorithm. Shor himslef agreed that it vastly improved on his original method.
Right, the TH-cam channel "Quanta Magazine" just released a video about Computer Science Breakthroughs of 2023 and this improvement was one of them. But like mentioned in both videos, it is not yet practical from what I could understand.
Shor, Mara, Dibella, Kynareth, Akatosh. Divines, please help me.
@@oggolbat7932I love you 😂
Make sure you frequent Quanta's website. It's one of the best for tech and science@@mihailovasic4623
@@mihailovasic4623 That's gotta be the best random-ass lore snippet insertion I've seen in years.
wave form collaps is not really related to quantum physics but is cool anyway. An algorithm that i miss is the stochastic gradient descent algorithm, what propelled us into the AI area.
Any good course about it ?
Yeah it's just monte carlo sampling of a distribution defined implicitly in terms of local consistency rules. The quantum BS probably helped its marketing though.
It might be more accurate to call it something like "Random field collapse" because it's unrelated to the quantum wave function. But still cool!
I was expecting something related to Signed Distance Fields... Graphics programming has some insanely ways of overcoming challenges
Pedantry warning: SGD is an amazing optimization algorithm, but it is not correct to say that SGD is what propelled us into the current AI era - that would be backpropagation. If you want to assign credit to a single algorithm, it would be more appropriate to assign it to backprop, since backprop is what allows SGD to solve the credit assignment problem in the first place. Without backpropagation, a network cannot learn. Backprop is the algorithm that SGD relies on in neural networks to actually train them. So, it's not SGD but backprop that let us do AI.
That being said, the real winner is raw compute power. Things like SGD and backprop have been around for 40+ years (backprop over 50) and were already used in AI as far back as the 1980's. The problem is that you couldn't handle anything with any meaningful depth until the mid-to-late 2000's because the compute power and memory just weren't there. The explosive advancement of AI really is just a matter of hardware advancement, especially anything that allows for parallel computing. Thank you, video games, for getting someone to invent discrete GPUs.
One of your most fascinating videos yet! The fact that you relate so many of these to other fields (quantum physics, medicine, thermodynamics, metallurgy) is really cool. I'd love to see more videos of you relating computer science/programming concepts to other fields and real-world phenomena!
I actually did invent a simpler improved variant of the marching cubes algorithm, while sleeping.
And the dream was so vivid I thought I had programmed it, but I could not find the code when awake.
So I had to write the code again while awake, and it was so easy the second time.
r/thathappened
Link to the repo or didn't happen
I use it on my own 3D-printer projects. Code is secret for now@@Fran-kc2gu
you aren't special, Kim.
I have several world records.@@lgbtthefeministgamer4039
In the lecture 'Logic of living systems' that included Boids we also covered so called 'Core Wars'. Basically its about different assembler code fighting over memory via replication and 'killing' other code. Maybe you are also interested in this subject 😊
What determines which code wins? I mean is it always going to end the same regardless of architecture or is there something system related that influences the outcome? I tried to find the lecture but there are many with that same name... I could see uses for a system like code snippets fighting over memory...
I DID have dreams about extracting polygonal meshes from isosurfaces when I was 15! Worked on a destructible pseudo-infinite 3D landscape first-person "game" at the time. Marching tetrahedrons was the answer.
@stephanenouafo
1 day ago
0:00 - Intro
0:43 - Wave Function Collapse
1:41 - Diffusion
2:40 - Simulated Annealing
3:40 - Sleep Sort
4:19 - Quantum Bogosort
4:59 - Shor's
6:10 - Marching Cubes
6:48 - Byzantine Fault Tolerance
7:46 - Boids
8:17 - Boyer Moore
I was listening to this on my car on my way back home. This was the kind of stuff that made me love learning computer science and made me go to masters and then PhD (which I never finished).
Nowadays I work doing bullshit software that I hate 99% of the time. Doing enterprise software development is atrocious for the mind and soul.
What made you stop the PhD? Curious as a CS major working towards Bachelor’s atm
@@o0QuAdSh0t0o I was with heavy clinical depression and probably burn out, too. I was completely disillusioned with the bureaucracy of research grants, the "office politics " at the university, the way my supervisors didn't support or supervise, having to teach first year students (which I liked) while doing all else, including review papers that were supposed to be reviewed by my supervisor... Everything was just too much.
You can add spice to software development too, I used to do that. Finding an excessively elegant way to do something, only comment what it does without any clue to how, and leave it there. Not a very good example but you can check if password rules are followed (mostly) with one quite short regex. Comment it with 'password rule check' and leave it to beaver to then at some later point try to figure out what the password rules actually are, most people don't know regex ;-). You'll have someone ask at some point later, possibly, but they may have a sleepless night over it first. Leave easter eggs that are very hard to find. Use convoluted data models that are defensible as justifiable. Etc ;-).
@@noth606you know that won't get past the code review
I love the fact that he continues the simulation story line through every video!
Or how he mention to kill your look a like version of you self..( 😂)
portal jump to steal their advancement and bring it back.. 😮
I think i'm gonna start using sleep sort in my production apps, wpuld work wonders to minimize the CPU usage of my apps. I currently use quantum bogosort, but it's a little too CPU intensive.
Hey look, it's the I Hate Myself Dev!
sleep sort is basically counting sort
make sure you document the metrics well so you get yourself a raise!
try to sort [ 8,2, 99999999999999999999999999999999999999] with sleep sort
Wave function collapse is awesome, procedural-generation in general is a really interesting topic of computer science to me.
when it comes to the factorization problem and other mathematical problems that most modern cryptographic systems use, there are already out there new algorithms that will replace what is currently in use and that are not breakable/exploitable by paralell/quantum computing (these new algorithms use lattice theory).
You should be given some kind of an award man. For years now you have been producing high quality content and your meme choices are just absolutely perfect.
Shors Algo has recently been improved by Oded Regev. It was basically out of nowhere!
One day, after watching a video from the Veritasium channel, I was inspired to create the same formula they demonstrated in the video. The next day, I woke up in a cold sweat from a nightmare. In the dream, I was writing the same line repeatedly, unable to stop, as if my hands were glued to the keyboard. It was a creepy experience.
Don’t forget about the algorithm that controls us all
Differential evolution?
Particle Life is another amazing algorithm. It's similar to boids but it's simpler and produces way more complex and emergent behaviors.
Nature-inspired optimisation is SO COOL i love things like ant colony and particle swarms and genetic algorithms o.o
Here's a string search algo faster that Boyer-Moore: the FM-index. For searching pattern P in text T, Boyer-Moore has runtime O(|P|+|T|) but FM-index is O(|P|). That's right, it doesn't depend on the length of the text. You can search gigabytes of text just as fast as kilobytes, provided that you've built the FM-index for it.
I remember reading a comment on some other CS related vid that said that back in the old days of coding, programs were like masterful works of art kind of like Baroque music - meant to fulfill a certain task as efficiently and basically not be touched after creation. Probably this led to some really great algorithms being created during that time (though I’m not saying we should revert back to unmaintainable obscure “art” code)
so this is where the saying "if it works don't fix it" originates from
High quality content sir. That was a tasteful blend between memes and informative information
Me scared af because some of the "Interesting" algorithms are in my Syllabus
What course was it?
Finishing my degree and never encountered any of these
The speedcubing reference with CFOP is perfect
0:50 that’s actually a common misconception, it doesn’t change when you look at it but instead when you MEASURE the particle
The figure at 6:22 is incorrect. A tensor is not a 3d matrix, it's a more general concept. A scalar is a type of tensor. A vector is a type of tensor. A matrix is a type of tensor. A 3d array is a type of tensor. Tensors are, very informally, objects with n indices that satisfy certain transformation rules.
You're confusing the definitions for math and computer science. They are all essentially arrays of numbers in programming and are just given the names scaler, vector and tensor because they are representations of those objects.
In math, a matrix is a linear transformation, and a tensor is a multilinear map (given a basis).
The "informal" definition you mentioned is the one usually given in physics and it's only for the components of a tensor (which is typically all you have to worry about since physics should be background independent) but not the object itself.
@@Jang09 No, I am not. First of all, there isn't really a "definition" of tensor specific for computer science, since the term was just lifted from math and physics without much thought and no further theory was developed, and secondly, even if there was, it would still be the case that a tensor has an arbitrary number of indices _because that is the practice where the term tensor is used_ e.g. in machine learning. If you really want to drop the transformation properties, go ahead, but it's pretty silly to come up with a synonym for array. What you cannot do is say it must be 3d, because nobody uses it that way and that's a definition used only by you.
" it's only for the components of a tensor"
That is incorrect. It is the definition of the object. A single component of a tensor is not a very useful object.
@isodoubIet The transformation law is for the components of a tensor the indices are labeling the components this is pretty standard in physics. The word tensor in computer science is used for multidimensional arrays.
@@Jang09 "The "informal" definition you mentioned is the one usually given in physics and it's only for the components of a tensor "
Is what you said above. You said it's _only_ for the components and not for the whole object, which is definitively incorrect. The transformation laws obviously operate on the components, but that's not what you said, nor is it something relevant or useful to bring up.
"The word tensor in computer science is used for multidimensional arrays."
I literally just explained this. 1. The word tensor is not used productively, its just a cute word that people who don't understand what tensors are decided to use for multidimensional arrays 2. computer science already had multidimensional arrays and 3. "multidimensional" means with an arbitrary number of indices, not just 3, precisely as I stated.
You're trying to be absurdly pedantic, which I can appreciate, but you're also failing miserably. Just stop.
@isodoubIet I'm literally just stating that the same word is used in different fields to mean different things 😅 so your first comment doesn't make sense since your trying to use the physics definition on a CS video.
And yes the transformation law only refers to the components of the tensor as the tensor itself is invariant to a change of basis.
This is overwhelming amount of information in just 10 min.
Thanks Fireship for such quality content.
I actually used Wave Function Collapse recently, helping a friend with his project. It was a machine learning class, and the project involved training a neural network to create the *rules* for wave function collapse to do its thing. It wasn't very successful 😆
Thank God it failed. Otherwise that would've been the first step to create the Generals for our AI overlords
6:06 I don't know specifics but I remember my professor saying that there are already algorithms in the making that are theoretically safe from quantum computers.
I believe this year someone improved Shor's algorithm by making it multi-dimensional
4:14 that's clever as hell
Could you apply that last one to the library of babel algorithm and find anything? Seems like an interesting project.
man, your channel is one of the best on TH-cam. Thanks for not wasting my time with long as pointless intros begging for likes and subs. Your shit rocks.
Weird algorithms summary:
Wave Function Collapse (0:43):
Procedurally generates maps for video games by collapsing possibilities upon observation. Represents an initial map in superposition, selecting tiles based on consistent rules.
Diffusion Algorithm (1:41):
Derived from thermodynamics, reverses the process of spreading particles to generate coherent images. Used in image generators like DALL·E and Stable Diffusion, with potential for audio and video generation.
Simulated Annealing (2:40):
Optimization algorithm inspired by metallurgy, balances exploration and exploitation. Offers a metaphor for a developer's journey from exploring diverse technologies to specializing in one.
Sleep Sort (3:40):
Unconventional sorting algorithm that delegates sorting to the CPU scheduler through thread sleep times. Genius yet impractical, as it relies on the scheduler to execute the sorting process.
Quantum BOGO Sort (4:19):
Theoretical sorting algorithm leveraging quantum mechanics and multiverse theory. Hypothetically relies on observing parallel universes to find a pre-sorted array, requiring a portal gun.
Shor's Algorithm (4:59):
Quantum algorithm for integer factorization, potentially threatening RSA encryption. Leverages quantum concepts like qubits, superposition, and entanglement to perform parallel calculations.
Marching Cubes Algorithm (0:00 & 6:10):
3D mesh generation algorithm used for rendering MRI data in 3D. Processes a 3D scalar field to create a mesh by considering neighboring points and predefined polygons.
Practical Byzantine Fault Tolerance (PBFT) (6:48):
Distributed consensus algorithm essential for maintaining network integrity in the face of node failures. Enables nodes to reach a consensus on executing changes despite up to one-third of nodes behaving unpredictably.
Boyd's Artificial Life Program (7:46):
Simulates flocking behavior of birds using three simple rules: avoid crowding, align with the average heading, and move towards the center of mass. Demonstrates emergent complexity and beauty arising from simple rules, reflecting natural phenomena.
Boyer-Moore String Search Algorithm (8:17):
Efficient string search algorithm that becomes faster with larger search strings. Scans text from right to left, utilizing pre-processed tables for skipping characters based on bad character rules and mismatch occurrences.
Fireship, you're killing it.
Fireship is the tinfoil-hat-wearing older brother we all need.
MRI scan is crazy. It's one of the highest form of engineering the world has ever seen.
@0:09 yes, actually
Same, lol
* Marching Cubes Algorithm (timestamp: 2:42): Used to extract a 3D mesh from a 3D image (like an MRI scan).
* Wave Function Collapse (timestamp: 3:12): Used for procedural generation, like creating a map for a video game.
* Diffusion (timestamp: 4:01): Machine learning algorithm used to generate images by starting with random noise and gradually refining it.
* Simulated Annealing (timestamp: 5:01): Optimization algorithm to find the best solution in a complex problem.
* Sleep Sort (timestamp: 5:46): Joke sorting algorithm that uses threads.
* BOGO Sort (timestamp: 6:01): Joke sorting algorithm that works by randomly guessing until the array is sorted.
* RSA (timestamp: 6:10): Public key cryptography system essential for digital security.
* Shor's Algorithm (timestamp: 6:38): Quantum algorithm that can break RSA encryption (theoretical).
* Byzantine Generals Problem (timestamp: 7:14): Algorithm used in distributed systems to ensure all computers agree on the state of the system.
* Boyds-Cobbins Algorithm (timestamp: 7:40): Simulates flocking behavior of birds.
* Boyer-Moore String Search (timestamp: 8:22): Efficient string searching algorithm for long texts.
I love any video where you don't mention that I'm going to be unemployed.
Hey I used the BOIDS algorithm to design a student-faculty management system for our uni glad to see it mentioned here
While watching this video i had a panic rithms!
AFAIK, grep was originally written by Ken Thompson. Yes, the one that was involved in Unix and C and make a significant contribution to running regular expressions.
My favourite is fast inverse square root. Never seen a more weird algorithm than that in my life. Its just so random but also so useful.
The one used in Quake III Arena? It's dark magic, the original code even has a line in this function that's commented out with a note that says // 2nd iteration, this can be removed.
Oh yeah, Boyer Moore Horspool, had that one in first semester in Informatics. We also programmed Haskell lol.
i have a bot that likes every one of my comments
your comment has one like - seems accurate
I'd like to imagine there's only 1 bot and it likes your comments once and nothing else
realy ?
no wonder the video mentions most algorithms worth going into dumpsters 🫠
Lol
Ive realised Algorithm designing first easens coding step instead of directly going to code
Wow. 6:50, I didn't know about the Byzantine stuff, but I reached a similar conclusion when talking about plain crashes, and how I would code its sensors.
The input to the marching cubes algorithm is a *scalar* field, not a *scaler* field. A scalar field is just a set of numbers associated to points in space. Each scalar can be a vector, like if you knew the measurements of wind speed and direction at regular intervals within a 3D area you'd be dealing with scalar fields. If it's about 3D modeling the number could be 1 or 0 to represent the presence of an object, or a quantity representing its color or texture, etc. A scaler is something that scales (resizes) something.
A field of vector isn’t a scalar field, it’s a vector field
Wow, what a coincidence, I was reading about Boyer-Moore algorithm yesterday.
Hey Jeff, since you mentioned weird algorhitms any ideas about extraciting readings in a base-plate of prefabulated aluminite surmounted by a malleable logarithmic casing?
go sleep
there is no way jeff is using algorithms, it's all AI, right?
Thanks!
Am I trippin or does Fireship's voice sound AI generated?
I'm high as hell right now, you got feeling paranoid now lol
Wave function collapse has been my favorite algorithm for a while now. It's really neat, and it has a badass name.
That bird flocking 3 rules system, I heard it was 3 different rules:
1. Flock together
2. Keep equidistant apart
3. Avoid predators.
This last one is what creates the spectacular patterns we see when a large crowd looks almost like smoke from a distance.
Soooo much content that by the end of your videos I can’t remember what you said at the beginning of the video.
Pretty entertaining! Thanks!
Cool upload!
I've been working on a new digital image Steganography idea that doesn't rely on an algorithm, but leaves the target image untouched and applies a given co-ordinate reference to the target bytes for extraction in the correct sequence. So technically, I could extract a 300KB GIF image of a fishing boat from a 124KB Jpeg image of a wedding dress. So basically you could never extract the boat bytes without the coordinate sequence.
Because the boat has not been algoritmically 'worked into' the target image (wedding dress).
I'm pretty excited about my findings...
That sounds interesting!
1:25 I just implemented a background to my racing game that moves down and then when it reaches the bottom move up and I have 2 of them so they never see any blank space so idk what kind of algorithm that is.
For my major at uni I studied the WFC, Simulated Annealing, Marching Cubes and boids. I never thought I would hear about those ever again but here we are.
Tbh best fireship video ever...
Pls make more of such videos
Easily my favorite video of yours!
I HAVE "woken up in the middle of the night in a panic wondering how to extract a a polygonal mesh of an isosurface from a three dimensional discrete scalar field".
I wrote a Java program that displayed molecular orbits that used the marching cube algorithm. That required lots of patience and discipline. Amazing algorithm, though. Your a different programmer after you implement it.
Great subject for a video!
I recently had a conversation with someone who was shocked that I don't think I'm clever. This video proves my point. I am pretty sure if I spent the time I could understand everything in this video, but would I ever invent anything like it.. nah
Thank you so much for all these great videos!
Loving the consistency of these videos. Keep up the good work.. Loving the consistency of these videos. Keep up the good work..
I woke up in the middle of the night in a panic to watch this video.
A fireship video that doesn't fill me with existential dread? I'm still full of it, but liking the change of mood.
Moore was one of my college professors. Loved seeing him pop up at the end!
You are really good at computer science not only creating website you understand deeply inside of computer science
This video is great! More weird algorithms videos in the future?
3:42 For those not getting why this is funny, algorithmic complexity (basically how good an algorithm is at handling lots of data) if measured using big-O notation, where bubble sort is O(n²) (quadratic: really bad), quick sort is O(n log n) (good), and this abomination is, technically, O(n) (the holy grail of sorting algorithms). The only problem is that big-O only cares about growth, not actual speed, so taking (at least) an entire second per element is favoured because even quicksort would, eventually, be overtaken by it, at least in theory
Honestly, Proof of Work is one of the most beautiful consensus algorithm, it's so simple.
5:17 Bonus points for the biological algorithm happening in the background!
I'm so engrained into the youtube slop that I instinctively read the title as "Top 10 weird algorithms"
Crazy to see Boyer-Moore mentioned. I fondly remember their CS class at UT.
Man I really love that sense of humor in your videos
I feel proud as a science student and understanding 95% of everything in the video
Interesting how this faceless channel is so highly valuable! You changed my perspective on faceless YT channels
I remember how Wave Function Collapse was theme of my first course work i ever made. It's so much easier to understend then other generative algorithms
4:58 I shiver at the possibility that Bogo Sort might one day actually be useful.
I love how Terry always pops up. Gotta keep the legends alive.... So bitter sweet
0:50 I recognize that graphic! It's from a german 100sekundenphysik video about it! Cool
When I realized sleep sort actually sorts it blew my mind. It might not be fast but at least it runs the same speed on an old computer vs a new one.
Cutting down on AWS bill is highly compelling explanation for the collapse of the wave function; it makes perfect sense.👏