CS600: Advanced Algorithms

1. Course Info.

2. Basic Data Structures.

   • Array, vector, and linked list [slides].

   • Binary search [slides].

   • Skip list [slides].

3. Sorting.

   • Bubble sort [slides].

   • Insertion 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].

   • Dense and sparse matrix data structures [slides].

   • Fast matrix multiplication and Strassen algorithm [slides].

6. Binary Trees.

   • Tree basics [slides].

   • Binary search tree [slides-1] [slides-2].

7. Priority Queues.

   • Priority queues [slides].

   • Binary heaps [slides].

8. Disjoint Sets.

   • Disjoint sets [slides].

9. Graph Basics.

   • Graph data structures [slides].

   • Single-source shortest paths [slides-1] [slides-2] [slides-3].

   • Minimum spanning trees [slides-1] [slides-2] [slides-3].

10. Network Flow Problems.

    • Maximum flow problem [slides].

    • Ford-Fulkerson algorithm and Edmonds–Karp algorithm [slides].

    • Dinic's algorithm [slides].

    • Max-flow and min-cut [slides].

11. Bipartite Graphs.

    • Testing bipartiteness [slides].

    • Maximum cardinality bipartite matching [slides].

    • Maximum weight bipartite matching [slides].

    • Stable marriage problem [slides].

12. Dynamic Programming.

    • Fibonacci numbers.

    • Climbing stairs.

    • Longest common substring.

    • Edit distance.

    • Combinations of coins.

    • Knapsack.

13. Strings.

    • Tries.

    • KMP algorithm.

14. Randomized Algorithms.

    • Monte Carlo algorithms.

    • Concentration inequalities.

    • Pseudo random number generators.

    • Random shuffling.

    • Fingerprinting.

15. Hashing.

    • Hash table.

    • Collision-resistant hash.

    • Locality sensitive hashing.

16. Cryptographic Algorithms.

    • RSA algorithm.

    • Digital signature.

    • Homomorphic encryption.

17. Blockchain.