Reducible
Reducible
  • Видео 22
  • Просмотров 9 931 484
The Discrete Fourier Transform: Most Important Algorithm Ever?
Go to nordvpn.com/reducible to get the two year plan with an exclusive deal PLUS 1 bonus month free! It’s risk free with NordVPN’s 30 day money back guarantee!
The Discrete Fourier Transform (DFT) is one of the most essential algorithms that power modern society. In this video, we go through a discovery-oriented approach to deriving the core ideas of the DFT.
We start by defining ideal conditions and properties of our transform. We define a similarity measure and come up with an idea that the transform we are looking for is fundamentally a matrix multiplication. Within the context of simple cosine waves, we develop an initial version of our transform using cosine wave analysis frequencies ...
Просмотров: 108 377

Видео

The Traveling Salesman Problem: When Good Enough Beats Perfect
Просмотров 261 тыс.Год назад
Use the code "reducible" to get CuriosityStream for less than $15 a year! curiositystream.com/reducible The Traveling Salesman Problem (TSP) is one of the most notorious problems in all of computer science. In this video, we dive into why the problem presents such a challenge for computer scientists and some of the clever methods used to solve the problem. We start with showing why all brute fo...
PageRank: A Trillion Dollar Algorithm
Просмотров 159 тыс.2 года назад
Visit brilliant.org/Reducible/ to get started learning STEM for free, and the first 200 people will get 20% off their annual premium subscription. Chapters: 0:00 Intro 1:00 Defining Markov Chains 2:00 Introducing the Problem 4:08 Modeling Markov Chains 6:26 Stationary Distributions 7:20 Uniqueness of Stationary Distributions (Irreducibility) 9:11 Convergence of Stationary Distributions (Periodi...
How PNG Works: Compromising Speed for Quality
Просмотров 627 тыс.2 года назад
Visit brilliant.org/Reducible/ to get started learning STEM for free, and the first 200 people will get 20% off their annual premium subscription. Chapters: 0:00 Introduction 1:35 Exploiting redundancy 2:09 Huffman Codes 4:22 Run Length Encoding 5:23 Lempel-Ziv Schemes (LZSS) 13:50 Transforming the problem 14:36 Filtering 17:46 How PNG Picks Filters 18:58 Heuristics for Filtering 21:06 PNG Enco...
The Unreasonable Effectiveness of JPEG: A Signal Processing Approach
Просмотров 1,1 млн2 года назад
Visit brilliant.org/Reducible/ to get started learning STEM for free, and the first 200 people will get 20% off their annual premium subscription. Chapters: 00:00 Introducing JPEG and RGB Representation 2:15 Lossy Compression 3:41 What information can we get rid of? 4:36 Introducing YCbCr 6:10 Chroma subsampling/downsampling 8:10 Images represented as signals 9:52 Introducing the Discrete Cosin...
How Computers Draw Weird Shapes (Marching Squares)
Просмотров 407 тыс.2 года назад
In this video, we start with an interesting animation of blobby objects which we introduce as metaballs. There's a lot of surprisingly intricate ideas behind making these objects render on a screen. We'll see how folks in computer graphics attempted to solve this problem through a really elegant algorithm called marching squares. Marching squares is a really powerful algorithm that allows you t...
Huffman Codes: An Information Theory Perspective
Просмотров 223 тыс.2 года назад
Huffman Codes are one of the most important discoveries in the field of data compression. When you first see them, they almost feel obvious in hindsight, mainly due to how simple and elegant the algorithm ends up being. But there's an underlying story of how they were discovered by Huffman and how he built the idea from early ideas in information theory that is often missed. This video is all a...
A Strange But Elegant Approach to a Surprisingly Hard Problem (GJK Algorithm)
Просмотров 333 тыс.3 года назад
In 1988, three engineers came together and developed one of the most clever solutions to the problem of detecting when two complex objects collide. Their solution, the Gilbert Johnson Keerthi (GJK) algorithm, named after the authors, made an incredible impact in the fields of robotics, control, and computer graphics. This video is about understanding this ingenious algorithm from first principl...
Building Collision Simulations: An Introduction to Computer Graphics
Просмотров 462 тыс.3 года назад
Collision detection systems show up in all sorts of video games and simulations. But how do you actually build these systems? Turns out that the key ideas behind these systems show up all over a field of computer science called computer graphics. We start off with the basics of animation and then branch off into ideas in discrete and continuous collision detection. We break them down in the con...
FFT Example: Unraveling the Recursion
Просмотров 81 тыс.3 года назад
This video is meant as further support to the main video on the FFT ruclips.net/video/h7apO7q16V0/видео.html We break down how the FFT evaluates a particular polynomial at the roots of unity by unraveling the recursive process completely. 0:00 Introduction 1:13 FFT Example Breakdown Support: www.patreon.com/reducible This video wouldn't be possible without the open source manim library created ...
The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?
Просмотров 1,9 млн3 года назад
In this video, we take a look at one of the most beautiful algorithms ever created: the Fast Fourier Transform (FFT). This is a tricky algorithm to understand so we take a look at it in a context that we are all familiar with: polynomial multiplication. You will see how the core ideas of the FFT can be "discovered" through asking the right questions. The key insights that are presented in this ...
Breadth First Search (BFS): Visualized and Explained
Просмотров 192 тыс.3 года назад
In this video we break down the BFS algorithm in a visual manner with examples and key intuition. We then show the implementation of the algorithm with code and then finish off the video by demonstrating how you can use the BFS algorithm to solve the Flood Fill problem. 0:00 Introduction 0:45 BFS Intuition/Examples 2:39 BFS Implementation 5:19 Flood Fill Problem Support: www.patreon.com/reducib...
5 Simple Steps for Solving Dynamic Programming Problems
Просмотров 1 млн3 года назад
In this video, we go over five steps that you can use as a framework to solve dynamic programming problems. You will see how these steps are applied to two specific dynamic programming problems: the longest increasing subsequence problem and optimal box stacking. The five steps in order are as follows: 1. Visualize examples 2. Find an appropriate subproblem 3. Find relationships among subproble...
Depth First Search (DFS) Explained: Algorithm, Examples, and Code
Просмотров 372 тыс.3 года назад
In this video, I explain the fundamental ideas behind the Depth First Search (DFS) graph algorithm. We first introduce the concept of a graph traversal. We then go through several examples of DFS to provide intuition. Afterwards, we then go through both a recursive and iterative implementation with provided code. We discuss the differences between the implementation and also make a distinction ...
Introduction to Graph Theory: A Computer Science Perspective
Просмотров 547 тыс.4 года назад
In this video, I introduce the field of graph theory. We first answer the important question of why someone should even care about studying graph theory through an application perspective. Afterwards, we introduce definitions and essential terminology in graph theory, followed by a discussion of the types of graphs you may encounter. We then define several ways to represent graphs as a data str...
Towers of Hanoi: A Complete Recursive Visualization
Просмотров 445 тыс.4 года назад
Towers of Hanoi: A Complete Recursive Visualization
What Is Big O Notation?
Просмотров 311 тыс.4 года назад
What Is Big O Notation?
5 Simple Steps for Solving Any Recursive Problem
Просмотров 1,2 млн4 года назад
5 Simple Steps for Solving Any Recursive Problem
The Simple and Elegant Idea behind Efficient Dynamic Arrays
Просмотров 58 тыс.4 года назад
The Simple and Elegant Idea behind Efficient Dynamic Arrays
What if you had to invent a dynamic array?
Просмотров 139 тыс.4 года назад
What if you had to invent a dynamic array?
What Actually Is a Data Structure?
Просмотров 27 тыс.4 года назад
What Actually Is a Data Structure?
A Preview for Data Structures and Algorithms
Просмотров 23 тыс.4 года назад
A Preview for Data Structures and Algorithms

Комментарии

  • @meenalrawlani623
    @meenalrawlani623 8 часов назад

    i am gonna throw up, how was i supposed to come up with the last bit of logic in the last problem

  • @shibinabraham7819
    @shibinabraham7819 День назад

    Excellent work mate. :)

  • @SubhodeepMondal-uq2gr
    @SubhodeepMondal-uq2gr 2 дня назад

    sign for imaginary components are not matching with numpy.fft.fft() results!

  • @rudrOwO
    @rudrOwO 3 дня назад

    Amazing!

  • @brenofilho3320
    @brenofilho3320 4 дня назад

    kewl

  • @bubisepulturegd4638
    @bubisepulturegd4638 6 дней назад

    I love when algorithm's names have simple words in them such as this one's `fast` or SHA-256's acronym's `secure hash algorithm`. Truly the most ingenious aspect of these algorithms is their names.

  • @JustNow42
    @JustNow42 6 дней назад

    It is so easy, you move the smallest disk every second move in a sequence from 1-2 and 2-3 and 3-1 etc. Very boring. In the other moves there are only one choice to move when you must put the smaller disk on to the larger. That's it. 30 seconds to find out.

  • @JustNow42
    @JustNow42 6 дней назад

    When in high-school I used to spend the time in transit by doing the tower in the head. My record was 8 disks before arriving but it heavily depended on the number of pretty girls that sometimes made it difficult to concentrate.

  • @fernandocelso8332
    @fernandocelso8332 6 дней назад

    What an incredible video, thank you for the content, really well explained! 😁

  • @1matan5
    @1matan5 6 дней назад

    greatly explanied!

  • @swetanksrivastava3159
    @swetanksrivastava3159 7 дней назад

    what does the line y= [0]*n indicate in fft function ?? It is not very clear to me.

  • @shilpavpurushothaman
    @shilpavpurushothaman 7 дней назад

    excellent tutorial

  • @andreabonannibonanni211
    @andreabonannibonanni211 8 дней назад

    great video, thank you!!

  • @TejaaaaaaReddy
    @TejaaaaaaReddy 9 дней назад

    great video! but can you please teach us how to identify if a given problem can be solved by recursion or not?

  • @whatever8011
    @whatever8011 9 дней назад

    90% of the people still doesn't know how to solve this type of the problems.

  • @arihantkumar9383
    @arihantkumar9383 9 дней назад

    is the maze solvable?

  • @user-kv3jd1ln4l
    @user-kv3jd1ln4l 10 дней назад

    thanks for clear explaining

  • @dryyrun
    @dryyrun 11 дней назад

    fantastic video! respect++ just an optimization for the last problem's base case currently, say if I provide n=3 and m=15, it will return this : { 0 (since n<m) + f(n, m-1)} == {0 + f(3, 14)} and f(3,14) will again return {0 + f(3, 13)} and these unnecessary calls will continue untill m==n i.e. untill f(3,3) gets called, so we can add a line: if(n<m) return f(n,m) to reduce time waste and jump to effective function calls

  • @prayagcbose3862
    @prayagcbose3862 11 дней назад

    Best explanation of TOH I've ever heard.

  • @vk8a8
    @vk8a8 12 дней назад

    huh

  • @IOSARBX
    @IOSARBX 13 дней назад

    Reducible, cool video keep up the amazing work

  • @goober3666
    @goober3666 14 дней назад

    this video is oddly beautiful, i absolutely despised this whole semester of discrete math but you kinda got me invested

  • @Monkeymario.
    @Monkeymario. 15 дней назад

    what about webp

  • @kaustubhsonar4613
    @kaustubhsonar4613 15 дней назад

    am i stupid or it is hard?

  • @abhirup619
    @abhirup619 15 дней назад

    best explanantion of this concept and also the most beauiful in any book or video ever!!!!

  • @collinspo
    @collinspo 16 дней назад

    Who else came here after watching Nvidia's CEO talk about the cuOPT (Combinatorial Optimization) library

  • @ianegan
    @ianegan 17 дней назад

    This was a great video...I'm trying to "figure this stuff out" and so when i learned there is a word to describe one of the other issues i had noticed because it was so common (aka tunneling).

  • @holdthelineprod
    @holdthelineprod 17 дней назад

    I learnt a lot with this video. Ive tried my solution of those problem in C++ but there is something i dont know how to handle. With Voloban equation, only the speed vector is changed then the position is changed by another function. It wont make a long time until, when particle A and B collides the algo moves one of them in particle C.... After that we have the opposite effect : Part a (or b) is now glued to part c. I would love to find a way to implement this correctly...

  • @antonkukoba3378
    @antonkukoba3378 17 дней назад

    I got lost at about 15 minutes. Something is really missing in this explanation

  • @yhdzhang
    @yhdzhang 17 дней назад

    What does the DAG look like for the House Robber problem?

  • @luh034
    @luh034 18 дней назад

    I love QOI so much, its such a cool format. And on top of that such a great example of the idiom: "a wise person simplifies the complex whilst a foolish person complicates the simple" (Not to throw shade on the PNG guys, as it's still absolutely mind-boggling how highly it can compress images)

  • @nichan008
    @nichan008 19 дней назад

    Could you do some mathemagics if you knew the 'negative' volume that makes a shape concave when doing the Minkowski sums?

  • @ryanmckenna2047
    @ryanmckenna2047 20 дней назад

    Very nicely introduced, I hope you have some very complex cutting edge applications of graph theory to show off :)

  • @twipps7700
    @twipps7700 20 дней назад

    This video helped my understand my bugs alot better thanks!!

  • @frommarkham424
    @frommarkham424 21 день назад

    u can also solve it using loops

  • @nigel9637
    @nigel9637 21 день назад

    in the last problem shouldnt we also include that count_partitions(n,m) -> 1 if n=0 AND m!=0? (since m is already assumed to be >=0)

  • @kambizmerati1119
    @kambizmerati1119 21 день назад

    It was nt that my mind was nt blown. It was. But I started weeping too! Really cool!

  • @nichan008
    @nichan008 21 день назад

    For finding if point A passed the origin, would it not be simpler to just check the signs of the relevant vector components?

  • @rodrigoqteixeira
    @rodrigoqteixeira 22 дня назад

    I love the way how he discretely changed it to P[::2] and P[1::2] to match python syntax.

  • @rodrigoqteixeira
    @rodrigoqteixeira 22 дня назад

    20:49 unopened brackets when saying to me to check if it is true? Are you kidding me?

  • @ArpitAnand-yd7tr
    @ArpitAnand-yd7tr 22 дня назад

    Can someone please explain how did the multiplication yield those results at 6:31

  • @unveil7762
    @unveil7762 22 дня назад

    Very cool 👌… i will try this volume bounding thingy sound not impossible to code. Thanks!! Also the sweep was really well explained i was using it without fully understand! ❤

  • @Quietlamacakes
    @Quietlamacakes 22 дня назад

    I did this iteratively, fear me.

  • @esomonugift7572
    @esomonugift7572 23 дня назад

    God bless you bro ❤

  • @antoine2571
    @antoine2571 23 дня назад

    Such a shame this video hasn't millions of views. I'm not kidding, we're looking at a masterpiece.

  • @newbie8051
    @newbie8051 24 дня назад

    Holy fuck, I am in awe ! Damn, our prof covered this in a week and I couldn't understand how it really worked so I have to revisit such lectures regularly Thanks

  • @ignore_for_your_sanity
    @ignore_for_your_sanity 24 дня назад

    Imagine bloating matrix representation to 30 minutes and still confusing "people." Covid didn't go far enough curing cancer.

  • @AvoytDesign
    @AvoytDesign 25 дней назад

    "Just because a question is easy to verify doesn't mean it's easy to solve." prove it and you'll win $1M; that's literally the P v NP problem.

  • @tadhailu
    @tadhailu 26 дней назад

    You are so geneous

  • @maxpricefield7586
    @maxpricefield7586 26 дней назад

    @10:32 the succinctness ends here. how is the split up representation having squares in the x's?