ACM-ICPC Preparation Guide
MIT License
This curriculum has been developed to learn Algorithms to use in Competitive Programming, but can also be used for:
Prerequisites:
The concept of this repository is to have well-structured content divided into parts that one can follow even if they are busy. Here we collected sources we find well prepared to learn the proposed topics. The curriculum has different data structures and algorithms.
Estimated time required for a week is 6-7 hours. (To complete the curriculum in the given time)
Basic usage guide: Using this repository depends on what the user wants to do with it. Here we are suggesting the following for people who want to slowly gain knowledge of the topics while continuing their studies etc.:
Here are some of the websites/tools that we use through this curriculum:
If you have anything to add, do not hesitate to offer! You can check Code of Conduct. You can submit a PR or an issue; I will try to personally review all.
Here are the topics we currently include in the curriculum.
Number Theory
Combinatorics (Probability-Combinations-Permutations-Matrix..)
Computational Geometry
Sort
Search
Graph Theory
Dynamic Programming
Strings
Bit Manipulation
Game theory
Optional Advanced Algorithms
Week | Topics | Optional Topics |
---|---|---|
**Heads Up ** | Big O Notation | |
1.Week | Prime Numbers (Sieve of Eratosthenes)Efficient Prime FactorizationModular Exponentiation | |
2.Week | GCD and LCM Euclids AlgorithmLong arithmetic (Multi, Sum, Div, Sub) | C++ STL:VectorC++ STL:PairsC++ STL:Iterators |
3.Week | QuickSortCounting Sort | C++ STL:StringC++ STL:SetC++ STL:Map |
4.Week | Merge SortBinary Search | Ternary Search |
5.Week | Queue (DS)Stack (DS)Breadth First SearchDepth First Search | C++ STL: QueueC++ STL: Stack |
6.Week | Linked List (DS)Dijkstras Shortest PathMinimum Spanning Tree (MST)Floyd Warshall | Cycle Detection (Union Find) |
7.Week | KnapsackCoin ChangeKadane | |
8.Week | Questions from previous topics | |
9.Week | Trees (DS)Segment Trees (DS)Range Minimum Query (RMQ)Lowest Common Ancestor (LCA) | Topological Sorting |
10.Week | Ford BellmanMax Flow / Min CutLongest increasing Subsequence (with RMQ) | Heavy Light Decomposition |
11.Week | Primitive OperationsIntuitionPolygon Inside, OutsideImplementing CCWImmutable Point ADTConvex HullClosest pair problemLine intersection | |
12.Week | Tries (DS)Suffix Trees/Arrays (DS)Knuth-Morris-Pratt Algorithm (KMP)Rabin-Karp Algorithm | |
13.Week | Heaps (DS)Priority queue (DS)Combinatorics | |
14.Week | Z algorithmHashDisjoint Data Structure (DS) | |
15.Week | Matrix chain multiplicationSQRT Decomposition (DS) | Mo's AlgorithmRod Cutting |
16.Week | Questions from previous topics | |
17.Week | Nim gameGrundy numbers | |
18.Week | Sprague-Grundy theoremFenwick tree or Binary indexed trees (DS) | |
19.Week | Bit Manipulation | Palindromic TreeAVL Trees |
20.Week | Heavy Light DecompositionDynamic Programming by Profile | Graph Coloring |