Data Structures and Algorithms

Hi all,
I need your help to make a list of most used data structures and algorithms along with their tutorials, implementation and some problems on them. It will be helpful to everyone in many ways. I request everyone to contribute to this list by providing links to tutorials, problems, etc. I will keep updating this list regularly.

  1. Binary Search :
    Tutorial, Problems, Tutorial, Implementation, Problem

  2. Quicksort :
    Tutorial, Implementation, Tutorial

  3. Merge Sort :
    Tutorial, Implementation, Tutorial

  4. Suffix Array :
    Tutorial, Tutorial, Implementation, Tutorial, Implementation, Problem, Problem

  5. Knuth-Morris-Pratt Algorithm (KMP) :
    Tutorial, Tutorial, Implementation, Tutorial, Problem

  6. Rabin-Karp Algorithm :
    Tutorial, Implementation, Tutorial, Problem, Problem

  7. Tries :
    Tutorial, Problems, Tutorial : I, II, Tutorial, Problem, Problem, Problem

  8. Depth First Traversal of a graph :
    Tutorial, Impelementation, Tutorial, Problems, Problem, Problem, Problem

  9. Breadth First Traversal of a graph :
    Tutorial, Impelementation, Tutorial, Problems, Problem, Problem, Problem, Flood Fill

  10. Dijkstra’s Algorithm :
    Tutorial, Problems, Problem, Tutorial(greedy), Tutorial (with heap), Implementation, Problem, Problem

  11. Binary Indexed Tree :
    Tutorial, Problems, Tutorial, Original Paper, Tutorial, Tutorial, Problem, Problem,
    Problem, Problem, Problem, Problem, Problem

  12. Segment Tree (with lazy propagation) :
    Tutorial, Implementation, Tutorial, Tutorial, Problems, Implementation, Tutorial, Implementation and Various Uses, Persistent Segment Tree: I, II, problems same as BIT, Problem, Problem/HLD is used as well/

  13. Z algorithm :
    Tutorial, Problem, Tutorial, Tutorial, problems same as KMP.

  14. Floyd Warshall Algorithm :
    Tutorial, Implementation, Problem, Problem

  15. Sparse Table (LCP, RMQ) :
    Tutorial, Problems, Tutorial, Implementation(C++), Java implementation

  16. Heap / Priority Queue / Heapsort :
    Implementation, Explanation, Tutorial, Implementation, Problem, Chapter from CLRS

  17. Modular Multiplicative Inverse

  18. Binomial coefficients (nCr % M): Tutorial, Tutorial, Paper (Link Not Working), Problem

  19. Suffix Automaton :
    Detailed Paper, Tutorial, Implementation (I), Tutorial, Implementation (II), Problem, Problem, Problem, Problem, Tutorial, Implementation

  20. Lowest Common Ancestor :
    Tutorial, Problems, Paper, Paper, Problem, Problem, Problem

  21. Counting Inversions :
    Divide and Conquer, Segment Tree, Fenwick Tree, Problem

  22. Euclid’s Extended Algorithm

  23. Suffix Tree :
    Tutorial, Tutorial, Intro, Construction : I, II, Implementation, Implementation, Problem, Problem, Problem, Problem

  24. Dynamic Programming :
    Chapter from CLRS(essential), Tutorial, Problems, Problem, Problem, Problem, Problem, Tutorial, Problem, Problem, Problem, Longest Increasing Subsequence, Bitmask DP, Bitmask DP, Optimization, Problem, Problem, Problem, Problem, Problem, Problem, Problem, DP on Trees : I, II

  25. Basic Data Structures :
    Tutorial, Stack Implementation, Queue Implementation, Tutorial, Linked List Implementation

  26. Logarithmic Exponentiation

  27. Graphs :
    Definition, Representation, Definition, Representation, Problem, Problem

  28. Minimum Spanning Tree :
    Tutorial, Tutorial, Kruskal’s Implementation, Prim’s Implementation, Problem, Problem, Problem, Problem, Problem

  29. Efficient Prime Factorization

  30. Combinatorics :
    Tutorial, Problems, Problem, Tutorial

  31. Union Find/Disjoint Set :
    Tutorial, Tutorial, Problems, Problem, Problem, Problem

  32. Knapsack problem :
    Solution, Implementation

  33. Aho-Corasick String Matching Algorithm :
    Tutorial, Implementation, Problem, Problem, Problem, Problem

  34. Strongly Connected Components :
    Tutorial, Implementation, Tutorial, Problem, Problem, Problem

  35. Bellman Ford algorithm :
    Tutorial, Implementation, Tutorial, Implementation, Problem, Problem

  36. Heavy-light Decomposition :
    Tutorial, Problems, Tutorial, Implementation, Tutorial, Implementation, Implementation, Problem, Problem, Problem

  37. Convex Hull :
    Tutorial, Jarvis Algorithm Implementation, Tutorial with Graham scan, Tutorial, Implementation, Problem, Problem, Problem, Problem, Problem

  38. Line Intersection :
    Tutorial, Implementation, Tutorial, Problems

  39. Sieve of Erastothenes

  40. Interval Tree :
    Tutorial, Implementation, Problem, Problem, Problem, Problem, Problem, Problem, Tutorial

  41. Counting Sort

  42. Probabilities

  43. Matrix Exponentiation :
    Tutorial, Tutorial

  44. Network flow :
    (Max Flow)Tutorial : I, II, Max Flow(Ford-Fulkerson) Tutorial, Implementation, (Min Cut) Tutorial, Implementation, (Min Cost Flow)Tutorial : I, II, III, Dinic’s Algorithm with Implementation, Max flow by Edmonds Karp with Implementation, Problem, Problem, Problem, Problem, Problem, Problem, Problem, Problem, Problem, Problem, Problem, Problem, Problem, Problem, Problem

  45. K-d tree :
    Tutorial, Tutorial, Implementation, Problem

  46. Deque

  47. Binary Search Tree :
    Tutorial, Implementation, Searching and Insertion, Deletion

  48. Quick Select :
    Implementation, Implementation

  49. Treap/Cartesian Tree :
    Tutorial(detailed), Tutorial, Implementation, Uses and Problems, Problem, Problem

  50. Game Theory :
    Detailed Paper, Tutorial, Problems, Grundy Numbers, Tutorial with example problems - I, II, III, IV, Tutorial, Problems, Problem, Problem, Problem, Problem, Problem, Problem, Problem, Problem, Problem, Problem, Problem, Nim

  51. STL (C++) :
    I, II, Crash Course

  52. Maximum Bipartite Matching

  53. Manacher’s Algorithm :
    Implementation, Tutorial, Tutorial, Implementation, Tutorial, Implementation, Problem, Problem, Problem

  54. Miller-Rabin Primality Test and this

  55. Stable Marriage Problem

  56. Hungarian Algorithm, Tutorial

  57. Sweep line Algorithm : I, II

  58. LCP :
    Tutorial, Implementation, Tutorial, Implementation

  59. Gaussian Elimination

  60. Pollard Rho Integer Factorization, problem

  61. Topological Sorting

  62. Detecting Cycles in a Graph : Directed - I, II
    Undirected : I

  63. Geometry : Basics, Tutorial

  64. Backtracking :
    N queens problem, Tug of War, Sudoku

  65. Eulerian and Hamiltonian Paths :
    Tutorial, Tutorial, (Eulerian Path and Cycle)Implementation, (Hamiltonian Cycle)Implementation

  66. Graph Coloring :
    Tutorial, Implementation

  67. Meet in the Middle :
    Tutorial, Implementation

  68. Arbitrary Precision Integer(BigInt), II

  69. Radix Sort, Bucket Sort

  70. Johnson’s Algorithm :
    Tutorial, Tutorial, Implementation

  71. Maximal Matching in a General Graph :
    Blossom/Edmond’s Algorithm, Implementation, Tutte Matrix, Problem

  72. Recursion : I, II, Towers of Hanoi with explanation

  73. Inclusion and Exclusion Principle : I, II

  74. Co-ordinate Compression

  75. Sqrt-Decomposition :
    Tutorial, Tutorial, Problem, Problem

  76. Link-Cut Tree :
    Tutorial, Wiki, Tutorial, Implementation, Problem, Problem, Problem, Problem

  77. Euler’s Totient Function :
    Explanation, Implementation, Problems, Explanation, Problems

  78. Burnside Lemma :
    Tutorial, Tutorial, Problem

  79. Edit/Levenshtein Distance :
    Tutorial, Introduction, Tutorial, Problem, Problem

  80. Branch and Bound

  81. Math for Competitive Programming

  82. Mo’s Algorithm : Tutorial and Problems

1172 Likes

we already have a topic for list of imp algo

http://discuss.codechef.com/questions/18752/what-are-the-must-known-algorithms-for-online-programming-contests

17 Likes

A good initiative :slight_smile:

37 Likes

add geeksforgeeks.org for tutorials

6 Likes

I bookmarked this page… relating to the problem is best part… thanku…
want more…:slight_smile:

5 Likes

Nice Initiative I would recommend MAXimal :: algo for the implementation and theory. Make use of google translate. It also have a good set of questions in the end.

For DP I would recommend this the topic is nicely explained by Mimino.(For starters)

10 Likes

Take a look of this website once…Explanation of all the algorithms from different sources can be found at one place!!!

13 Likes

link

The above link has lesser known but useful data structures.

33 Likes

I think stackoverflow can also be of immense help.

Really awesome effort.

8 Likes

For heavy-light decomposition -

 http://wcipeg.com/wiki/Heavy-light_decomposition 
20 Likes

I have found a nice implementation of Dijkstra’s algorithm using c++. Please , have a look at the following link:

 I, ME AND MYSELF !!!: Dijkstra's Algorithm in C++

3 Likes

Matrix exponentiation :  I, ME AND MYSELF !!!: Matrix Exponentiation

related problem : Long walks from Office to Home Sweet Home | Practice Problems

17 Likes

One might try http://e-maxx.ru/ :slight_smile: It’s in Russian though, but Google translator might help.

9 Likes

Quick Select

Deque

Binary Search Trees

2 Likes

Really good work.

God Bless you and you will win IOI :slight_smile:

29 Likes

GRUNDY NUMBERS-

4 Likes

Superb initiative !! Keep it up

I hope i will help you

2 Likes

persistent segment tree: Explanation with basic code, tutorial with implementations of spoj and codechef problems by Anudeep Nekkanti

2 Likes

Try this for classical problems of dp(interactive tutorial)

http://people.cs.clemson.edu/~bcdean/dp_practice/

2 Likes

This one is an awesome and very good crash course of STL here

Add this to list.

5 Likes