/algo

Implementation of a few algorithms

Primary LanguageHaskell

Collection of a few non trivial algorithms

Primes

Linear Sieve

David Gries, Jayadev Misra - A Linear Sieve Algorithm for Finding Prime Numbers

  • Linear Sieve Segfaults for n > 1666680 (we reach a point where int is not sufficient for storing the numbers). I should only use this implementation for numbers less than 10^6.
  • a simple adaptation of linear sieve to get the smallest prime factor of a number.
  • Implemented lisp version.

Graphs

Minimum Spanning Tree

Boruvka

Traversal

./graph-traversal.org

Trees

Fenwick Tree

A data structure for O(log n) prefix sums and updates of a array.