# AdvancedAlgorithms **Repository Path**: zgzhang_1005/AdvancedAlgorithms ## Basic Information - **Project Name**: AdvancedAlgorithms - **Description**: No description available - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2024-11-25 - **Last Updated**: 2024-11-25 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # CS600: Advanced Algorithms 1. **Course Info**. 2. **Basic Data Structures**. * Array, vector, and linked list [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/02_Basic_1.pdf)] [[video (English)](https://youtu.be/Ign3VHqNybs)] [[video (Chinese)](https://youtu.be/zxHYm3PqdAE)]. * Binary search [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/02_Basic_2.pdf)] [[video (English)](https://youtu.be/yfHcb1hXt3s)] [[video (Chinese)](https://youtu.be/RH3tZldhjJ0)]. * Skip list [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/02_Basic_3.pdf)] [[video (English)](https://youtu.be/UGaOXaXAM5M)] [[video (Chinese)](https://youtu.be/m6m0pnsOzN4)]. 3. **Sorting**. * Insertion sort [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/03_Sorting_1.pdf)] [[video (English)](https://youtu.be/m5UJM-0gtD8)]. * Bubble sort [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/03_Sorting_2.pdf)]. * Merge sort [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/03_Sorting_3.pdf)]. * Quick sort [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/03_Sorting_4.pdf)]. * Quick select [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/03_Sorting_5.pdf)]. 4. **Divide and Conquer**. * Master theorem [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/04_DC.pdf)]. 5. **Matrix Data Structure and Algorithms**. * Addition and multiplication [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/05_Matrix_1.pdf)] [[video (English)](https://youtu.be/ZTtW6SMTmcY)] [[video (Chinese)](https://youtu.be/PzhMlw7xVs0)]. * Dense matrix data structures [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/05_Matrix_2.pdf)] [[video (English)](https://youtu.be/fy_dSZb-Xx8)] [[video (Chinese)](https://youtu.be/2KsvAa5zJt8)]. * Sparse matrix data structures [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/05_Matrix_3.pdf)] * Fast matrix multiplication and Strassen algorithm [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/05_Matrix_4.pdf)]. 6. **Binary Trees**. * Tree basics [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/06_Trees_1.pdf)] [[video (English)](https://youtu.be/HWPLrH-n0-k)]. * Binary search tree: search and insertion [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/06_Trees_2.pdf)]. * Binary search tree: traversal [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/06_Trees_3.pdf)]. * Binary search tree: deletion [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/06_Trees_4.pdf)]. 7. **Balanced Trees**. 8. **Priority Queues**. * Priority queues [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/08_PQ_1.pdf)]. * Binary heaps [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/08_PQ_2.pdf)]. 9. **Disjoint Sets**. * Disjoint sets [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/09_Sets_1.pdf)]. 10. **Graph Basics**. * Graph data structures [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/10_Graphs_1.pdf)] [[video (Chinese)](https://youtu.be/JS9MB8tp0eY)]. * Topological sort [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/10_Graphs_2.pdf)]. 11. **Shortest Paths**. * Shortest path problem [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/11_Path_1.pdf)] [[video (Chinese)](https://youtu.be/tsVUDM_lYKo)]. * Single-source shortest path in unweighted graphs [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/11_Path_2.pdf)] [[video (Chinese)](https://youtu.be/e7unEsKHW54)]. * Single-source shortest path in weighted graphs [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/11_Path_3.pdf)] [[video (Chinese)](https://youtu.be/uyNJxsH16nc)]. 12. **Minimum Spanning Trees**. * Spanning trees [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/12_Span_1.pdf)] [[video (Chinese)](https://youtu.be/KsobpcI3dN0)]. * Prim's algorithm [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/12_Span_2.pdf)] [[video (Chinese)](https://youtu.be/GLlIaT_PxVE)]. * Kruskal's algorithm [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/12_Span_3.pdf)] [[video (Chinese)](https://youtu.be/Z4jm4o2bt28)]. 13. **Network Flow Problems**. * Maximum flow problem [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/13_Flow_1.pdf)] [[video (Chinese)](https://youtu.be/6DFWUgV5Osc)]. * Ford-Fulkerson algorithm [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/13_Flow_2.pdf)] [[video (Chinese)](https://youtu.be/8sLON0DqLZo)]. * Edmonds–Karp algorithm [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/13_Flow_3.pdf)] [[video (Chinese)](https://youtu.be/l-5W0ffPsDo)]. * Dinic's algorithm [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/13_Flow_4.pdf)] [[video (Chinese)](https://youtu.be/mtxzaGFLIAo)]. * Max-flow and min-cut [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/13_Flow_5.pdf)] [[video (Chinese)](https://youtu.be/Ev_lFSIzNh4)]. 14. **Bipartite Graphs**. * Testing bipartiteness [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/14_BiGraph_1.pdf)] [[video (Chinese)](https://youtu.be/lyH43SAcyjc)]. * Maximum cardinality bipartite matching [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/14_BiGraph_2.pdf)] [[video (Chinese)](https://youtu.be/cndaoZ6XTxA)]. * Maximum weight bipartite matching [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/14_BiGraph_3.pdf)] [[video (Chinese)](https://youtu.be/7yN_KZijerA)]. * Hungarian algorithm [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/14_BiGraph_4.pdf)] [[video (Chinese)](https://youtu.be/bSoZQkxc1Zw)]. * Stable marriage problem [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/14_BiGraph_5.pdf)] [[video (Chinese)](https://youtu.be/qwA5QNqyK08)]. * Gale-Shapley algorithm [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/14_BiGraph_6.pdf)] [[video (Chinese)](https://youtu.be/nYTTv9GL7gw)]. 15. **Dynamic Programming**. * Fibonacci numbers [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/15_DP_1.pdf)]. * Climbing stairs [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/15_DP_2.pdf)]. * Longest common substring [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/15_DP_3.pdf)]. * Edit distance [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/15_DP_4.pdf)]. * Combinations of coins [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/15_DP_5.pdf)]. * Knapsack [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/15_DP_6.pdf)]. 16. **Strings**. * Tries. [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/16_String_1.pdf)]. * KMP algorithm. [[slides-1](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/16_String_2.pdf)] [[slides-2](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/16_String_3.pdf)]. 17. **Randomized Algorithms**. * Monte Carlo algorithms [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/17_Rand_1.pdf)] [[video (English)](https://youtu.be/CmpWM2HMhxw)] [[video (Chinese)](https://youtu.be/XRGquU0ZJok)]. * Concentration inequalities [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/17_Rand_2.pdf)]. * Pseudo random number generators. * Random shuffling [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/17_Rand_4.pdf)] [[video (English)](https://youtu.be/xaSBvljOQkc)] [[video (Chinese)](https://youtu.be/1m68x5Gy5No)]. * Fingerprinting. 18. **Hashing**. * Hash table [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/18_Hash_1.pdf)]. * Collision-resistant hash [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/18_Hash_2.pdf)]. * Locality sensitive hashing [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/18_Hash_3.pdf)]. 19. **Cryptographic Algorithms**. * RSA algorithm [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/19_Crypto_1.pdf)]. * Digital signature [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/19_Crypto_2.pdf)]. * Homomorphic encryption [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/19_Crypto_3.pdf)]. 20. **Crypto Currency**. * Decentralized payment system [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/20_CryptoCurrency_1.pdf)]. * Blockchain [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/20_CryptoCurrency_2.pdf)]. * Merkel tree [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/20_CryptoCurrency_3.pdf)]. 21. **Backtracking**. * Turnpike reconstruction [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/21_Backtracking_1.pdf)]. * Eight queens problem [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/21_Backtracking_2.pdf)]. * Hamiltonian cycle [[slides](https://github.com/wangshusen/AdvancedAlgorithms/blob/master/Slides/21_Backtracking_3.pdf)].