algorithms

my implementations of common algorithms and useful data structures

INDEX OF CONTENTS

1. advanced-data-structures
   1. graphs
      • BFS (breadth first search)
      • DFS (depth first search)
   2. trees
      • segment-tree
      • tries
   3. linked lists
      • floyd's cycle detection algorithm
2. backtracking
   • nqueens-backtracking
   • nqueens-branch_and_bound
   • all-paths-in-a-maze
   • sudoku-solver
3. bit-manipulation
   • generateK-SetBits (generates numbers with k bits set in their binary form)
   • powerOfTwo (finds the closest power of two to a number in both directions)
   • numberOfSetBits (counts the number of set bits in a binary number O(number of set Bits) algorithm )
4. combinatronics
   • combinations (generates combinations of a string/array)
   • permutation (generates permutations of a string/array)
   • subsets (generates all possible subsets of a string/array)
5. greedy
   • 0-1knapsack (classic 0-1 knapsack problem using George Dantzig's greedy approach)
6. numbers
   • O(sqrt(n)) primality check
   • baseconversion (convert a decimal to any base)
   • fermats-little-theorem-primality-test (primality test using fermat's little theorem. higher complexity (number of tests) gives higher accuracy)
   • fermat's integer factorization
   • Pollard Rho Integer factorization
   • largest prime factor of a (long long int) number
7. sorting
   • selectionsort
   • bubblesort
   • countsort
   • mergeSort
   • quickSort
   • radixsort
   • insertionsort

cpp-template (a template for competitions, filled with shorthands and useful macros)