Important Topics for Competitive Programming.

You may have wondered about the vast and endless nature of topics important(or I should say sufficient) for competitive programming point of view. Well to sum it all I have prepared a list(huge one!!!). It contains all the famous problems,algorithms and data structure…………………………

(a)Number Theory

  1. Prime Number Generation  (Sieve, Segmented Sieve)
  2. Euler Totient Theorem
  3. Fermat’s Theorem
  4. HCF & LCM (Euclid)
  5. Linear Diophantine Equations (Extended Euclid)
  6. Modulus Arithmetic (addition,multiplication,subtraction,modular Inverse)
  7. Cycle Finding (Floyd Algo and Brent Algo)
  8. Integer Factorization (Trial Division , Pollard Rho method)
  9. Lucas Theorem  (Simple & Advance)
  10. Chinese Remainder Theorem
  11. Wilson Theorem
  12. Miller – Rabin Primality Testing
  13. Perfect Numbers
  14. Goldbach Conjecture

(b)Probability

  1. Basic Probability and Conditional Probability
  2. Random Variables
  3. Probability Generating Functions
  4. Expectation
  5. Probability Distribution [Binomial, Poisson, Normal,Bernoulli]

(c)Counting

  1. Pigeonhole principle
  2. Inclusion Exclusion
  3. Special Numbers  [Stirling,Fibonacci,Catalan, Eulerian, Harmonic, Bernoulli]
  4. Polya Counting
  5. Burnside lemma

(d)Permutation Cycles

(e)Linear Algebra

  1. Addition And Subtraction Of Matrices
  2. Multiplication ( Strassen’s algorithm ), Logarithmic exponentiation
  3. Matrix Transformations [ Transpose, Rotation Of Matrix, Representing Linear Transformations Using Matrix ]
  4. Determinant , Rank and Inverse Of Matrix [ Gaussian Elimination , Gauss Jordan Elimination]
  5. Solving System Of Linear Equations
  6. Matrix Exponentiation To Solve Recurrences
  7. Eigenvalues And Eigen vector
  8. Roots of a polynomial [ Prime factorization of a polynomial, Integer roots of a polynomial]
  9. Lagrange Interpolation

(e)Game Theory

  1. Basic Concepts & Nim Game [Grundy Theorem , Grundy Number]
  2. Hackenbush

(f)Group Theory

  1. Burnside Lemma
  2. Polya’s Theorem

Graphs:

(a)Graph Representation

  1. Adjacency Matrix
  2. Adjacency List
  3. Incidence Matrix
  4. Edge List

(b)Graph Types

  1. Directed
  2. Undirected
  3. Weighted
  4. Unweighted
  5. Planar
  6. Hamilton
  7. Euler
  8. Special Graphs

(c)DFS & It’s Application

  1. Cycle Detection
  2. Articulation Points
  3. Bridges
  4. Strongly Connected Component
  5. Connected Component
  6. Path Finding
  7. Solving Maze
  8. Biconnectivity in Graph
  9. Topological Sorting
  10. Bipartite Checking
  11. Planarity Testing
  12. Flood-fill algorithm

(d)BFS & It’s Application

  1. Shortest Path (No. Of Edges)
  2. Bipartite Checking
  3. Connected Components

(d)Minimum Spanning Tree

  1. Prim’s Algorithm
  2. Kruskal Algorithm

(d)Single Source Shortest-Path

  1. Dijkstra
  2. Bellman Ford

(e)All pair Shortest Path

  1. Floyd Warshall’s Algorithm

(f)Euler Tour

(g)Flow

  1. Ford-Fulkerson [PFS,DFS,BFS]
  2. Dinic’s Algorithm
  3. Min Cost – Max Flow  [Successive Shortest Path Algo,Cycle Cancelling Algorithm]
  4. Max Weighted BPM  [Kuhn Munkres algorithm/Hungarian Method]
  5. Stoer Wagner Min-Cut Algo
  6. Hop-Kraft BPM
  7. Edmond Blossom Shrinking Algorithm

(h)Other Important Topics On Graphs

  1. 2-SAT,
  2. LCA
  3. Maximum Cardinality Matching
  4. Application Flow
  5. Min Path Cover Over Dag
  6. Independent Edge Disjoint Path
  7. Minimum Vertex Cover
  8. Maximum Independent Set

Data Structures:

  1. Arrays
  2. Linked List
  3. Trees (Binary Tree And Binary Search Tree)
  4. Stacks
  5. Queues
  6. Heap
  7. Hash Tables
  8. Disjoint-Set Data Structures
  9. Trie
  10. Segment Tree
  11. Binary Index Tree
  12. Treap

Searching And Sorting:

  1. Linear Search
  2. BInary Search
  3. Ternary Search
  4. Selection Sort
  5. Bubble Sort
  6. Insertion Sort
  7. Merge Sort
  8. Quick Sort
  9. Quick Select
  10. Heap Sort
  11. Radix Sort
  12. Counting Sort

Greedy:
Classical Problems of Greedy & Concept
example : Fractional Knapsack

Dynamic Programming Classical Problems

  1. Edit Distance
  2. Egg Dropping Puzzle
  3. Integer Knapsack
  4. Largest Independent Set
  5. Longest Biotonic Subsequence
  6. Longest Common Subsequence
  7. Longest Common Substring
  8. Longest Increasing Subsequence
  9. Longest Palindromic Subsequence
  10. Longest Palindromic Substring
  11. Longest Substring Without Repeating Character
  12. Matrix Chain Multiplication
  13. Max Size Square Submatrix With One
  14. Maximum Length Chain Pairs
  15. Maximum Sum Increasing Subsequence
  16. Optimal Binary Search Tree
  17. Palindrome Partition Problem
  18. Set Partition Problem
  19. Subset Sum
  20. Word Wrap Problem

Dynamic Programming  Advanced Techniques

  1. DP + Tree
  2. DP + Bit Masking
  3. DP + Binary Search
  4. DP + Graph
  5. DP + Matrix Exponentiation
  6. DP + Probability Space
  7. DP + Crack Recurrence

Divide & Conquer
Classical Problems & Concepts

  1. Merge Sort
  2. Closest Pair Points

Other Algorithm Design Techniques :

  1. BackTracking
  2. Man In Middle
  3. Newton-Raphson to reach the fixed point
  4. Brute Force
  5. Constructive Algo
  6. Sliding Window
  7. Pancake Sorting

Here is a topcoder link for some of algorithm tutorials.

Advertisements

2 thoughts on “Important Topics for Competitive Programming.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s