ACM-ICPC Preparation

This program has been developed to learn Algorithms for use in Competitive Prorgamming, but can be used for:

Competitive Programming
Practicing for Interviews
Improving Algorithmic Thinking
Practicing for College Classes
FUN

The course requires:

To know at least one programming language well. (You have to be able to use the language efficiently.)
You have to be familiar with some of the basic Data Structures (Array, Stack, Queue, etc.) (Although if you don't know one of them, you may learn it when you come across it.)

PS: I am saying "Any programming language" but in this course mostly we used C, C++ and some Java, but you can still follow the curriculum without any knowledge of these languages

In the program there is only direction to resources, we did not add much content apart from what already existed. We just collected good sources to learn in one place, so that one can follow up and learn. The course includes algorithms and a bit data structures. You need to follow the the curriculum week by week.

Basic following guide would be to:

See the sources to study
Get the logic and try to code it without looking other code
When you are stuck(you really should try first) or when you are done, look at the source code, and compare it with yours so that you can see what would be the best approach for that algorithm. You may not like others, or you may find some of them useful.
After you feel comforatable with the code, try to solve the questions.
When you are done with solving or are stuck(again ...) check other solutions and try to understand your mistake or to see if a better aproach exists.

Resources

In this course we will use some tools for the questions. As I mentioned above all of these questions already exist, we just highlight them so that you can reach them easier. Here are the websites/tools that we use through this course:

I gave these tools name because you may not be able to submit your solution or display the question for some websites. It would be better if you just sign up. Although it is not neccesary...

Contribution

We are open to any support. If you have anything to add, do not hesitate to offer! For further information you can check Code of Conduct

Topics

Here are the topics we included in this curriculum.

DS

Stacks
Queues
Priority queue
Hashmap
Linked List
Trees
Heaps
Advanced Trees
- Tries
- Segment trees
- Fenwick tree or Binary indexed trees
- RMQ
SQRT Decomposition
Disjoint Data Structure
C++ STL (optional)

Algo

Number Theory
- Prime Numbers (Sieve of Eratosthenes)
- GCD and LCM Euclid’s Algorithm
- Modular Exponentiation
- Long arithmetic (Multi, Add)
- Efficient Prime Factorization
Combinatorics(Probability-Combinations-Permutations-Matrix..)
Computational geometry
- Primitive Operations
  - Intuition
  - Polygon Inside, Outside
  - Implementing CCW
  - Immutable Point ADT
- Convex Hull
- Closest pair problem
- Line intersection
Sorting
- QuickSort
- Counting Sort
- Merge Sort
Searching
- Binary Search
- Ternary Search
Graph Theory
- Depth First Search (DFS)
- Breadth First Search (BFS)
- Dijkstra’s Shortest Path
- Minimum Spanning Tree
- Ford Bellman
- Floyd Warshall
- LCA (Lowest Common Ancestor)
- Max Flow / Min Cut
Dynamic programming
- Knapsack
- Matrix chain multiplication
- Coin Change
- Kadane
- Longest increasing Subsequence (with RMQ)
Strings
- Z algorithm
- Suffix Trees/Arrays
- Knuth-Morris-Pratt Algorithm (KMP)
- Rabin-Karp Algorithm
- Hash
Bit Manipulation
Game theory
- Nim game
- Grundy numbers
- Sprague-Grundy theorem
Optional Advanced Algorithms
- AVL Trees
- Graph Coloring
- Mo's Algorithm
- Palindromic Tree
- Heavy Light Decomposition
- Dynamic Programming by Profile
- Rod Cutting
- Topological Sorting
- DP with Bitmask - Dynamic Programming
- Diobhantine Equation - Math
- Flood Fill - Graph

Here is our Curriculum

Week	Topics	Optional Topics
Heads Up	Big O Notation
Week 1	Prime Numbers (Sieve of Eratosthenes) Efficient Prime Factorization Modular Exponentiation
Week 2	GCD and LCM Euclid’s Algorithm Long arithmetic (Multi, Sum, Div, Sub)	C++ STL:Vector C++ STL:Pairs C++ STL:Iterators
Week 3	QuickSort Counting Sort	C++ STL:String C++ STL:Set C++ STL:Map
Week 4	Merge Sort Binary Search	Ternary Search
Week 5	Queue (DS) Stack (DS) Breadth First Search Depth First Search	C++ STL: Queue C++ STL: Stack
Week 6	Linked List (DS) Dijkstra’s Shortest Path Minimum Spanning Tree (MST) Floyd Warshall	Cycle Detection (Union Find)
Week 7	Knapsack Coin Change Kadane
Week 8	Questions from previous topics
Week 9	Trees (DS) Segment Trees (DS) Range Minimum Query (RMQ) Lowest Common Ancestor (LCA)	Topological Sorting
Week 10	Ford Bellman Max Flow / Min Cut Longest increasing Subsequence (with RMQ)	Heavy Light Decomposition
Week 11	Primitive Operations Intuition Polygon Inside, Outside Implementing CCW Immutable Point ADT Convex Hull Closest pair problem Line intersection
Week 12	Tries (DS) Suffix Trees/Arrays (DS) Knuth-Morris-Pratt Algorithm (KMP) Rabin-Karp Algorithm
Week 13	Heaps (DS) Priority queue (DS) Combinatorics
Week 14	Z algorithm Hash Disjoint Data Structure (DS)
Week 15	Matrix chain multiplication SQRT Decomposition (DS)	Mo's Algorithm Rod Cutting
Week 16	Questions from previous topics
Week 17	Nim game Grundy numbers
Week 18	Sprague-Grundy theorem Fenwick tree or Binary indexed trees (DS)
Week 19	Bit Manipulation	Palindromic Tree AVL Trees
Week 20	Heavy Light Decomposition Dynamic Programming by Profile	Graph Coloring

kidogb/ACM-ICPC-Preparation