Skip to content

Latest commit

 

History

History
195 lines (138 loc) · 6.19 KB

README.md

File metadata and controls

195 lines (138 loc) · 6.19 KB
Raw

CodeLibrary

A storage for the most commonly used algorithms and data structures.

Please note that we are currently working to make this library as usefull as possible, by adding kind of readme file to every code, which contains important pieces of information such as detailed instructions how to use it, what is the input/output and some significant assumptions we made during the process of implementation. We are also providing information about the problems (usually from spoj.com and spoj.pl) solved by explicit or implicit (i.e. some easy modification) usage of a particular algo.

You may consider it as a spoiler in some case, so be aware that our intention is to deliver you a confirmation of correctness of a particular implementation, not a detailed solution.

However in early development some of the codes may be flaged as [UNTESTED] just to inform you, that they might have a nonzero probability of failing in some cases :-) Still we are doing our best to avoid that uncertainity.

Table of contents:

###Graph algorithms

  1. Breadth First Search
  2. Breadth First Search on grid
  3. Depth First Search
  4. Depth First Search on grid
  5. Maximal Flow - Dinic algorithm
  6. Maximal Matching - Hopcroft-Karp algorithm
  7. Minimal Spanning Tree - Kruskal algorithm
  8. Strongly Connected Components
  9. Shortest Paths - Bellman-Ford algorithm
  10. Shortest Paths - Dijkstra algorithm
  11. Shortest Paths - Floyd-Warshall algorithm
  12. Topological sort using DFS
  13. Topological sort using elimination

###Sorting algorithms

  1. HeapSort
  2. MergeSort
  3. QuickSort

###Numerical algorithms

###Combinatorical algorithms

  1. Counting inversions - MergeSort

###Text algorithms

  1. Finding a pattern - KMP
  2. Radius of a palindrome - Manacher's algorithm

###Cryptographic algorithms

###Dynamic approach algorithms

###Computentional geometry

###Data structures

  1. Dictionary Tree
###Libraries

In progress:

###Graph algorithms

  1. Articulation points and bridges
  2. Eulerian traversal
  3. Hamiltonian traversal
  4. Traveling Salesman Problem
  5. Minimal Spanning Tree - Prim algorithm
  6. Lowest Common Ancestor - Trajan algorithm
  7. Some connectivity algos

###Sorting algorithms

  1. InsertionSort
  2. SelectSort
  3. BubbleSort

###Numerical algorithms

  1. Basic Euclidean algorithm
  2. Extended Euclidean algorithm - diofantic equations
  3. Factorisation
  4. Modular Inverse
  5. Basic Sieve of Eratosthenes
  6. Segmented Sieve of Eratosthenes
  7. Newton's Symbol
  8. Sign of permutation
  9. Basic Sieve of Eratosthenes
  10. Basic Sieve of Eratosthenes
  11. Some generation algorithms (including De Brujin's sequences)

###Text algorithms

  1. KMP 2D
  2. Cyclic equality

###Cryptographic algorithms

  1. Basic Caesar
  2. Playfair
  3. Vigenere

###Dynamic approach algorithms

  1. 0-1 Knapsack Problem
  2. Bounded Knapsack Problem
  3. Unbounded Knapsack Problem
  4. Longest common subsequence
  5. String distance
  6. Longest increasing subsequence
  7. And moar

###Computentional geometry

  1. Convex Hull
  2. Hell lot of things

###Data structures

  1. Static list
  2. Static queue
  3. Static stack
  4. Static heap
  5. Static tree
  6. Dynamic list
  7. Dynamic queue
  8. Dynamic stack
  9. Dynamic heap
  10. Dynamic tree
  11. Binary Search Tree
  12. Red-Black Tree
  13. AVL Tree
  14. Segment Tree
  15. Binary Indexed Tree
  16. Statistic Tree
  17. Disjoint Set Forest

###Libraries

  1. BigNums
  2. Matrix
  3. Complex Numbers
  4. Fractions

AND MAYBE SOME SIMPLEX!!!1111oneone :D:D:D:D:D:D