/ACM-ICPC-Preparation

ACM-ICPC Preparation Guide

Primary LanguageC++MIT LicenseMIT

ACM-ICPC

ACM-ICPC Preparation

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

  • Competitive Programming
  • Practicing for Interviews
  • Improving Algorithmic Thinking
  • Practicing for College Class
  • 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 familiarize with some of the basic Data Structures (Array, Stack, Queue, etc.) (Although if you don't know some of them, you may learn it when you come accross.)
PS: I am saying "Any programming language" but in this course mostly we used C, C++ and some Java. But still you can follow the curriculum without any knowledge of these languages

In the program there is only guidence, so we did not add many content apart from that already exist. 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 fallowing guide would be to:

  1. See the sources to study
  2. Get the logic and try to code it without looking other codes
  3. When you are stuck(you really should try first) or when you are done, look at the source codes, 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.
  4. After feeling comfortable with the code itself, try to solve the questions.
  5. When you are done with solving or are stuck(again ...) check other solutions and try to understand your mistake or 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 exists, we just highlight them so that you can reach better. 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
1.Week
  • Prime Numbers (Sieve of Eratosthenes)
  • Efficient Prime Factorization
  • Modular Exponentiation
2.Week
  • GCD and LCM Euclid’s Algorithm
  • Long arithmetic (Multi, Sum, Div, Sub)
  • C++ STL:Vector
  • C++ STL:Pairs
  • C++ STL:Iterators
3.Week
  • QuickSort
  • Counting Sort
  • C++ STL:String
  • C++ STL:Set
  • C++ STL:Map
4.Week
  • Merge Sort
  • Binary Search
  • Ternary Search
5.Week
  • Queue (DS)
  • Stack (DS)
  • Breadth First Search
  • Depth First Search
  • C++ STL: Queue
  • C++ STL: Stack
6.Week
  • Linked List (DS)
  • Dijkstra’s Shortest Path
  • Minimum Spanning Tree (MST)
  • Floyd Warshall
  • Cycle Detection (Union Find)
7.Week
  • Knapsack
  • Coin Change
  • Kadane
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 Bellman
  • Max Flow / Min Cut
  • Longest increasing Subsequence (with RMQ)
  • Heavy Light Decomposition
11.Week
  • Primitive Operations
    • Intuition
    • Polygon Inside, Outside
    • Implementing CCW
    • Immutable Point ADT
  • Convex Hull
  • Closest pair problem
  • Line 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 algorithm
  • Hash
  • Disjoint Data Structure (DS)
15.Week
  • Matrix chain multiplication
  • SQRT Decomposition (DS)
  • Mo's Algorithm
  • Rod Cutting
16.Week Questions from previous topics
17.Week
  • Nim game
  • Grundy numbers
18.Week
  • Sprague-Grundy theorem
  • Fenwick tree or Binary indexed trees (DS)
19.Week
  • Bit Manipulation
  • Palindromic Tree
  • AVL Trees
20.Week
  • Heavy Light Decomposition
  • Dynamic Programming by Profile
  • Graph Coloring

Contributers

  • Mustafa Bedir Tapkan . . . .
  • Nadide Pasali . . . . . . . . . .
  • Almaz Tukenov . . . . . . . . . .
  • Inamullah Rasuna Muhammad . . . .
A NAU-ACM Project