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 RUclips 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.
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 RUclips 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.
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.
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.
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.
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 ;-).
🎯 Key Takeaways for quick navigation: 00:42 🌐 *Introduction to Weird Algorithms* - Algorithms play a crucial role in solving real-world problems. - Some algorithms are fast, beautiful, and others are exceptionally weird. 01:09 🌊 *Wave Function Collapse Algorithm* - Describes the wave function collapse concept, which can be implemented programmatically. - Relates it to procedural map generation for video games. - Draws a philosophical connection to living in a simulation. 02:03 🤖 *Diffusion Algorithm in AI* - Explains the diffusion algorithm's origin in thermodynamics and its application in AI. - Highlights its role in image generators like DALL-E and Stable Diffusion. - Mentions its potential in audio and upcoming challenges in video generation. 02:44 🏔️ *Simulated Annealing Optimization* - Introduces simulated annealing as an optimization algorithm. - Analogizes its exploration-exploitation trade-off to a career specialization journey. - Provides a metaphor using temperature adjustment in exploring a solution space. 03:41 🛌 *Sleep Sort Algorithm* - Presents the unconventional sleep sort algorithm using Bash. - Delegates sorting to the CPU scheduler, making it both genius and impractical. - Humorously contrasts it with the equally useless BOGO sort algorithm. 04:52 🌌 *Quantum BOGO Sort (Hypothetical)* - Hypothetically explores the concept of Quantum BOGO Sort using multiverse theory. - Imagines leveraging parallel universes to find a sorted array. - Acknowledges the impracticality but raises the concept for consideration. 05:07 🔐 *RSA Encryption Algorithm* - Explains the RSA public key crypto system's importance in digital security. - Highlights the difficulty of factoring large numbers and the potential threat from quantum computers. - Mentions Shor's algorithm and the current limitations of quantum computing in this context. 06:19 📏 *Marching Cubes Algorithm* - Explores the marching cubes algorithm for generating a 3D mesh from scalar field data. - Describes the process of selecting polygons based on the scalar values in a cube. - Discusses its historical significance in rendering 3D data from MRI machines. 07:02 ⚔️ *Byzantine Generals Problem and PBFT Algorithm* - Introduces the Byzantine generals problem in a military context. - Explains the PBFT algorithm as a solution for maintaining consensus in distributed networks. - Emphasizes its relevance to blockchain technology and distributed cloud databases. 07:59 🐦 *Boyd's Artificial Life Program* - Describes Boyd's artificial life program simulating flocking behavior in birds. - Highlights the emergence of intricate patterns from simple rules. - Draws parallels between algorithmic behavior and natural phenomena. 08:29 🧵 *Boyer-Moore String Search Algorithm* - Explains the Boyer-Moore string search algorithm's efficiency in large texts. - Details the algorithm's right-to-left text scanning and rules for character skipping. - Attributes the speed of tools like grep to the effectiveness of this algorithm. Made with HARPA AI
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.
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.
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.
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 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.
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...
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).
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.
The double slit experiment isn't about whether you look or not at something. The term "observation" is really misleading and refers to an act of measurement which always requires disruption or destruction of one kind of information as a cost of another kind information.
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 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)
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 😆
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.
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.
man, your channel is one of the best on RUclips. Thanks for not wasting my time with long as pointless intros begging for likes and subs. Your shit rocks.
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.
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?
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!
My cousin and I have an ongoing conversation that Fireship is in fact an AI that makes these videos and another AI watches the video, then adds the dank memes.
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.
*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
@@capta1nseal"that's what they taught us to do, I don't know why it works..."
I like the idea that there’s a universe where pogosort works every single time and nobody knows why
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
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 RUclips 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! 😎✌️
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.
Loving the consistency of these videos. Keep up the good work.
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 😂
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 RUclips 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.
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.
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
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 RUclips 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!!!!!
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
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 :)
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
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.
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 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
Nature-inspired optimisation is SO COOL i love things like ant colony and particle swarms and genetic algorithms o.o
🎯 Key Takeaways for quick navigation:
00:42 🌐 *Introduction to Weird Algorithms*
- Algorithms play a crucial role in solving real-world problems.
- Some algorithms are fast, beautiful, and others are exceptionally weird.
01:09 🌊 *Wave Function Collapse Algorithm*
- Describes the wave function collapse concept, which can be implemented programmatically.
- Relates it to procedural map generation for video games.
- Draws a philosophical connection to living in a simulation.
02:03 🤖 *Diffusion Algorithm in AI*
- Explains the diffusion algorithm's origin in thermodynamics and its application in AI.
- Highlights its role in image generators like DALL-E and Stable Diffusion.
- Mentions its potential in audio and upcoming challenges in video generation.
02:44 🏔️ *Simulated Annealing Optimization*
- Introduces simulated annealing as an optimization algorithm.
- Analogizes its exploration-exploitation trade-off to a career specialization journey.
- Provides a metaphor using temperature adjustment in exploring a solution space.
03:41 🛌 *Sleep Sort Algorithm*
- Presents the unconventional sleep sort algorithm using Bash.
- Delegates sorting to the CPU scheduler, making it both genius and impractical.
- Humorously contrasts it with the equally useless BOGO sort algorithm.
04:52 🌌 *Quantum BOGO Sort (Hypothetical)*
- Hypothetically explores the concept of Quantum BOGO Sort using multiverse theory.
- Imagines leveraging parallel universes to find a sorted array.
- Acknowledges the impracticality but raises the concept for consideration.
05:07 🔐 *RSA Encryption Algorithm*
- Explains the RSA public key crypto system's importance in digital security.
- Highlights the difficulty of factoring large numbers and the potential threat from quantum computers.
- Mentions Shor's algorithm and the current limitations of quantum computing in this context.
06:19 📏 *Marching Cubes Algorithm*
- Explores the marching cubes algorithm for generating a 3D mesh from scalar field data.
- Describes the process of selecting polygons based on the scalar values in a cube.
- Discusses its historical significance in rendering 3D data from MRI machines.
07:02 ⚔️ *Byzantine Generals Problem and PBFT Algorithm*
- Introduces the Byzantine generals problem in a military context.
- Explains the PBFT algorithm as a solution for maintaining consensus in distributed networks.
- Emphasizes its relevance to blockchain technology and distributed cloud databases.
07:59 🐦 *Boyd's Artificial Life Program*
- Describes Boyd's artificial life program simulating flocking behavior in birds.
- Highlights the emergence of intricate patterns from simple rules.
- Draws parallels between algorithmic behavior and natural phenomena.
08:29 🧵 *Boyer-Moore String Search Algorithm*
- Explains the Boyer-Moore string search algorithm's efficiency in large texts.
- Details the algorithm's right-to-left text scanning and rules for character skipping.
- Attributes the speed of tools like grep to the effectiveness of this algorithm.
Made with HARPA AI
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.
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.
Don’t forget about the algorithm that controls us all
Differential evolution?
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.
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 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
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...
High quality content sir. That was a tasteful blend between memes and informative information
Fireship, you're killing it.
Shors Algo has recently been improved by Oded Regev. It was basically out of nowhere!
Wave function collapse is awesome, procedural-generation in general is a really interesting topic of computer science to me.
Particle Life is another amazing algorithm. It's similar to boids but it's simpler and produces way more complex and emergent behaviors.
I woke up in the middle of the night in a panic to watch this video.
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).
Algorithms are weird until you realize they're genius in specialized circumstances.
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.
This is overwhelming amount of information in just 10 min.
Thanks Fireship for such quality content.
The speedcubing reference with CFOP is perfect
The double slit experiment isn't about whether you look or not at something. The term "observation" is really misleading and refers to an act of measurement which always requires disruption or destruction of one kind of information as a cost of another kind information.
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.
Fireship is the tinfoil-hat-wearing older brother we all need.
I love any video where you don't mention that I'm going to be unemployed.
4:14 that's clever as hell
Weird Al - gorithms... missed opportunity
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
Thanks!
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
@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 believe this year someone improved Shor's algorithm by making it multi-dimensional
Could you apply that last one to the library of babel algorithm and find anything? Seems like an interesting project.
MRI scan is crazy. It's one of the highest form of engineering the world has ever seen.
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
This video is great! More weird algorithms videos in the future?
@0:09 yes, actually
Same, lol
My algorithm is simple - I see Fireship video, I click Fireship video
While watching this video i had a panic rithms!
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.
Hey I used the BOIDS algorithm to design a student-faculty management system for our uni glad to see it mentioned here
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
I'm so engrained into the youtube slop that I instinctively read the title as "Top 10 weird algorithms"
Ive realised Algorithm designing first easens coding step instead of directly going to code
man, your channel is one of the best on RUclips. Thanks for not wasting my time with long as pointless intros begging for likes and subs. Your shit rocks.
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.
Tbh best fireship video ever...
Pls make more of such videos
there is no way jeff is using algorithms, it's all AI, right?
Easily my favorite video of yours!
Am I trippin or does Fireship's voice sound AI generated?
I'm high as hell right now, you got feeling paranoid now lol
It never ceases to amaze me how everything always finds itself being connected to a random genius on 4chan
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
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!
Loving the consistency of these videos. Keep up the good work.. Loving the consistency of these videos. Keep up the good work..
Bogosort being basically gambling amazes me
You are really good at computer science not only creating website you understand deeply inside of computer science
Sweet Roguelike Tutorial my dude
don't understand much and sometimes i feel like this is all gibberish, but i like it
Wow, what a coincidence, I was reading about Boyer-Moore algorithm yesterday.
My favorit sorting algorithm is Starling sort. Simply delete any element which is not in order.
I feel proud as a science student and understanding 95% of everything in the video
its like attending a computer science class as a toddler
A fireship video that doesn't fill me with existential dread? I'm still full of it, but liking the change of mood.
Man I really love that sense of humor in your videos
sleep sort just made my day
Moore was one of my college professors. Loved seeing him pop up at the end!
I was hoping you would cover bloom filters
sleep sort has to be the funniest algorithm i've ever seen
Wow thank you man, that double slit aws finally makes sense.
Dude, your humor is amazing
A 9 minute Fireship video is equivalent to 3 hours
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!
My cousin and I have an ongoing conversation that Fireship is in fact an AI that makes these videos and another AI watches the video, then adds the dank memes.
i love this channel so much!!! True definition of edutainment
One of your best yet
one of the best fireship video.
0:50 that’s actually a common misconception, it doesn’t change when you look at it but instead when you MEASURE the particle