HatchLib

Hatch Alpha algorithm library

Contents

• dynamic programming

  • hatchlib.dynamic.lcs(str1,str2)
    longest common sequence
    returns the longest sequence contained in both strings
    lcs('doom','poof') returns 'oo'

• encoding

  • hatchlib.encoding.huffman(s)
    huffman coding
    returns the huffman-encoded dictionary of s
huffman('test') returns {'e': '00','s': '01','t': '1'}

• factorization

  • hatchlib.factorize.fermat(n)
    fermat algorithm
    returns the prime factors of a number
    fermat(15) returns [3,5]

  • hatchlib.factorize.pollard_rho(x)
    Pollard's rho algorithm
    returns the prime factors of a number
    pollard_rho(10) returns [2,5]

  • hatchlib.factorize.trial_div(n)
    trial division
    return naively derived prime factors
    trial_div(20) returns [2,5]

• math

  • hatchlib.math.lcm(a,b)
    lowest common multiple
    return the lowest multiple shared by a and b
lcm(12,15) returns 3
  • hatchlib.math.euclid(a,b)
    euclidian algorithm
    returns gcd of a and b
euclid(12,16) returns 4

  • hatchlib.math.coprime(*n)
    unlimited argument coprime check
    checks if all arguments are coprime
    coprime(5,11,21) returns True

  • hatchlib.math.isprime(n)
    check if a number is prime
    isprime(17) returns True

  • sequence

    • hatchlib.math.sequence.hailstone(n)
      hailstone sequence
      returns a hailstone sequence beginning at n
      hailstone(13) returns [13,40,20,10,5,16,8,4,2,1]

    • hatchlib.math.sequence.nth_fib(n)
      nth fibonacci number
      returns the nth number of the fibonacci sequence
      nth_fib(11) returns 89

    • hatchlib.math.sequence.fibonacci(n)
      fibonacci sequence
      generate n terms of the fibonacci sequence fibonacci(10) returns [1,1,2,3,5,8,13,21,34,55,89]

  • sieve

    • hatchlib.math.sieve.erat(lim)
      Eratosthenes' sieve
      generate primes with Eratosthenes' sieve up to lim
erat(30) returns [2,3,5,7,11,13,17,19,23,29]

    • hatchlib.math.sieve.atkin(lim)
      Atkin's sieve
      generate primes with Atkin's sieve up to lim
atkin(30) returns [2,3,5,7,11,13,17,19,23,29]

• search

  • hatchlib.search.binary
    binary search
    return 0 or 1 if key is found in either position, else return False
binary([1,2,3,4],3) returns False

  • hatchlib.search.kmp(s,sub)
    kmp search
    return indicies of sub in s
kmp('test123','123') returns [4]

  • hatchlib.search.rabin_karp(s,sub)
    Rabin-Karp search
    returns indicies of sub in s
rabin_karp('test1231','1') returns [4,7]
    

• shuffle

  • hatchlib.shuffle.knuth(seq)
    knuth algorithm
    shuffles seq
knuth([1,2,3,4,5]) retruns [1, 2, 5, 3, 4], as an example

• sort

  • hatchlib.sort.cocktail(seq)
    cocktail sort
    sorts seq in ascending order
    cocktail([2,4,1,6,3,5]) returns [1,2,3,4,5,6]

  • hatchlib.sort.gnome(seq)
    gnome sort
    sorts seq in ascending order
    gnome([3,5,2,6,1,4]) returns [1,2,3,4,5,6]

  • hatchlib.sort.insertion(seq)
    insertion sort sorts seq in ascending order
    insertion([3,5,2,1,4,6]) returns [1,2,3,4,5,6]

  • hatchlib.sort.quicksort(seq)
    quicksort algorithm
    sorts seq in ascending order
    quicksort([3, 6, 1, 5, 2, 4]) returns [1,2,3,4,5,6]

  • hatchlib.sort.selection(seq)
    selection sort
    sorts seq in ascending order
    selection([4,3,6,1,2,5]) returns [1,2,3,4,5,6]

Notes to students

Install with the following command in c9 terminal:

 sudo pip install hatchlib

and update with:

 sudo pip install -U hatchlib

Credit due to:

• https://github.com/nryoung/
• https://rosettacode.org/