# 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. Depth First Traversal of a graph :
Tutorial, Impelementation, Tutorial, Problems, Problem, Problem, Problem

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

9. Dijkstraâ€™s Algorithm :
Tutorial, Problems, Problem, Tutorial(greedy), Tutorial (with heap), Implementation, Problem, Problem

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

11. 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/

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

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

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

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

16. Modular Multiplicative Inverse

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

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

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

20. Euclidâ€™s Extended Algorithm

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

22. 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

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

24. Logarithmic Exponentiation

25. Minimum Spanning Tree :
Tutorial, Tutorial, Kruskalâ€™s Implementation, Primâ€™s Implementation, Problem, Problem, Problem, Problem, Problem

26. Efficient Prime Factorization

27. Combinatorics :
Tutorial, Problems, Problem, Tutorial

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

29. Knapsack problem :
Solution, Implementation

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

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

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

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

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

35. Sieve of Erastothenes

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

37. Counting Sort

38. Probabilities

39. Matrix Exponentiation :
Tutorial, Tutorial

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

41. Deque

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

43. Quick Select :
Implementation, Implementation

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

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

46. Maximum Bipartite Matching

47. Manacherâ€™s Algorithm :
Implementation, Tutorial, Tutorial, Implementation, Tutorial, Implementation, Problem, Problem, Problem

48. Stable Marriage Problem

49. Gaussian Elimination

50. Topological Sorting

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

52. Geometry : Basics, Tutorial

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

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

55. Graph Coloring :
Tutorial, Implementation

56. Meet in the Middle :
Tutorial, Implementation

57. Johnsonâ€™s Algorithm :
Tutorial, Tutorial, Implementation

58. Maximal Matching in a General Graph :
Blossom/Edmondâ€™s Algorithm, Implementation, Tutte Matrix, Problem

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

60. Co-ordinate Compression

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

Tutorial, Wiki, Tutorial, Implementation, Problem, Problem, Problem, Problem

63. Eulerâ€™s Totient Function :
Explanation, Implementation, Problems, Explanation, Problems

64. Burnside Lemma :
Tutorial, Tutorial, Problem

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

66. Branch and Bound

67. Math for Competitive Programming

68. Moâ€™s Algorithm : Tutorial and Problems

1169 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

37 Likes

6 Likes

I bookmarked this pageâ€¦ relating to the problem is best partâ€¦ thankuâ€¦
want moreâ€¦

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

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/ Itâ€™s in Russian though, but Google translator might help.

9 Likes
2 Likes

Really good work.

God Bless you and you will win IOI

29 Likes

GRUNDY NUMBERS-

4 Likes

Superb initiative !! Keep it up

2 Likes
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