Algorithms-Code-Library

Algorithms-Code-Library

C++ Implementation of variety of Algorithms and some mush have cheetsheets for CS Students.

Cheet Sheets

Data Structure

In no particular order,

- Binary Indexed tree (BIT)
- Heavy Light Decomposition (HLD)
- Histrogram
- LCA
- RMQ
- trie

Geometry

In no particular order,

- CircleSegmentTetrahedron
- Closest Pair
- ConvexHull
- ConvexHull GrahamScan 
- ConvexHull MonotoneChain
- Parametric Geometry routine
- Line segment intersection
- Ray casting algorithm (PointInPolygon)
- Rotate point
- Tangent of line

Graph

In no particular order, - Stoer Wagner all pair Min Cut - Articulation Point - Bellman Ford - BiConnected Component - Bridge - Disjoint Set - Eular Circuit - Hungerian Algorithm - Max Weighted Bi-partite Matching - MaxFlow Dinic - Maximum Bipertite Matching - Mincost Max Flow - Minimum Expression - Dinitz - Dinitz With EdgeList - Stable marrige problem - Strongly Connected Component - Tarjans Off line LCA - manacher

Matrix & Numeric

In no particular order,

- Big float (C++ library)
- BigInt
- FFT
- Faussian Elimination
- matrix Exponentiation

Number theory and Math

In no particular order,

- ExtendedEuclidMOdInverse
- Hn
- LinearDiphontine
- Number Theory Part 1.pdf - Good colelction of Number theoric discussion.
- NumberTheory Part 2.pdf - Good colelction of Number theoric discussion.
- PollardRho
- SegmentedSieve
- ShankBabyStepGiantStep
- Sieve
- josepheous
- ncr

Searching

- Ternary Search

String

- Aho Chorasik
- KMP
- Hashing
- suffix-array.pdf - Good discussion of suffix-array
- Suffix array code.

IO

- Fast read C++

Collected Library

  • Stanford University ACM Team Notebook : Outdated, maybe helpful for mid-level/above mid-level problem solver.
    • Combinatorial optimization1.
      1. Sparse max-flow (C++)
      2. Min-cost max-flow (C++)
      3. Push-relabel max-flow (C++)
      4. Min-cost matching (C++)
      5. Max bipartite matching (C++)
      6. Global min cut (C++)
      7. Graph cut inference (C++)
    • Geometry
      1. Convex hull (C++)
      2. Miscellaneous geometry (C++)
      3. Java geometry (Java)
      4. 3D geometry (Java)
      5. Slow Delaunay triangulation (C++)
    • Numerical algorithms
      1. Number theoretic algorithms (modular, Chinese remainder, linear Diophantine) (C++)
      2. Systems of linear equations, matrix inverse, determinant (C++)
      3. Reduced row echelon form, matrix rank (C++)
      4. Fast Fourier transform (C++)
      5. Simplex algorithm (C++)
    • Graph algorithms
      1. Fast Dijkstra’s algorithm (C++)
      2. Strongly connected components ©
      3. Eulerian Path (C++)
    • Data structures
      1. Suffix arrays (C++)
      2. Binary Indexed Tree
      3. Union-Find Set (C/C++)
      4. KD-tree (C++)
      5. Lazy Segment Tree (Java)
      6. Lowest Common Ancestor (C++)
    • Miscellaneous
      1. Longest increasing subsequence (C++)
      2. Dates (C++)
      3. Regular expressions (Java)
      4. Prime numbers (C++)
      5. C++ input/output
      6. Knuth-Morris-Pratt (C++)
    • Stavropol SU : Extremely outdated, but worth to look at.
      • vimrc
      • Java template
      • Combinatorics
      • Number Theory
      • String Algorithms
      • Min-cost max-flow
      • Graph Theory
      • Games
      • Geometry
      • Math
      • Data Structures
      • Miscellanious 13FFT

Special Thanks: My trainer Tarif Ezaz and my friend Mohammad Abdullah Matin Khan Zarzis to whom I learned to think.

I also want to mention some of the other special names for their tremendous support. Nafis Ahmed, Mohammad Samiul Islam, Zobayer Hasan, Forhad Ahmed and Leonardo Boshell

NOTE : I don’t claim all of the soutions to be mine. While I was solving the problems, I took help from different peoples and see other people’s code for many problems. In Fact most of the coder here is collected. But I never submit any code without my complete understanding. I suugest those who will be following the repo to do so. Pasting code to online judges won’t take you any further except frustration.

Avatar
M Saiful Bari
Ph.D. Candidate

Computer Science enthusiast working in deep learning, natural language processing.