Algorithmic Resources

A Curated list of Topic wise Theory and Questions to Get You Started On Competitive Coding.

Topics

• Binary and Ternary Search
• Dynamic Programming
• Flow
• Game Theory
• Graphs
• Greedy
• Maths
• Matrix Exponentiation
• Miscellaneous
• Prefix and Suffix Trees
• Binary Indexed Trees
• Segment Trees
• Trees

Binary and Ternary Search

---

Binary Search : The process of exploiting the property of an array of being sorted to arrive at answers of questions in non linear time.

Ternary Search : The process of exploiting the property of a function having double diffrential of a constant sign to arrive to results in non linear time.

• Theory

  • Hackerearth - Power of Binary search by Aman Goel (Easy).
  • Topcoder - Binary Search by lovro (Hard).
  • Hackerearth - Tutorial on Ternary Search.

• Questions on

  • Codeforces
  • A2oj
  • Codechef

Dynamic Programming

---

Used to solve questions which can be broken down into smaller sub problems.It involves the technique of saving the result of a problem for future reference.

• Theory

  • Topcoder - Dynamic Programming from Novice to Advanced.
  • Codechef - Tutorial on Dynamic Programming.
  • Quora - Getting started with Dynamic Programming (Quora Discussion).

• Questions on

  • Hackerrank
  • spoj
  • More Problems on SPOJ
  • A2oj
  • Codeforces

Flow

---

• Theory

  • Topcoder - Max Flow Part 1
  • Topcoder - Max Flow Part 2

• Questions

  • spoj
  • A2oj

Game Theory

---

Used to solve problems involving mathematical modelling of conflict and cooperation among rational players.

• Theory

  • Stanford - PDF on Combinatorial Games.
  • Wikipedia - Introduction to Nim Games.
  • Book - Composite Mathematical Games.
  • Book - Game Theory By Thomas S. Ferguson.
  • Wikipedia - Sprague Grundy Theorem.
  • Topcoder - Introduction to Algorithmic Games.

• Questions on

  • A2oj

Graphs

---

A graph consists of nodes and the interconnection between them.The problems involve finding shortest distance, connectivity and flow.

• Theory

  • Topcoder
    • Identifying a graph on Topcoder
    • Searching in a Graph
    • Path Algorithms
  • Codeforces - Important Graph Algorithms by PrinceOfPersia
  • Codechef - Tutorial on Graph Theory - part 1

• Questions on

  • Codeforces
  • Codechef
  • A2oj

Greedy

---

Greedy problems involve solving a problem statement considering the most greedy, i.e. most optimal solution at the given time without taking into consideration the future effects of it.

• Theory

  • Topcoder - Greedy is Good.
  • Stackoverflow. - Tutorial on how to spot a greedy algorithm.
  • Hackerearth - Tutorial on greedy algorithms by Akash Sharma.

• Questions on

  • Codeforces
  • A2oj

Maths

---

Problem related to mathematics are quite common in the domain of competitive programming.It involved topics like geometry, algebra, discrete mathematics and probability.

• Theory

  • Stanford - Stanford's Guide on Introduction To Competitive Programming.
  • Aduni - Course Guide to Discrete Mathematics.
  • Topcoder - Understanding Probability.

• Questions on

  • A2oj
  • Codechef - Basic
  • Codechef - Advanced

Matrix Exponentiation

---

Used to solve problems which involve finding a solution to a given series by using exponentiation property on multiplication of matrices.The complexity is thus reduced to logrithmic from linear.

• Theory

  • zobayer - Introduction to Matrix exponentiations
  • Quora - Solving Dynamic Programming with Matrix Exponentiation.
  • Codechef - Solving Recurrences using Cayley Hamilton Theorem and Matrix Exponentiation

• Questions on

  • A2oj
  • POWSUM on CodeChef

Miscellaneous

---

• Mo's Algorithm

  • Blog Post By Anudeep Nekkanti
  • Hackerearth
  • DQUERY on Spoj
  • FREQUENT on Spoj

• Persistant Segment Trees

  • Blog Post By Anudeep Nekkanti
  • MKTHNUM on Spoj

• Mobius Function

  • Dance With Mobius Function by Surya Kiran

• Treaps

  • Codeforces
  • Wikipedia
  • TREAP on Spoj

• Bit Manipulation

  • Hackerearth - Tutorial on Bit Manipulation by Prateek Garg.
  • Hackerrank - Questions On Hackerrank on bit manipulation.

• Other Resources

  • Data Structures - A guide to high level data structures by PrinceOfPersia

Prefix and Suffix Trees

---

Tries are some kind of rooted trees in which each edge has a character on it.

• Theory

  • Wikipedia - Introduction to Tries.
  • Marknelson - Tutorial on prefix and suffix trees by Sartaj Sahni
  • Marknelson - Suffix Trees Explained.
  • Geeksforgeeks - Trie, Insertion and Search
  • Geeksforgeeks - Trie, Deletion.

• Questions on

  • Codechef
  • Another problem on Codechef
  • A2oj

Binary Indexed Trees

---

A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

• Theory

• Hackerearth

• Wikipedia - Fenwick Tree (data structure)

• Topcoder

• Questions on

• A2oj

Segment Trees

---

Segment tree is a tree for which each node represents an interval.

• Theory

  • Hackerearth - Segment trees for Beginners by Ayush Agrawal.
  • Codeforces - Everything about Segment trees by PrinceOfPersia
  • Lazy Propogation - Solving problems related to updation of segment tree in logrithmic time (also known as lazy propogation).

• Questions on

  • Codechef
  • A2oj

Trees

---

A tree is a data structure made up of nodes or vertices and edges without having any cycle.

• Theory

  • Hackerearth - Baisc introduction to trees and terminologies related to it by Anuj Garg
  • Wikipedia - Tree (data structure)

• Questions on

  • Hackerrank
  • Codechef
  • A2oj
  • Codeforces