/Algorithms_for_Competitive_Programming_in_Python

I regroup all algorithms usefull for CP contests (in Python)

Primary LanguagePython

Algorithms_for_Competitive_Programming_in_Python

The Algorithms crossed in the list below are not in this repo yet. Hopefully one day, nothing will be crossed anymore:)

Graphs

  1. Breadth First Search (BFS)
  2. Depth First Search (DFS)
  3. DFS Tree: (https://codeforces.com/blog/entry/68138)
  4. Count number of connected components
  5. Shortest Path from source to all vertices Dijkstra
  6. Shortest Path from every vertex to every other vertex Floyd Warshall
  7. Minimum Spanning tree Prim
  8. Minimum Spanning tree Kruskal
  9. Topological Sort
  10. Color a graph with 2 colors ( = make it bipartite)
  11. Johnson’s algorithm
  12. Articulation Points (or Cut Vertices) in a Graph
  13. Bridges in a graph

Dynamic Programming

  1. Longest Common Subsequence
  2. Longest Increasing Subsequence
  3. Edit Distance
  4. Minimum Partition
  5. Ways to Cover a Distance
  6. Longest Path In Matrix
  7. Subset Sum Problem - P
  8. Optimal Strategy for a Game
  9. 0-1 Knapsack Problem
  10. Assembly Line Scheduling

Searching And Sorting

  1. Binary Search
  2. Check if number x is present or not in a given sorted list
  3. Insertion Sort
  4. Quick Sort
  5. Merge Sort
  6. Count number of inversions
  7. Next Greater Element
  8. Order Statistics
  9. KMP algorithm
  10. Rabin karp
  11. Z’s algorithm
  12. Aho Corasick String Matching
  13. Counting Sort
  14. Manacher’s algorithm: Part 1, Part 2 and Part 3
  15. Query duplicates in a range
  16. Rolling Hash

Number theory and Other Mathematical

Prime Numbers and Prime Factorization

  1. Gcd (Euclid algorithm)
  2. Lcm
  3. Primality Test
  4. Set 1 (Introduction and School Method)
  5. Set 2 (Fermat Method)
  6. Set 3 (Miller–Rabin)
  7. Sieve of Eratosthenes (and other similar precomputations)
  8. Segmented Sieve
  9. Wilson’s Theorem - P
  10. Prime Factorisation
  11. Pollard’s rho algorithm

Modulo Arithmetic Algorithms

  1. Basic and Extended Euclidean algorithms
  2. Euler’s Phi Function (Totient Function)
  3. Modular Exponentiation
  4. Modular Multiplicative Inverse
  5. Chinese remainder theorem and Modulo Inverse Implementation
  6. Binomial coeficients, modulo calculation

Miscellaneous Algorithms

  1. Counting Inversions
  2. Counting Inversions using BIT
  3. logarithmic exponentiation
  4. Square root of an integer
  5. Heavy light Decomposition and this
  6. Matrix Rank
  7. Hungarian algorithm
  8. Link cut
  9. Mo’s algorithm and this
  10. Russian Peasant Multiplication
  11. Catalan Number

Geometrical and Network Flow Algorithms

  1. Convex Hull
  2. Graham Scan
  3. Line Intersection
  4. Interval Tree
  5. Matrix Exponentiation
  6. Maxflow Ford Furkerson Algo and Edmond Karp Implementation
  7. Bipartite matching
  8. Min cut
  9. Stable Marriage Problem
  10. Hopcroft–Karp Algorithm for Maximum Matching
  11. Dinic’s algo

Data Structures

  1. Heap
  2. Union Find
  3. BST
  4. Binary Indexed Tree or Fenwick tree
  5. Segment Tree (RMQ, Range Sum and Lazy Propagation)
  6. SortedList(can replace C++ set)
  7. K-D tree (See insert, minimum and delete)
  8. Union Find Disjoint Set (Cycle Detection and By Rank and Path Compression)
  9. Tries
  10. Suffix array (this, this and this)
  11. Sparse table
  12. Suffix automata
  13. Suffix automata II
  14. LCA and RMQ

Approximate sequence matching

  1. Bitap algorithm
  2. Phonetic algorithms
  3. Daitch–Mokotoff Soundex
  4. String metrics
  5. Damerau–Levenshtein distance
  6. Trigram search

Function Optimization and Root Finding

  1. Root search (bisection, secant, Newton)
  2. Newton method for minimum finding
  3. Ternary search (for unimodal function)
  4. Golden section (for unimodal function)
  5. Multivariate

Source @ http://www.geeksforgeeks.org/top-algorithms-and-data-structures-for-competitive-programming/
Idea from https://github.com/haikentcode/top10algoritms

This github repo is amazing: https://github.com/cheran-senthil/PyRival

should also have a look at David Eppstein, who has very elegant and very readable python code on algorithms. (go to Google and search: Eppstein PADS)

if you want to implement Travelling salesman problem, you should probably have a look at this nice implementation from Google: https://developers.google.com/optimization/routing/tsp