I don't always understand everything being talked about. I just appreciate being exposed to the knowledge.

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.

*Algorithm* (noun) : Word that programers use when they don't want to explain what they are doing

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

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.

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.

I might have to memorise all these algorithms in case it comes up in an interview

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

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.

Sleep-Sort made me pause, smile, and go “f*king genius” 😂😂😂

Happy to see you covering algorithms! I feel like that is an area of software engineering / computerscience that deserves more love!

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.

Loving the consistency of these videos. Keep up the good work.

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!

This might be my favorite Fireship video to date. The quality, the explanations, the humor, the subject, they are all near-perfect!

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...

that graphic you showed which explains the difference between scalers, vectors, matrices, and tensors is incredibly underrated.

I love the fact that he continues the simulation story line through every video!

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.

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 😊

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.

Don’t forget about the algorithm that controls us all

Wave function collapse is awesome, procedural-generation in general is a really interesting topic of computer science to me.

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.

4:14 that's clever as hell

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.

The speedcubing reference with CFOP is perfect

Awesome video as always, I didn't know about Boids and its exactly what I needed in my Threejs project! I would love it if you could make a video about different kinds of noise, like Voronoi or Perlin!

High quality content sir. That was a tasteful blend between memes and informative information

Particle Life is another amazing algorithm. It's similar to boids but it's simpler and produces way more complex and emergent behaviors.

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.

Shors Algo has recently been improved by Oded Regev. It was basically out of nowhere!

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.

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 😆

Nature-inspired optimisation is SO COOL i love things like ant colony and particle swarms and genetic algorithms o.o

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!

I believe this year someone improved Shor's algorithm by making it multi-dimensional

Fireship is the tinfoil-hat-wearing older brother we all need.

Tbh best fireship video ever... Pls make more of such videos

Crazy to see Boyer-Moore mentioned. I fondly remember their CS class at UT.

Me scared af because some of the "Interesting" algorithms are in my Syllabus

While watching this video i had a panic rithms!

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).

I've actually been looking for something like simulated annealing to help me solve a problem I've been working on. Thanks.

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.

Ive realised Algorithm designing first easens coding step instead of directly going to code

This video is great! More weird algorithms videos in the future?

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.

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.

Could you apply that last one to the library of babel algorithm and find anything? Seems like an interesting project.

I was really struggling with trying to understand marching cubes a week ago, what a timing.

i have a bot that likes every one of my comments

Am I trippin or does Fireship's voice sound AI generated?

Fireship, you're killing it.

Wave function collapse has been my favorite algorithm for a while now. It's really neat, and it has a badass name.

there is no way jeff is using algorithms, it's all AI, right?

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?

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.

Loving the consistency of these videos. Keep up the good work.. Loving the consistency of these videos. Keep up the good work..

Man I really love that sense of humor in your videos

Hey I used the BOIDS algorithm to design a student-faculty management system for our uni glad to see it mentioned here

Oh yeah, Boyer Moore Horspool, had that one in first semester in Informatics. We also programmed Haskell lol.

Wow thank you man, that double slit aws finally makes sense.

Moore was one of my college professors. Loved seeing him pop up at the end!

@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

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.

Dude I absolutely love your humor and you need to do programmer stand up , such a unique humor I love it !

Wow, what a coincidence, I was reading about Boyer-Moore algorithm yesterday.

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...

Yo, these algorithm videos are dope dude

this was great, more vids like this please!

Sweet Roguelike Tutorial my dude

One of your best yet

MRI scan is crazy. It's one of the highest form of engineering the world has ever seen.

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)

Cutting down on AWS bill is highly compelling explanation for the collapse of the wave function; it makes perfect sense.👏

Love this video, very educational

Dude, your humor is amazing

Brilliantly done sir.

Honestly, Proof of Work is one of the most beautiful consensus algorithm, it's so simple.

Immediately my favorite 2 algorithms of all time, I'm definitely watching through this video.

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.

I was hoping you would cover bloom filters

Came to watch as soon as I got the notification!

Early fireship vids hit different

A fireship video that doesn't fill me with existential dread? I'm still full of it, but liking the change of mood.

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

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.

i love this channel so much!!! True definition of edutainment

sleep sort has to be the funniest algorithm i've ever seen

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.

I actually DID wake up with that thought once, I had a 2D MRI scan of my skull and I needed to visualize it in 3D. Despite the technology already existing I was pretty young and I didn’t know. I managed to get it to work on myself.

You are really good at computer science not only creating website you understand deeply inside of computer science

Id love another video like this !😊

That was some spicy interesting content, bravo!

I remember making a Boids project, I even uploaded a video. It consisted of rendering a bunch of mouse cursors to the screen where they would fly around your monitor and avoid the "real" mouse Made for a good background