Sajid3/AdvancedAlgorithms

CS600: Advanced Algorithms

1. Course Info.

2. Basic Data Structures.

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

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

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

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 and sparse matrix data structures [slides] [video (English)] [video (Chinese)].

   • Fast matrix multiplication and Strassen algorithm [slides].

6. Binary Trees.

   • Tree basics [slides] [video].

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

   • Binary search tree: traversal [slides].

   • Binary search tree: deletion [slides].

7. Priority Queues.

   • Priority queues [slides].

   • Binary heaps [slides].

8. Disjoint Sets.

   • Disjoint sets [slides].

9. Graph Basics.

   • Graph data structures [slides].

   • Topological sort [slides].

10. Shortest Paths.

    • Shortest path problem [slides].

    • Single-source shortest path in unweighted graphs [slides].

    • Single-source shortest path in weighted graphs [slides].

11. Minimum Spanning Trees.

    • Spanning trees [slides].

    • Prim's algorithm [slides].

    • Kruskal's algorithm [slides].

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

13. Bipartite Graphs.

    • Testing bipartiteness [slides].

    • Maximum cardinality bipartite matching [slides].

    • Maximum weight bipartite matching [slides].

    • Stable marriage problem [slides].

14. Dynamic Programming.

    • Fibonacci numbers [slides].

    • Climbing stairs [slides].

    • Longest common substring [slides].

    • Edit distance [slides].

    • Combinations of coins [slides].

    • Knapsack [slides].

15. Strings.

    • Tries. [slides].

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

16. Randomized Algorithms.

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

    • Concentration inequalities [slides].

    • Pseudo random number generators.

    • Random shuffling [slides].

    • Fingerprinting.

17. Hashing.

    • Hash table [slides].

    • Collision-resistant hash [slides].

    • Locality sensitive hashing [slides].

18. Cryptographic Algorithms.

    • RSA algorithm [slides].

    • Digital signature [slides].

    • Homomorphic encryption [slides].

19. Crypto Currency.

    • Decentralized payment system [slides].

    • Blockchain [slides].

    • Merkel tree [slides].