You are not logged in. Please login at www.codechef.com to post your questions!

×

Data Structures and Algorithms

648
600

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, problems same as BIT, Problem, Problem/HLD is used as well/

  13. Z algorithm : Tutorial, Problem, 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. nCr % M

  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 : Code

  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

This question is marked "community wiki".

asked 31 Jul '14, 23:29

neo1tech9_7's gravatar image

5★neo1tech9_7
8.5k51537
accept rate: 19%

edited 28 Feb, 02:07

pkacprzak's gravatar image

5★pkacprzak ♦♦
65383373

25

Just a suggestion. Sort this list according to their usage. Like, the algorithms which are most used would be ranked first, then the rarely used problems.

(01 Aug '14, 15:10) thespacedude2★
2

For BIT use this tutorial: http://stackoverflow.com/questions/15439233/bitusing-a-binary-indexed-tree - way better than all other resources. And thanks for the resource.

(09 Sep '14, 22:41) travis_bickle2★
1

after spending hours reading KMP from several sites and failing to understand, i found this one very straight forward and well explaining: http://keithschwarz.com/interesting/code/?dir=knuth-morris-pratt

(03 Nov '14, 19:00) nishant20024★

@nishant2002 added :)

(10 Nov '14, 00:52) neo1tech9_75★
1
(31 Mar '15, 21:33) nisargshah953★

neo1tech9_7

In what order should I start.

(20 Jan '16, 21:53) arpit7282★

surprised that there was no mention of FFT and NTT

(09 Nov '16, 14:02) ashwanigautam3★

Some other algorithms that are not covered in the above list, @codechefofficial youtube link. https://www.youtube.com/user/codechefofficial

(07 Apr, 14:24) codedecode01114★
showing 5 of 9 show all

128 Answers:

12345 ... 13next »

30

A good initiative :)

link

answered 01 Aug '14, 05:18

its_pheonix's gravatar image

4★its_pheonix
2.3k62021
accept rate: 11%

@its_pheonix

In what order should I start.

(20 Jan '16, 21:52) arpit7282★
30

link

The above link has lesser known but useful data structures.

link

answered 07 Aug '14, 10:54

codemaster1994's gravatar image

4★codemaster1994
2.2k72018
accept rate: 0%

26

Really good work.

God Bless you and you will win IOI :)

link

answered 17 Aug '14, 11:59

tech_boy's gravatar image

3★tech_boy
1.2k41931
accept rate: 7%

More concise collection of STL... http://www.sgi.com/tech/stl/

(31 Aug '14, 14:13) tech_boy3★
3

Thanks friends .These links are really useful for newbies like us. May Allah(swt) bless and guide all those who contributed in collecting these links.

(13 Sep '14, 01:05) ahsankamal1★
17

For heavy-light decomposition - http://wcipeg.com/wiki/Heavy-light_decomposition

link

answered 07 Aug '14, 13:48

rajat_dtc's gravatar image

2★rajat_dtc
1.8k51422
accept rate: 6%

17
link

answered 12 Aug '14, 21:49

ravi0213's gravatar image

5★ravi0213
2.2k41324
accept rate: 14%

12

Take a look of this website once....Explanation of all the algorithms from different sources can be found at one place!!! http://algorithm.daqwest.com/

link

answered 05 Aug '14, 19:49

vicky002's gravatar image

1★vicky002 ♦♦
2361311
accept rate: 27%

link

answered 01 Aug '14, 00:02

ravi0213's gravatar image

5★ravi0213
2.2k41324
accept rate: 14%

Nice Initiative I would recommend http://e-maxx.ru/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)

link

answered 04 Aug '14, 02:21

johri21's gravatar image

2★johri21
436137
accept rate: 12%

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

link

answered 15 Aug '14, 14:35

gdisastery1's gravatar image

5★gdisastery1
1.9k41317
accept rate: 11%

I think stackoverflow can also be of immense help.
Really awesome effort.

link

answered 07 Aug '14, 12:42

ronakymca's gravatar image

4★ronakymca
1.1k31223
accept rate: 19%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Tags:

×1,256
×1,006
×679
×638

Asked: 31 Jul '14, 23:29

Seen: 354,793 times

Last updated: 09 May, 14:54