ACM/ICPC Road Map

The necessary Topics and Algorithms.

image

Elementary Data structure

  • array
  • stack
  • queue
  • string
  • heap
  • hash

Advanced Data Structrue

  • Priority Queue
  • Binary Indexed Tree or Fenwick Tree
  • Segment Tree(RMQ, Range Sum and Lazy Propagation)
  • K-D tree(insert, minimum, delete)
  • Union Find Disjoint Set(cycle Detection and by range or path compression)
  • Tries
  • Interval Tree
  • binary Search
  • Qucik Sort(Quick Select)
  • Merge Sort
  • Order Statistics

String Manipulation

  • KMP algorithm
  • Rabin Karp
  • Z’s algorithm
  • Aho Corasick String Matching

C++ skillset

Dynamic Programming

1
2
3
4
5
6
7
8
9
10
11
Longest Common Subsequence
Longest Increasing Subsequence
Edit Distance
Minimum Partition
Ways to Cover a Distance
Longest Path In Matrix
Subset Sum Problem
Optimal Strategy for a Game
0-1 Knapsack Problem
Assembly Line Scheduling
Optimal Binary Search Tree

backtracking

1
2
3
4
5
Rat in a Maze
N Queen Problem
Subset Sum
m Coloring Problem
Hamiltonian Cycle

Graph Algorithms

One of the most important topic which you can not ignore if preparing for ACM – ICPC.

1
2
3
4
5
6
7
8
9
10
Breadth First Search (BFS)
Depth First Search (DFS)
Shortest Path from source to all vertices **Dijkstra**
Shortest Path from every vertex to every other vertex **Floyd Warshall**
Minimum Spanning tree **Prim**
Minimum Spanning tree **Kruskal**
Topological Sort
Johnson’s algorithm
Articulation Points (or Cut Vertices) in a Graph
Bridges in a graph