Reducible

In this video, we take a look at one of the more challenging computer science concepts: Recursion. We introduce 5 simple steps to help you solve challenging recursive problems and show you 3 specific examples, each progressively more difficult than the last.

Support: https://www.patreon.com/reducible

This video wouldn't be possible without the open source manim library created by 3blue1brown: https://github.com/3b1b/manim

Here is link to the repository that contains the code used to generate the animations in this video: https://github.com/nipunramk/Reducible

Music: 
October by Kai Engel https://freemusicarchive.org/music/Kai_Engel/Chapter_Four__Fall/Kai_Engel_-_Chapter_Four_-_Fall_-_05_October
November by Kai Engel
https://freemusicarchive.org/music/Kai_Engel/Chapter_Four__Fall/Kai_Engel_-_Chapter_Four_-_Fall_-_08_November
Cobweb Morning by Kai Engel
https://freemusicarchive.org/music/Kai_Engel/Chapter_Four__Fall/Kai_Engel_-_Chapter_Four_-_Fall_-_04_Cobweb_Morning

5 Simple Steps for Solving Any Recursive Problem

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

The video covers a broad range of topics from Minkowski sums and differences to support functions to the full implementation of the 2D GJK algorithm. But what I hope you get out of this is an appreciation of the incredible shifts in perspective that lead to the final algorithm. Coming up with the algorithm is an amazing feat and useful for specific applications, but the overarching problem solving techniques that come through in the journey to the solution is truly invaluable. 

0:00 Introducing the Problem
2:02 Convexity
3:15 Infinite Point Perspective
4:07 Minkowski Sums and Differences
6:37 Triangles inside Minkowski Differences
7:41 Simplexes
8:57 Support Functions
13:05 Core GJK Algorithm: Broad Perspective
17:15 Remaining Key Questions
17:56 How to determine if a point passed the origin?
19:10 The line case
20:41 The triangle case
26:25 GJK Implementation
29:38 Recap and quick note about original GJK paper

This video is supported by a community of Patreons
Special Thanks to the following Patreons:
Burt Humburg
Justin Hiester
Michael Nawenstein
Richard Wells
Sebastian Gamboa
Zac Landis

There's a lot more to the GJK algorithm to learn for those interested. Here are some resources I recommend:
https://www.youtube.com/watch?v=Qupqu1xe7Io - a full walkthrough of how to implement GJK in 3D by Casey Muratori, the game developer/engineer that came up with some of the clever optimizations that I present in this video.
http://www.dyn4j.org/2010/04/gjk-gilbert-johnson-keerthi/ - a really nice writeup on GJK
https://www.youtube.com/watch?v=MDusDn8oTSE - A quick intro to GJK and an implementation in C++
https://www.toptal.com/game/video-game-physics-part-ii-collision-detection-for-solid-objects - solid resource for collision detection in general and goes deeper into the theory.
https://box2d.org/files/ErinCatto_GJK_GDC2010.pdf - an alternative perspective to GJK using barycentric coordinates -- I really wanted to cover this in this video, but it would have been an hour long instead of half an hour long so I'll compromise and give you this resource :)

Support: https://www.patreon.com/reducible
Twitter: https://twitter.com/Reducible20

This video wouldn't be possible without the open source library manim created by 3blue1brown: https://github.com/3b1b/manim

Here is link to the repository that contains the code used to generate the animations in this video: https://github.com/nipunramk/Reducible

Music attributions:
Midsummer Sky by Kevin MacLeod is licensed under a Creative Commons Attribution 4.0 license. https://creativecommons.org/licenses/by/4.0/
Source: http://incompetech.com/music/royalty-free/index.html?isrc=USUAN1100158
Artist: http://incompetech.com/
Luminous Rain by Kevin MacLeod is licensed under a Creative Commons Attribution 4.0 license. https://creativecommons.org/licenses/by/4.0/
Source: http://incompetech.com/music/royalty-free/index.html?isrc=USUAN1100169
Artist: http://incompetech.com/
Prelude No. 23 by Chris Zabriskie is licensed under a Creative Commons Attribution 4.0 license. https://creativecommons.org/licenses/by/4.0/
Source: http://chriszabriskie.com/preludes/
Artist: http://chriszabriskie.com/
All other tracks by Aakash Gandhi

A Strange But Elegant Approach to a Surprisingly Hard Problem (GJK Algorithm)

In this video, we take a look at Big O notation. We go through how Big O notation came about and why it's so useful as a method of measuring efficiency of algorithms. We then go through some examples of you can find the Big O runtime of various algorithms. 

Support: https://www.patreon.com/reducible

This video wouldn't be possible without the open source manim library created by 3blue1brown: https://github.com/3b1b/manim

Here is link to the repository that contains the code used to generate the animations in this video: https://github.com/nipunramk/Reducible

Music: 
October by Kai Engel https://freemusicarchive.org/music/Kai_Engel/Chapter_Four__Fall/Kai_Engel_-_Chapter_Four_-_Fall_-_05_October
November by Kai Engel
https://freemusicarchive.org/music/Kai_Engel/Chapter_Four__Fall/Kai_Engel_-_Chapter_Four_-_Fall_-_08_November
Cobweb Morning by Kai Engel
https://freemusicarchive.org/music/Kai_Engel/Chapter_Four__Fall/Kai_Engel_-_Chapter_Four_-_Fall_-_04_Cobweb_Morning

What Is Big O Notation?

Visit  https://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 Encoding/Decoding
23:04 The Compromise: PNG Is Slow
23:31 Quite OK Image (QOI) Format
28:26 Benchmark Results
29:27 Final Thoughts
30:36 Brilliant Sponsorship

Developed in the mid 1990's, the PNG encoding standard for images is now the most used image format on the web. One aspect that makes PNG quite attractive for users is image quality is perfectly preserved as a result of lossless compression. In this video, we dive into how exactly PNG is able to compress images so well, while also retaining all the information in the image. 

One thing we discover during this journey is how slow PNG is in practice. Towards the end, we discuss a relatively new image format called QOI that is somewhat comparable to PNG, but 20-50x faster. But what's perhaps the most remarkable aspect of QOI is how a simple set of rules lead to surprisingly good compression on a variety of images. 

Animations created jointly by Nipun Ramakrishnan and Jesús Rascón.

*Minor error in QOI section: QOI_DIFF_SMALL should have a tag of 01 not 10 (QOI_DIFF_MED has the tag 10.*

References:
PNG Specification: https://www.w3.org/TR/PNG/#9Filters and http://www.libpng.org/pub/png/spec/1.2/png-1.2.pdf

A nice interactive guide to LZSS: https://go-compression.github.io/algorithms/lzss/

A definitive guide to all the details we didn't have time to talk about with respect to PNG: http://www.libpng.org/pub/png/book/chapter08.html

A deep dive into all the details of DEFLATE: https://www.youtube.com/watch?v=oi2lMBBjQ8s&ab_channel=BillBird

Initial blog post introducing QOI: https://phoboslab.org/log/2021/11/qoi-fast-lossless-image-compression

Data on Image File Format Usage across Websites: https://w3techs.com/technologies/overview/image_format

QOI Specification: https://qoiformat.org/qoi-specification.pdf

QOI Source Code/Benchmark Results https://qoiformat.org/: 

This video wouldn't be possible without the open source library manim created by 3blue1brown and maintained by Manim Community.
The Manim Community Developers. (2022). Manim – Mathematical Animation Framework (Version v0.11.0) [Computer software]. https://www.manim.community/

Here is link to the repository that contains the code used to generate the animations in this video: https://github.com/nipunramk/Reducible

Music in this video comes from Jesús Rascón, Aaskash Gandhi, and Myuu.

Socials:
Patreon: https://www.patreon.com/reducible
Twitter: https://twitter.com/Reducible20

Big thanks to the community of Patreons that support this channel. Special thanks to the following Patreons:
Andreas
Adam Dřínek
Burt Humburg
Matt Q
Winston Durand
Andjela Arsic
Mutual Information
Richard Wells
Sebastian Gamboa
Zac Landis

How PNG Works: Compromising Speed for Quality

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 subproblems
4. Generalize the relationship
5. Implement by solving subproblems in order

After taking an in depth look at these problems, at the end of the video we will also have a discussion about common subproblems that you may encounter while solving dynamic programming problems.

Error correction: for the box problem, using dictionary solutions only works if we are given unique boxes -- using a list of subproblems would be a better way to solve it if we wanted to handle duplicate boxes (similar to how we did the longest increasing subsequence). 

Support: https://www.patreon.com/reducible

This video wouldn't be possible without the open source manim library created by 3blue1brown: https://github.com/3b1b/manim

Here is link to the repository that contains the code used to generate the animations in this video: https://github.com/nipunramk/Reducible

Music:
Prelude No. 2 by Chris Zabriskie is licensed under a Creative Commons Attribution license (https://creativecommons.org/licenses/by/4.0/)
Source: http://chriszabriskie.com/preludes/
Artist: http://chriszabriskie.com/

All other music by Aakash Gandhi

5 Simple Steps for Solving Dynamic Programming Problems

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 context of some simple simulations of a small number of particles, but scaling up these simulations is another challenge entirely. We present big ideas in broad phase optimization schemes for speeding up collision detection including the sweep and prune algorithm, uniform grids, K-D trees, and bounding volume hierarchies. 

0:00 Introduction
1:25 Intro to Animation
2:46 Discrete Collision Detection and Response
5:50 Implementation
6:50 Discrete Collision Detection Limitations
8:10 Continuous Collision Detection
11:42 Two Particle Simulations
13:13 Scaling Up Simulations
15:42 Sweep and Prune Algorithm
19:05 Uniform Grid Space Partitioning
20:43 KD Trees
23:51 Bounding Volume Hierarchies
27:12 Recap

Correction: At 9:02, the linear interpolation equations should be x(t) = t * x(1) + (1 - t) * x(0) and y(t) = t * y(1) + (1 - t) * y(0). All subsequent derivations have the x(0) switched with x(1). All y(0) should also be switched with y(1) for the same reason.

Post-correction 2: I ran the experiment with the naive solution of checking every pair of particles  with an added inefficiency in rendering the animations so the comparison wasn't fair and that's why the number was so high. The actual speed up is still fairly significant, but not THAT significant.

Minor correction: p.vel is updated and used in the next line at 6:28, p.vel and p.pos should be updated simultaneously

This video is supported by a community of Patreons
Special Thanks to the following Patreons:
Burt Humburg
Justin Hiester
Michael Nawenstein
Richard Wells
Zac Landis

Support: https://www.patreon.com/reducible
Twitter: https://twitter.com/Reducible20

This video wouldn't be possible without the open source library manim created by 3blue1brown: https://github.com/3b1b/manim

Here is link to the repository that contains the code used to generate the animations in this video: https://github.com/nipunramk/Reducible

2D Collision Response Vector Equation Derivation Walkthrough: https://www.vobarian.com/collisions/2dcollisions2.pdf 

Bounding Volume Hierarchy Traversal Algorithm for Broad Phase: https://thegeneralsolution.wordpress.com/2011/12/13/broad-phase-collision-detection-bounding-volume-hierarchies-1/

The ideas and presentation in this video were inspired by a culmination of resources -- here are some that I found particularly nice for further exploration:
https://www.toptal.com/game/video-game-physics-part-ii-collision-detection-for-solid-objects
Game Physics Engine Development by Ian Millington Ch. 12
https://github.com/mattleibow/jitterphysics/wiki/Sweep-and-Prune
http://www.mcihanozer.com/tips/computer-graphics/collision-detection-related/uniform-grid-based/

Building Collision Simulations: An Introduction to Computer Graphics

Visit  https://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 Cosine Transform (DCT)
11:32 Sampling cosine waves
12:43 Playing around with the DCT
17:38 Mathematically defining the DCT
21:02 The Inverse DCT
22:45 The 2D DCT
23:49 Visualizing the 2D DCT
24:35 Introducing Energy Compaction
26:05 Brilliant Sponsorship
27:23 Building an image from the 2D DCT
28:20 Quantization
30:23 Run-length/Huffman Encoding within JPEG
32:56 How JPEG fits into the big picture of data compression

The JPEG algorithm is rather complex and in this video, we break down the core parts of the algorithm, specifically color spaces, YCbCr, chroma subsampling, the discrete cosine transform, quantization, and lossless encoding. The majority of the focus is on the mathematical and signal processing insights that lead to advancements in image compression and the big themes in compression as a whole that we can take away from it. 

Animations created jointly by Nipun Ramakrishnan and Jesús Rascón.

References/Additional Resources:
https://www.red.com/red-101/video-chroma-subsampling - great resource on different types of chroma subsampling

http://weitz.de/dct/ - play around with the DCT

https://www.cse.iitd.ac.in/~pkalra/col783-2017/DCT-History.pdf - paper referenced in video

http://www.ee.ic.ac.uk/hp/staff/dmb/courses/DSPDF/00300_Transforms.pdf - a more rigorous signal processing approach to the DCT

https://www.impulseadventure.com/photo/jpeg-huffman-coding.html - great landing point for learning more about how huffman codes work in the context of JPEG

https://www.youtube.com/watch?v=CPT4FSkFUgs&list=PLpsTn9TA_Q8VMDyOPrDKmSJYt1DLgDZU4&ab_channel=DanielHarding - a great playlist I recommend that dives deep into actually implementing a JPEG decoder

This video wouldn't be possible without the open source library manim created by 3blue1brown and maintained by Manim Community.
The Manim Community Developers. (2021). Manim – Mathematical Animation Framework (Version v0.11.0) [Computer software]. https://www.manim.community/

Here is link to the repository that contains the code used to generate the animations in this video: https://github.com/nipunramk/Reducible

All music in the video is from Aakash Gandhi

The Unreasonable Effectiveness of JPEG: A Signal Processing Approach

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 between a preorder and post order DFS traversal. We then finish the video off with some practical and fun applications of depth first search in graph theory.

0:00 Intro and Preview
0:50  Graph Traversal
1:20 DFS Walkthrough and Examples
6:26 Recursive Implementation
11:08 Iterative Implementation
15:06 Preorder vs Postorder DFS
17:01 DFS Applications

Support: https://www.patreon.com/reducible

This video wouldn't be possible without the open source manim library created by 3blue1brown: https://github.com/3b1b/manim

Here is link to the repository that contains the code used to generate the animations in this video: https://github.com/nipunramk/Reducible