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 structure and finish off the video with a discussion of what types of interesting problems you can ask about graphs to help motivate the ideas in future videos. 

Typo correction: at 5:12 the vertex set V should be {0, 1, 2, 3, 4} instead of {0, 1, 2, 3, 4, 5} (there is no vertex 5). 

Big thanks to Dániel László Bertalan for making the closed captions for this video!

The sudoku example was inspired by this incredible reddit visualization: https://www.reddit.com/r/dataisbeautiful/comments/6ty4vf/visualizing_the_sudoku_connectivity_graph_more_in/

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/Ka...
November by Kai Engel
https://freemusicarchive.org/music/Ka...
Cobweb Morning by Kai Engel
https://freemusicarchive.org/music/Ka...

Introduction to Graph Theory: A Computer Science Perspective

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 to render any implicit function. But what's even more impressive in my opinion is the many clever shifts in perspective that allowed a vague problems such as this one to be transformed into a clear, well-defined, and solvable problem.

0:00 Introduction
3:29 Circles and Ellipses
4:57 Defining the Problem
6:00 A Guessing Game
8:29 Contours around Two Points
10:35 Sampling The Space
12:32 Breaking Down Cases
15:00 A Clever Optimization
17:20 How Marching Squares Works
18:59 Parallel Marching Squares
20:21 How Do Metaballs Work?
24:59 Marching Cubes
25:58 Some Parting Thoughts

References/Additional Resources:
http://jamie-wong.com/2014/08/19/metaballs-and-marching-squares/ - the initial inspiration for the framework of this video, great introduction to metaballs and how they can be rendered using marching squares.

http://www.geisswerks.com/ryan/BLOBS/blobs.html  - great resource on implementing metaballs and some of the physics inspirations behind implicit functions

Original Marching cubes paper: https://www.researchgate.net/publication/202232897_Marching_Cubes_A_High_Resolution_3D_Surface_Construction_Algorithm 

Sebastian Lague Video on Marching Cubes:
https://www.youtube.com/watch?v=M3iI2l0ltbE

Further reading on polynomial approximations of metaball implicit functions:
https://www.researchgate.net/publication/242914163_Data_Structure_for_Soft_Objects

Implementation Help for Marching Cubes
http://paulbourke.net/geometry/implicitsurf/ 

Excellent lecture by Casey Muratori about Marching Cubes: https://www.youtube.com/watch?v=SDS5gLSiLg0&t=978s

https://courses.lumenlearning.com/physics/chapter/19-4-equipotential-lines/ - some of the physics behind equipotential lines in electric fields

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

How Computers Draw Weird Shapes (Marching Squares)

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?

This is the main discussion part. Q&A follows at https://www.youtube.com/watch?v=lcF-HzlFYKE .

Discussion: Making Programming Language Parsers, etc (Q&A is in separate video).

A follow up to https://www.youtube.com/watch?v=QM1iUe6IofM

Object-Oriented Programming is Embarrassing: 4 Short Examples

A little exploration of some of the fundamentals of how computers work. Logic gates, binary, two's complement; all that good stuff!

The simulation tool is now available for download!
You can find it here: https://sebastian.itch.io/digital-logic-sim
Along with source code over here: https://github.com/SebLague/Digital-Logic-Sim

If you'd like to support the creation of more videos (and get early access to new content), I'd greatly appreciate your support here: https://www.patreon.com/SebastianLague

See the full playlist here: https://www.youtube.com/playlist?list=PLFt_AvWsXl0dPhqVsKt1Ni_46ARyiCGSq

Resources and Inspiration:
https://www.youtube.com/c/BenEater
https://www.coursera.org/learn/build-a-computer
https://en.wikipedia.org/wiki/Two%27s_complement

Chapters:
00:00 Intro
00:50 Logic Gates
03:09 The Simulation
05:06 Binary Numeral System
06:16 Binary Addition Theory
07:24 Building an Adder
12:11 Negative Numbers Theory
15:08 Building the ALU
17:43 Outro

Music:
"A Quiet Place" by Jordan White
"A New Perspective" by Ryan Smart
"Beyond the Horizon" by Sounds Like Sander
"Crystal Bursts" by Cody Martin
"Air" by Assaf Ayalon
"Elastic Vibe" by Ziv Moran
"Gotcha!" by Avocado Junkie

Images:
https://en.wikipedia.org/wiki/Vacuum_tube#/media/File:8863-Project-Whirlwind-CRMI.JPG

Exploring How Computers Work

Welcome to the first part in a series teaching pathfinding for video games. In this episode we take a look at the A* algorithm and how it works.

Some great A* learning resources:
http://theory.stanford.edu/~amitp/GameProgramming/
http://www.policyalmanac.org/games/aStarTutorial.htm

Source code: https://github.com/SebLague/Pathfinding

If you'd like to support the creation of more programming videos, I'd greatly appreciate your support on patreon:
https://www.patreon.com/SebastianLague

Background music is 32. The Hidden Path by longzijun.

A* Pathfinding (E01: algorithm explanation)

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 video is that polynomial multiplication can be improved significantly by multiplying polynomials in a special value representation. The challenge that presents itself is the problem of converting a polynomial from a standard coefficient representation to value representation. 

We see that the FFT is an incredibly efficient recursive algorithm that performs this task, and we also discover that a slightly tweaked FFT (Inverse FFT) can also solve the reverse problem of interpolation. If this video doesn't blow your mind, I don't know what will. 

0:00 Introduction
2:19 Polynomial Multiplication
3:36 Polynomial Representation
6:06 Value Representation Advantages
7:07 Polynomial Multiplication Flowchart
8:04 Polynomial Evaluation
13:49 Which Evaluation Points?
16:30 Why Nth Roots of Unity?
18:28 FFT Implementation
22:47 Interpolation and Inverse FFT
26:49 Recap

Also a subtle mistake that a commenter made me aware of -- at 26:40 instead of replacing w with (1/n * e^{-2 * pi i/ n}), the actual right way to do this is by taking the final output of the IFFT at the end of the recursion and dividing by n. 

So the full change is w = e^{-2 pi i / n} 
And then somewhere outside the scope of the IFFT function ifft_result = 1/n * IFFT(values)

The treatment of the FFT in this video is inspired by several well known references, mainly Introduction to Algorithms (Cormen et al.) and Algorithms (Papadimitriou et al.).

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

Elegant proof that the matrix used in the proof that (d + 1) points uniquely define a degree d polynomial is invertible: https://math.stackexchange.com/questions/426932/why-are-vandermonde-matrices-invertible

Music:
Lift Motif by Kevin MacLeod is licensed under a Creative Commons Attribution license (https://creativecommons.org/licenses/...)
Source: http://incompetech.com/music/royalty-...
Artist: http://incompetech.com/

All other music by Aakash Gandhi

SVG Attributions:
Earth: Designed by Flat Icons from www.flaticon.com, CC BY 4.0 https://creativecommons.org/licenses/by/4.0, via Wikimedia Commons
GPS: Icons made by https://www.flaticon.com/authors/pause08 from https://www.flaticon.com/
Wireless Comms: Design inspired by https://svgsilh.com/image/297434.html