List of Algorithms and data structures for Competitive Programming

YOUTUBE CHANNEL

 List of most used data structures and algorithms along with their tutorials, implementation and some problems on them.

1. Binary Search :
   Tutorial, Problems 6.3k, Tutorial, Implementation 1.6k, Problem 1.8k

2. Quicksort :
   Tutorial, Implementation 953, Tutorial 450

3. Merge Sort :
   Tutorial, Implementation 450, Tutorial 450

4. Suffix Array :
   Tutorial 839, Tutorial, Implementation 369, Tutorial, Implementation 151, Problem 226, Problem 105

5. Knuth-Morris-Pratt Algorithm (KMP) :
   Tutorial 637, Tutorial, Implementation 204, Tutorial 62, Problem 193

6. Rabin-Karp Algorithm :
   Tutorial, Implementation 296, Tutorial 55, Problem 59, Problem 39

7. Tries :
   Tutorial, Problems 423, Tutorial : I, 196 II 45, Tutorial 71, Problem 82, Problem 40, Problem 47

8. Depth First Traversal of a graph :
   Tutorial, Impelementation 460, Tutorial, Problems 268, Problem 167, Problem 72, Problem 58

9. Breadth First Traversal of a graph :
   Tutorial, Impelementation 165, Tutorial, Problems 268, Problem 58, Problem 29, Problem 22, Flood Fill 29

10. Dijkstra’s Algorithm :
    Tutorial, Problems 303, Problem 86, Tutorial(greedy) 62, Tutorial (with heap) 39, Implementation 55, Problem 41, Problem 36

11. Binary Indexed Tree :
    Tutorial, Problems 265, Tutorial 67, Original Paper 35, Tutorial 26, Tutorial 18, Problem 43, Problem 16,
    Problem 19, Problem 24, Problem 14, Problem 20, Problem 21

12. Segment Tree (with lazy propagation) :
    Tutorial, Implementation 228, Tutorial 79, Tutorial, Problems, Implementation 83, Tutorial, Implementation and Various Uses 48, Persistent Segment Tree: I 20, II 13, problems same as BIT, Problem 43, Problem 11/HLD is used as well/

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

14. Floyd Warshall Algorithm :
    Tutorial, Implementation 145, Problem 30, Problem 8

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

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

17. Modular Multiplicative Inverse 86

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

19. Suffix Automaton :
    Detailed Paper 33, Tutorial, Implementation (I) 33, Tutorial, Implementation (II) 9, Problem 6, Problem 3, Problem 59, Problem 105, Tutorial, Implementation 6

20. Lowest Common Ancestor :
    Tutorial, Problems 110, Paper 24, Paper 12, Problem 16, Problem 6, Problem 11

21. Counting Inversions :
    Divide and Conquer 68, Segment Tree 23, Fenwick Tree 26, Problem 15

22. Euclid’s Extended Algorithm 67

23. Suffix Tree :
    Tutorial 66, Tutorial 9, Intro 7, Construction : I 5, II 3, Implementation 6, Implementation 3, Problem 3, Problem 3, Problem 1, Problem 1

24. Dynamic Programming :
    Chapter from CLRS(essential), Tutorial, Problems 402, Problem 100, Problem 22, Problem 14, Problem 13, Tutorial 28, Problem 11, Problem 9, Problem 15, Longest Increasing Subsequence 16, Bitmask DP 55, Bitmask DP 24, Optimization 17, Problem 10, Problem 6, Problem 4, Problem 4, Problem 3, Problem 5, Problem 11, DP on Trees : I 33, II 13

25. Basic Data Structures :
    Tutorial 277, Stack Implementation 162, Queue Implementation, Tutorial 52, Linked List Implementation 141

26. Logarithmic Exponentiation 73

27. Graphs :
    Definition, Representation 136, Definition, Representation 27, Problem 60, Problem 22

28. Minimum Spanning Tree :
    Tutorial 35, Tutorial, Kruskal’s Implementation 26, Prim’s Implementation 11, Problem 7, Problem 4, Problem 16, Problem 5, Problem 3

29. Efficient Prime Factorization 62

30. Combinatorics :
    Tutorial, Problems 229, Problem 43, Tutorial 64

31. Union Find/Disjoint Set :
    Tutorial 87, Tutorial, Problems 43, Problem 20, Problem 16, Problem 8

32. Knapsack problem :
    Solution, Implementation 136

33. Aho-Corasick String Matching Algorithm :
    Tutorial 61, Implementation 23, Problem 10, Problem 2, Problem 3, Problem 2

34. Strongly Connected Components :
    Tutorial, Implementation 46, Tutorial 3, Problem 8, Problem 2, Problem 4

35. Bellman Ford algorithm :
    Tutorial, Implementation 53, Tutorial, Implementation 3, Problem 10, Problem 6

36. Heavy-light Decomposition :
    Tutorial, Problems 47, Tutorial, Implementation 12, Tutorial 10, Implementation 6, Implementation 3, Problem 2, Problem 3, Problem 3

37. Convex Hull :
    Tutorial, Jarvis Algorithm Implementation 52, Tutorial with Graham scan 5, Tutorial 2, Implementation 5, Problem 7, Problem 7, Problem 2, Problem 1, Problem 3

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

39. Sieve of Erastothenes 67

40. Interval Tree :

41. Tutorial, Implementation 56, Problem 5, Problem 1, Problem 2, Problem 1, Problem 2, Problem 3, Tutorial 3

42. Counting Sort 38

43. Probabilities 84

44. Matrix Exponentiation :
    Tutorial 58, Tutorial 8

45. Network flow :
    (Max Flow)Tutorial : I, 33 II 6, Max Flow(Ford-Fulkerson) Tutorial, Implementation 19, (Min Cut) Tutorial, Implementation 4, (Min Cost Flow)Tutorial : I, 6 II, 2 III 1, Dinic’s Algorithm with Implementation 5, Max flow by Edmonds Karp with Implementation 7, Problem 4, Problem, Problem, Problem 2, Problem 2, Problem, Problem 4, Problem 1, Problem 1, Problem, Problem, Problem 1, Problem, Problem 2, Problem 3

46. K-d tree :
    Tutorial 63, Tutorial 16, Implementation 20, Problem 12

47. Deque 49

48. Binary Search Tree :
    Tutorial, Implementation 105, Searching and Insertion 22, Deletion 7

49. Quick Select :
    Implementation 25, Implementation 4

50. Treap/Cartesian Tree :
    Tutorial(detailed) 32, Tutorial, Implementation 14, Uses and Problems 16, Problem 1, Problem 1

51. Game Theory :
    Detailed Paper 73, Tutorial, Problems 24, Grundy Numbers 12, Tutorial with example problems - I, 10 II, 2 III, 1 IV 1, Tutorial, Problems 5, Problem 1, Problem 3, Problem 4, Problem 2, Problem, Problem 1, Problem 2, Problem 3, Problem 3, Problem 2, Problem 3, Nim 6

52. STL (C++) :
    I, 325 II 130, Crash Course 439

53. Maximum Bipartite Matching 35

54. Manacher’s Algorithm :
    Implementation 34, Tutorial 18, Tutorial, Implementation 3, Tutorial, Implementation 3, Problem 5, Problem 3, Problem 7

55. Miller-Rabin Primality Test 25 and this 4

56. Stable Marriage Problem 50

57. Hungarian Algorithm 39, Tutorial 6

58. Sweep line Algorithm : I 29, II 8

59. LCP :
    Tutorial, Implementation 50, Tutorial, Implementation 10

60. Gaussian Elimination 35

61. Pollard Rho Integer Factorization 11, problem 5

62. Topological Sorting 26

63. Detecting Cycles in a Graph : Directed - I 16, II 7
    Undirected : I 7

64. Geometry : Basics 59, Tutorial 29

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

66. Eulerian and Hamiltonian Paths :
    Tutorial 8, Tutorial 2, (Eulerian Path and Cycle)Implementation 3, (Hamiltonian Cycle)Implementation 7

67. Graph Coloring :
    Tutorial, Implementation 65

68. Meet in the Middle :
    Tutorial 71, Implementation 13

69. Arbitrary Precision Integer(BigInt) 6, II 1

70. Radix Sort 15, Bucket Sort 6

71. Johnson’s Algorithm :
    Tutorial 49, Tutorial 6, Implementation 11

72. Maximal Matching in a General Graph :
    Blossom/Edmond’s Algorithm, Implementation 22, Tutte Matrix 2, Problem 6

73. Recursion : I, 63 II 15, Towers of Hanoi 25 with explanation 13

74. Inclusion and Exclusion Principle : I 29, II 1

75. Co-ordinate Compression 23

76. Sqrt-Decomposition :
    Tutorial 53, Tutorial 13, Problem 20, Problem 11

77. Link-Cut Tree :
    Tutorial 53, Wiki 12, Tutorial, Implementation 17, Problem 4, Problem 2, Problem 2, Problem 6

78. Euler’s Totient Function :
    Explanation, Implementation, Problems 63, Explanation, Problems 14

79. Burnside Lemma :
    Tutorial 51, Tutorial 10, Problem 17

80. Edit/Levenshtein Distance :
    Tutorial 35, Introduction 12, Tutorial 11, Problem 10, Problem 10

81. Branch and Bound 77

82. Math for Competitive Programming 754

83. Mo’s Algorithm : Tutorial and Problem