10 weird algorithms

have you ever woken up in the middle of the night in a panic wondering how to extract a polygonal mesh of an ISO surface from a three-dimensional discrete scalar field yeah I didn't think so but back in ' 87 two programmers at General Electric did they created and patented the marching cubes algorithm an algorithm that is likely saved countless lives by allowing doctors to visualize data from CT and MRI scans whenever you instruct a machine to solve a problem with code you're creating an algorithm a procedure for rearranging ones and zeros that can make animals talk and vacuums walk most algorithms belong in the dumpster but some are fast some are beautiful and some are so weird they're indistinguishable from Magic today we'll look at 10 of the most interesting algorithms ever engineered and how they're used to solve very interesting problems in the real world first on the list we have wave function collapse one of the weirdest things in all of science is the double slit experiment where particles behave like a wave when you're not looking but when you look they suddenly collapse down to a particle it seems counterintuitive but it makes total sense when you realize we're living in a simulation and the universe wrote this algorithm to cut down on its AWS bill it's an interesting concept to think about philosophically but the general idea behind wave function collapse can also be implemented programmatically imagine we have a map for a video game but what if this is a sidescrolling game that can go on for eternity we can't just make a bigger map we need an algorithm to procedurally generate it on the Fly what's so weird is that we can take this initial map and think of it as being in the initial super position of all possibilities it's the wave function then upon observation it collapses into a particle or in other words it selects a Rand a map tile but follows a consistent set of rules like in this case making sure that the roads are always connected providing a random yet cohesive result and doesn't rely on any sort of modern generative AI speaking of which AI is weird as hell diffusion is a machine learning algorithm originally developed at open Ai and is the magic behind image generators like Dolly and stable diffusion but the concept of diffusion actually comes from thermodynamics where particles spread from areas of higher concentration to lower concentration in artificial intelligence the process is r reversed the algorithm starts by generating random noise which would be like high entropy in thermodynamics and gradually refines it to a structured image which would be lower entropy but first you'll need to train a model that can do this well the diffusion algorithm Works in two phases in the forward phase it gradually adds noise to an image step by step until it becomes completely random in the second phase the algorithm reverses this process reconstructing it back into a coherent image when the algorithm runs over millions of labeled images we get a collection of Weights that can be used to generate new images out of thin air allowing us to build an infinite Army of only fans models it's highly compute intensive but also works well on audio and the next Frontier is diffusion for video generation but now let's talk about simulated analing one frustrating thing about programming is that for many problems there's not just one solution but many solutions like an Amazon warehouse has many different ways to organize its inventory but some ways are more efficient than others an neine is a word that comes from metery where metals are heated up and cooled down over and over again to to remove defects the same idea is used in optimization algorithms to find the best answer in a CA of good answers imagine trying to find the highest point in a mountain range full of Peaks and valleys a simple Hill Climb algorithm won't work because there are many local Peaks initially the temperature starts High allowing the algorithm to explore freely as time goes on though the temperature is lowered which decreases the probability of accepting a worse solution the trade-off here is exploration versus exploitation but the reason I included this algorithm is because it's also a good way for beginners to learn how to code initially you start out exploring all kinds of different Technologies and Frameworks then eventually you find one specific area to exploit and specialize in but we can't talk about algorithms without talking about sorting and the most ingenious sorting algorithm of all time is without a doubt sleep sort the majority of say sorting algorithms out there use strategies like divide and conquer to break up an array into subarrays where it can be sorted more efficiently however some random genius on forchan found a better way but it's a bit unconventional here's what the code looks like in Bash it's incredibly simple it Loops over the array and then for each element it opens up a new thread that sleeps for the amount of time proportional to the value of its element then finally after waking up it prints that element it's genius because it delegates the Sorting to the CPU scheduler it's also incredibly dumb and useless because it delegates sorting to the CPU scheduler speaking of which you might be familiar with another useless sorting algorithm BOGO sort which tries to sort an array by randomly guessing over and over again it's like playing the lottery but what if we apply the same algorithm with Quant mechanics to the Multiverse if we're to trust Multiverse science we know that all possible outcomes exist in separate parallel universes that means as a developer if you find yourself with an unsorted array there's some other parallel universe where it is sorted the technology isn't quite there yet but if we could randomly observe these other universes to find the sworded array we could then use a portal gun to travel to that Universe which would make our lives much easier although we would obviously have to kill the version of oursel in that universe but if it's a really large array Quantum BOGO sort might be worth it that's purely hypothetical but one of the most practical and goed algorithms of all time is RSA a public key crypto system it's essential for digital security allowing people on the internet to lock their mailboxes and sign their letters with a unique signature but it's based on one simple mathematical reality multiplying large numbers to find two original large prime numbers is extremely difficult and timec consuming like it take your laptop 300 trillion years to brew Force unless quantum computers become a thing and we can start leveraging Shores algorithm which can solve the integer factorization problem exponentially faster than any classical algorithm Prime factoring is pretty simple but how this algorithm does it is where things get weird it relies on Concepts like cubits superposition and entanglement to perform massive amounts of calculations in parallel the algorithm is legit but so far the biggest number ever factored is [Music] 21 even IBM state-of-the-art Q system one fails when trying to factor the number 35 however just recently the Chinese factored this big ass number with a quantum computer but it uses a different algorithm that doesn't scale very well for large numbers unlike Shores algorithm everything is safe for now but when someone figures out how to make quantum computers work expect all hell to break loose in the cyber security world at the beginning of this video I mentioned the marching cubes algorithm but it deserves a closer look so first we start with a 3D scalar field which might represent data from an MRI machine each point in the 3D space is represented by a single number or scaler the algorithm starts with a single point then takes its eight neighboring locations to form an imaginary Cube but treats the values as a bit in an 8bit integer this results in 256 different possibilities which point to a pre-calculated array of polygons the algorithm marches through each point to create a 3D mesh that can be used in 3D software and at the time this was really cool because MRI machines produce slices of data that can now be rendered in 3D in modern times though we're often dealing with distributed systems in the cloud and that brings us to the Byzantine generals problem imagine you're a general in the Byzantine Army you're camped around a city with a few other generals with plans to attack attack at the next morning but what if one of the generals gets drunk and wakes up to hung over to attack the entire system could collapse computers have the same problem sometimes they might fail or be infiltrated by hackers and you never know when or where that's going to happen luckily algorithms like pbft are designed to solve this they can keep a distributed Network working properly even if up to onethird of its nodes go Haywire it works by having a node broadcast a pre-prepare message to other nodes indicating its Readiness to execute some code that will change the system the other nodes will respond back an agreement then after a certain threshold a consensus is formed once there's a consensus the original node sends back a commit message to all the other nodes which can then all execute the changes making the entire state of the system consistent algorithms like this are essential for blockchain technology and things like distributed Cloud databases what's really cool about algorithms though is that they can also reflect nature like Boyd's artificial Life program it was created back in ' 86 and simulates the flocking behavior of birds what's so cool about it is that it demonstrates the emerging complexity or beauty that we get out of just a few simple rules in this case the birds have three rules they steer to avoid crowding they steer towards the average heading of the flock and they steer towards the center of mass of their local flock mates the end result are these intricate patterns that weren't programmed directly but just emerge naturally but finally that brings us to an old algorithm that blew my mind just the other day and inspired this video boy or more string search it's weird because it becomes faster and more efficient as the string it's searching becomes bigger that seems impossible but it makes sense when you understand the algorithm it scans text from right to left then has two rules when it encounters a bad character not found in the search pattern it jumps past it based on an estimation made in a pre-processed table likewise if it finds a partial match then a mismatch occurs it has a separate pre-calculated table that maximizes the number of characters it can safely skip these rules are called horis STS which are like functions that are not guaranteed to be perfect but are far more practical than looping over every single character in this case the algorithm gets faster with more text because it's able to to skip a higher proportion of characters and if you've ever wondered why grep is so fast you have this algorithm to thank

Channel: Fireship

Views: 1,163,746

Keywords: webdev, app development, lesson, tutorial

Id: SmyPTnlqhlk

Length: 9min 5sec (545 seconds)

Published: Thu Dec 21 2023