Algorithms

Algorithms stuff created on my own, grabbed from some resources and all of them are putted here.

Methodology

This repository of ready-to-use algorithms follows a methodology that makes algorithms easy to find, extend and copy to your existing code. Every algorithm that is here needs to be:

• In separated file need to work sreperatly, without using any sources or algorithms from another one.
• Easy to copy and paste into your own code.
• Is supposed to be fast, not necessarily readable

Note
Usefull for creating memory-efficent algorithms are sizes of each types in C++, they are listed in sizes file

Tasks

List of currently implemented algorithms:

• Prefix sums Answers: O(1)

  • 2d sums O(n * m)
  • Normal sums O(n)
  • Sums on overlapping intervals O(n)

• Math

  • Is a prime number O(sqrt2(n))
  • Euklides NWD O(log2(max(n, k)))
  • Euklides NWW O(log2(max(n, k)))
  • Advenced euklides O(log2(max(n, k)))
  • The sieve of Eratosthenes O(n log2(log2(n)))
  • Number of dividers
  • Remembered factorial
  • Permutations

• Trees O(log2(n))

  • Range-Range Tree
  • Point-to-Range Tree
  • Range-to-Point Tree

• Graphs

  • Dijkstra algorithm O(m log2(n))
  • BFS for:
    • Graph O(n+m)
    • Grid O(n*m)
  • DFS for:
    • Graph: O(n+m)
    • Grid O(n*m)

• Sparses

  • Range Minimum Queries O(n log n) O(1)
  • Range Sum Queries (is simmilar to prefix sums but much slower)

• Other

  • Caterpillar algorithm O(2 * n)
  • Merge sort O(n log n)
  • Binary Search O(log2(n))
  • Bubble sort O(n^2)

Credits

Thanks for help from various internet sources including software engineering forums and CpAlgorithms