Data Structures and Algorithms

Binary search tree: indexing for faster search
B+ tree: read optimized
LSM tree: fast write, decent read, larger memory; Copy-on-write B tree plus buffering

Trees

Trie

aka digital tree, prefix tree

Trie - Wikiwand

Tries - YouTube Building a Trie data structure in Go

How Trie Data Structures Work – Validate User Input with Automated Trie Visualization with Python

Prefix sharing
Alphabet-independent size
Support for advanced search operations
Space optimization with compressed Tries

Binary trees

Binary search tree - Wikiwand
Self-balancing binary search tree - Wikiwand
B-tree - Wikiwand generalized BST, can have >2 children
B+ tree - Wikiwand wide tree where node contains only keys

Log Structured Merge (LSM) Tree

Log-structured merge-tree - Wikiwand
The Secret Sauce Behind NoSQL: LSM Tree - YouTube

optimized for fast write
bloom filter at key lookup on level
B-Tree, used in SQL DB, is optimized for fast write

Bloom Filters

Bloom Filters Explained by Example - YouTube
Bloom Filters - YouTube

return firm no or probably yes
bit array and hash functions

Covariance and Contravariance

Covariance and contravariance (computer science) - Wikiwand C# uses in, out keywords to control variance
c# - Covariance and contravariance in programming languages - Stack Overflow
Covariance and Contravariance - withoutbugs.com
C# : Is Variance (Covariance / Contravariance) another word for Polymorphism? - Stack Overflow

State Machine

reactive-programming#Xstate

Finite-state machine - Wikiwand
Deterministic finite automaton - Wikiwand
Finite State Machines
Chomsky Language Levels - YouTube

Automata & Python - Computerphile - YouTube
Automata & Python (Long Version) - Computerphile - YouTube
Non-Deterministic Automata - Computerphile - YouTube

Ragel State Machine Compiler
State Machines & Tools--Quantum Leaps

SCXML - Wikiwand
State Chart XML (SCXML): State Machine Notation for Control Abstraction
SCXML - Commons SCXML

UML State Chart Autocoding for the Mars Science Laboratory (MSL) Mission, Eddie Benowitz, JPL - YouTube
JPLOpenSource/SCA: JPL Statechart Autocoder Rev. 2

Search results · PyPI
Automat: Self-service finite-state machines for the programmer on the go. — automat documentation
glyph/automat: Self-service finite-state machines for the programmer on the go.

Coding State Machines in C and C++ | Embedded Systems Experts
c - state machines tutorials - Stack Overflow

Greedy Algorithms

Greedy Algorithms Tutorial – Solve Coding Challenges - YouTube

Shortest Distance/Pathfinding

A Comparison of Pathfinding Algorithms - YouTube

Dijkstra's Algorithm - Computerphile - YouTube
Gamedev: In-depth Topics - YouTube Python
pygame_tutorials/examples/pathfinding at master · kidscancode/pygame_tutorials · GitHub
How Dijkstra's Algorithm Works - YouTube

A* Algorithm:

choose a clever heuristic
apply heuristic reweighing
run Dijkstra on the new graph

A* (A Star) Search Algorithm - Computerphile - YouTube
A* ALGORITHM BASICS FOR PATH FINDING & HEURISTICS METHODS : ARTIFICIAL INTELLIGENCE
Introduction to the A* Algorithm
The hidden beauty of the A* algorithm - YouTube
Pathfinding in Unity DOTS! (Insane Speed!!!) - YouTube

Maze Solving - Computerphile - YouTube
mikepound/mazesolving: A variety of algorithms to solve mazes from an input image Python

Easy pathfinding in python [almost without math] - YouTube

How Command & Conquer: Tiberian Sun Solved Pathfinding | War Stories | Ars Technica - YouTube

Sorting

Holy Grail: O(NlogN), in-place, stable

The Sorting Algorithm Olympics - Who is the Fastest of them All - YouTube

Kuvina Saydaki
Explaining EVERY Sorting Algorithm (part 1) - YouTube
Explaining EVERY Sorting Algorithm (part 2) - YouTube
Explaining EVERY Sorting Algorithm: Variants and Hybrids - YouTube
The Perfect Sorting Algorithm?? Block Sort Explained (Wiki Sort, Grail Sort) - YouTube

Hash table

Hashtable Naïveté – CrashedTestDummy
C++ STL 之哈希表 | unordered_map | 「浮生若梦」 - sczyh30's blog
How does C++ STL unordered_map resolve collisions? - Stack Overflow
Class template unordered_map - boost

Random Number Generator

Random number generation - Wikiwand
Diehard tests - Wikiwand
Empirical Testing of Random Number Generators
Birthday problem - Wikiwand

TIFU by using Math.random() — Medium
V8 JavaScript Engine: There's Math.random(), and then there's Math.random()

Perlin noise

Perlin noise - Wikiwand a smoother gradient noise
The Theory of Noise: An Overview of Perlin Noise - YouTube
How to turn a few Numbers into Worlds (Perlin Noise) - YouTube
Understanding Perlin Noise
Mathf.PerlinNoise | Smooth Random Values | Unity Quick Tutorial - YouTube

Compression

Kolmogorov complexity - Wikiwand complexity of data
Berry's Paradox - An Algorithm For Truth - YouTube

compression - How are zlib, gzip and zip related? What do they have in common and how are they different? - Stack Overflow
A Quick Benchmark: Gzip vs. Bzip2 vs. LZMA
Quick Benchmark: Gzip vs Bzip2 vs LZMA vs XZ vs LZ4 vs LZO - CatchChallenger wiki
Comparison of Brotli, Deflate, Zopfli, LZMA, LZHAM and Bzip2 Compression Algorithms PDF, 2015

zlib-ng/zlib-ng: zlib replacement with optimizations for "next generation" systems.

Elegant Compression in Text (The LZ 77 Method) - Computerphile - YouTube
Entropy in Compression - Computerphile - YouTube

How Computers Compress Text: Huffman Coding and Huffman Trees - YouTube

Error Correction

Error Correction - Computerphile - YouTube
Multiple Dimension Error Correction - Computerphile - YouTube
Error Correction & International Book Codes - Computerphile - YouTube

How to send a self-correcting message (Hamming codes) - YouTube
Hamming codes part 2, the elegance of it all - YouTube

Visualization

SORTING
Sorting Algorithms Explained Visually - YouTube

VisuAlgo - visualising data structures and algorithms through animation
Red Blob Games
SIGHT & LIGHT - How to create 2D visibility/shadow effects for your game
Visualizing Algorithms
Algorithm Visualizer source

Sketching

Non-exact (rounded) results is good enough for many scenarios.

Dynamic Programming

an optimization over plain recursion by memoizing results of overlapping sub-problems

Dynamic programming - Wikiwand
Dynamic Programming - GeeksforGeeks
Dynamic Programming - Learn to Solve Algorithmic Problems & Coding Challenges - YouTube (memoized) recursion and tabulation
How to Count Dice Rolls - An Introduction to Dynamic Programming - YouTube
Mastering Dynamic Programming - How to solve any interview problem (Part 1) - YouTube
Solving the subsets problem with dynamic programming - YouTube
What can “The Simpsons” teach us about Dynamic Programming? - YouTube several typical examples

Fibonacci number
Coin change
Knapsack problem
Staircase

Decision Problem (Can)
Combinatorics Problem (How)
Optimization Problem (Best)

Constraint programming

Constraint programming - Wikiwand
Constraint satisfaction problem - Wikiwand

Satisfiability modulo theories - Wikiwand
Z3 Theorem Prover - Wikiwand
Z3Prover/z3: The Z3 Theorem Prover
z3-solver · PyPI
Python: package z3
Home · Z3Prover/z3 Wiki
Programming Z3
Z3: An Efficient SMT Solver | SpringerLink
Programming Z3 - YouTube
Analyzing Programs with Z3 - YouTube

"z3" is actual magic (intermediate) anthony explains #425 - YouTube
F2020 - Intro to Constraint Solving with z3 - YouTube Python 2 sample
Modeling functions with Z3 - YouTube