Course Info.

Basic Data Structures.

• Array, vector, and linked list [slides] [video (English)] [video (Chinese)].

• Binary search [slides] [video (English)] [video (Chinese)].

• Skip list [slides] [video (English)] [video (Chinese)].

Sorting.

• Insertion sort [slides] [video (English)].

• Bubble sort [slides].

• Merge sort [slides].

• Quick sort [slides].

• Quick select [slides].

Divide and Conquer.

• Master theorem [slides].

Matrix Data Structure and Algorithms.

• Addition and multiplication [slides] [video (English)] [video (Chinese)].

• Dense matrix data structures [slides] [video (English)] [video (Chinese)].

• Sparse matrix data structures [slides]

• Fast matrix multiplication and Strassen algorithm [slides].

Binary Trees.

• Tree basics [slides] [video (English)].

• Binary search tree: search and insertion [slides].

• Binary search tree: traversal [slides].

• Binary search tree: deletion [slides].

Balanced Trees.

Priority Queues.

• Priority queues [slides].

• Binary heaps [slides].

Disjoint Sets.

• Disjoint sets [slides].

Graph Basics.

• Graph data structures [slides] [video (Chinese)].

• Topological sort [slides].

Shortest Paths.

• Shortest path problem [slides] [video (Chinese)].

• Single-source shortest path in unweighted graphs [slides] [video (Chinese)].

• Single-source shortest path in weighted graphs [slides] [video (Chinese)].

Minimum Spanning Trees.

• Spanning trees [slides] [video (Chinese)].

• Prim's algorithm [slides] [video (Chinese)].

• Kruskal's algorithm [slides] [video (Chinese)].

Network Flow Problems.

• Maximum flow problem [slides] [video (Chinese)].

• Ford-Fulkerson algorithm [slides] [video (Chinese)].

• Edmonds–Karp algorithm [slides] [video (Chinese)].

• Dinic's algorithm [slides] [video (Chinese)].

• Max-flow and min-cut [slides] [video (Chinese)].

Bipartite Graphs.

• Testing bipartiteness [slides] [video (Chinese)].

• Maximum cardinality bipartite matching [slides] [video (Chinese)].

• Maximum weight bipartite matching [slides] [video (Chinese)].

• Hungarian algorithm [slides] [video (Chinese)].

• Stable marriage problem [slides] [video (Chinese)].

• Gale-Shapley algorithm [slides] [video (Chinese)].

Dynamic Programming.

• Fibonacci numbers [slides].

• Climbing stairs [slides].

• Longest common substring [slides].

• Edit distance [slides].

• Combinations of coins [slides].

• Knapsack [slides].

Strings.

• Tries. [slides].

• KMP algorithm. [slides-1] [slides-2].

Randomized Algorithms.

• Monte Carlo algorithms [slides] [video (English)] [video (Chinese)].

• Concentration inequalities [slides].

• Pseudo random number generators.

• Random shuffling [slides] [video (English)] [video (Chinese)].

• Fingerprinting.

Hashing.

• Hash table [slides].

• Collision-resistant hash [slides].

• Locality sensitive hashing [slides].

Cryptographic Algorithms.

• RSA algorithm [slides].

• Digital signature [slides].

• Homomorphic encryption [slides].

Crypto Currency.

• Decentralized payment system [slides].

• Blockchain [slides].

• Merkel tree [slides].

Backtracking.

• Turnpike reconstruction [slides].

• Eight queens problem [slides].

• Hamiltonian cycle [slides].