Introduction
This GitHub project that one of the ongoing project of NAU ACM Chapter aim to guide people in competitive programming.
This project developed to learn algorithms for using in competitive programming, but also can be used for:
- Competitive Programming
- Practicing for Interviews
- Improving Algorithmic Thinking
- Practicing for College Class
- FUN !!
The project is offering a week-by-week processing curriculum that includes essential data structures and algorithms. Each week has three parts to follow:
- Sources to learn basic of algorithm
- Source codes to find out more
- Questions to practice it
The project provides collections of good sources about each algorithm. In time, blog tutorials will be added by synthesizing these sources, so you can take advantage of learning in one place.
The project also provide different contributors’ codes. After you try by your own you can go and see different approaches in same problem.
The well-developed curriculum is easy to follow up and learn. The only thing you will do is to follow curriculum week-by-week.
The course requires:
- To know at least one programming language well.
- You have to be familiar with some of the basic Data Structures (Array, Stack, Queue, etc.)
PS: In the course mostly we used C, C++ and some Java. But still you can follow the curriculum without any prior knowledge of these languages
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
- Primitive Operations
- 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
Curriculum
Resources
Here are the websites/tools that we use through this course: