CS600: Advanced Algorithms

1. Course Info.

2. 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)].

3. Sorting.

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

   • Bubble sort [slides].

   • Merge sort [slides].

   • Quick sort [slides].

   • Quick select [slides].

4. Divide and Conquer.

   • Master theorem [slides].

5. 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].

6. Binary Trees.

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

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

   • Binary search tree: traversal [slides].

   • Binary search tree: deletion [slides].

7. Balanced Trees.

8. Priority Queues.

   • Priority queues [slides].

   • Binary heaps [slides].

9. Disjoint Sets.

   • Disjoint sets [slides].

10. Graph Basics.

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

    • Topological sort [slides].

11. 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)].

12. Minimum Spanning Trees.

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

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

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

13. 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)].

14. 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)].

15. Dynamic Programming.

    • Fibonacci numbers [slides].

    • Climbing stairs [slides].

    • Longest common substring [slides].

    • Edit distance [slides].

    • Combinations of coins [slides].

    • Knapsack [slides].

16. Strings.

    • Tries. [slides].

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

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

18. Hashing.

    • Hash table [slides].

    • Collision-resistant hash [slides].

    • Locality sensitive hashing [slides].

19. Cryptographic Algorithms.

    • RSA algorithm [slides].

    • Digital signature [slides].

    • Homomorphic encryption [slides].

20. Crypto Currency.

    • Decentralized payment system [slides].

    • Blockchain [slides].

    • Merkel tree [slides].

21. Backtracking.

    • Turnpike reconstruction [slides].

    • Eight queens problem [slides].

    • Hamiltonian cycle [slides].