[Algorithms] Binary Search Tree (BST)

          parent
            / \
          /     \
        left    right

Binary search trees stores information (keys) holding some constraint. Each node holds some value. A left node holds value less than or equal to the parent node and right node holds value greater than parent node.

Motivation:
Interval scheduling problems can be solved efficiently with binary search trees. We will need to traverse left and right to see where a given interval should fit into. If that place is already taken or being overlapped by an existing interval, we discard the interval otherwise we insert it.

BST operations
0. insert : insert a key to the tree if the key does not already exist.
1. search : check if a key is present in the tree or not.
2. delete : delete a key if exist in the tree.

0. Insert
def insert (node, key):
  if node == null:
    return new Node(key)
  else if node.key == key:
    return node
  else if (node.key > key):
    node.left = insert(node.left, key)
  else:
    node.right = insert(node.right, key)

1. Search
def search(node, key):
  if node == null:
    return false
  if node.key == key:
    return true
  else if node.key > key:
    return search(node.left, key)
  else
    return search(node.right, key)

2. delete:
def delete(node, key):
  if node == null:
    return node
  if node.key == key:
    if node.left == null
      return node.right
    else if node.left.right == null
      return node.left
    else
      new_node = get_right_most(node.left)
      delete_right_most(node.left)
      new_node.left = node.left
      new_node.right = node.right
      return new_node
  else if node.key > key:
     node.left = delete(node.left, key)
  else
    node.right =  delete(node.right, key)
  return node

Augmented Binary Tree
When a binary tree holds information along with keys, it is called augmented binary tree. A common augmented BST is storing node counts of a subtree.

We will be discussing about the following binary search trees
0. avl tree
1 red-black tree
2. b-tree

AVL Tree
Self balancing binary trees. Balances herself using "rotate" operation. There can be log n number of rotations.
This tree is an augmented data structure. Every node contains the following information
  height of subtree
  left child
  right child
 
property:
  at any node, let h_left and h_right are left sub tree height and right sub tree height.
    |h_left - h_right| <= 1
  number of nodes, at worst case, N_h = 1 + N_(h-1) + N_(h-2) [because in best case both the left and right will be balanced]
  1 + N_(h-1) + N_(h-2) > 1 + 2 * N_(h-2) > 2 * N_(h-2)
  N_h > 2 * N(h-2)
  so number of nodes N = 2 ^ (h/2) => h = O(logn)

Rotation:
      x           <- left rotate                 y
    /   \         right rotate ->              /   \
   A     y                                    x     C
        / \                                  / \
       B   C                                A   B

in order traversal produces A x B y C for both the trees.

insert:
  simple bst insert
  fix avl property broken at any point of insertion. move up.

while insertion, the following cases can occur where AVL tree properties are broken at node x.
0. Right child is right heavy.

         x (h)          
       /   \      
(h-3) A     y (h-1)                                  
           / \                                
   (h-3)  B   C (h-2)                              

a left rotate against right child, y fixes the properties.

        y (h-1)
       / \
(h-2) x   C (h-2)
     / \
    A   B  [both A and B have h-3 height]

1. Right child is left heavy
                      x (h)          
                    /   \      
            (h-3) A     y (h-1)                                  
                       / \                                
               (h-2)  z   C (h-3)                              
                     / \
              (h-3) B   D (h-4)

              do a right rotate with respect to y

                  x (h)
                /   \
        (h-3)  A     z (h-1)
                    / \
            (h-3)  B   y (h-2)
                      / \
               (h-4) D   C (h-3)

        now we have the same situation as case 0. do as we did in case 0.

Mirror situation occurs for left heaviness.

[Algorithms] String search algorithms

String Matching Algorithms

problem: given two strings, s and t. does s occurs as a substring of t?

naive approach:

def substringSearch(t, s):
  for i in range(0..len(t)):
    matched = true
    for j in range(0..len(s)):
      if t[i+j] != s[j]:
        matched = false
        break
    if matched:
      return "String occurs"
  return "does not occur"

Runtime: O(m * n)

Rabin-Karp Algorithm:

def subStringSearch(t, s):
  len_s = len(s)
  pattern_hash = get_hash_val(s, 0, len_s)
  substr_hash = -1
  for i in range(0..len(t)-len(s)):
    substr_hash = get_hash(t, i, i+len_s, substr_hash)
    if substr_hash == pattern_hash:
      if t[i:i+len_s].matches(s):
        return true
  return false

def get_hash_val(s, start, end, prev_hash=-1):
  size_of_alphabet = SIZE_OF_ASCII_CHARS
  lowest_ascii_char = 'a'
  hash_val = 0
  if prev_hash == -1:
    for i in range(start..end):
      hash_val *= size_of_alphabet
      hash_val += (s[i] - lowest_ascii_char)
  else:
      start_char = s[start]
      hash_val = prev_hash * size_of_alphabet + (s[end] - lowest_ascii_char) - start_char * (size_of_alphabet ^ (end-start+1))

Analysis:
  if prev_hash = -1, hashing takes O(s)
  inside the for loop, hashing happens in O(1) time
  the hash function is designed in such a way that if two hash value equals then they are the same string.
  So for good hash function, O(n)
  for bad hash function O(m * n)

[Algorithms] Perfect Hashing: Guarantying constant time operation for hash function

For any hash function, it is possible to find a set of keys that will result O(n) time in search. In this article, I will talk about a scenario when we already know the keys, and we want to do the look up the keys in O(1) time even for the worst case.

Perfect Hashing Scheme:
We need two level hashing. In first level, we have n slots in hash table T where n = number of keys.
At level1, we use one hash function h_l1. Each slot of T contains 3 things
[number of items, hash function, pointer to array holding keys at level 2]

for any slot in T, size of key array in level 2 = (number of keys in level 2) ^ 2.

Index     Level-1         Level-2
0         [2 | 40 | ->]   [- | 40 | 37 | 27 ]
1         [1 | 01 | ->]   [- | 3 ]
2         [1 | 23 | ->]   [- | 25 ]
3         [0 | 19 | ->]   [ ]
4         [1 | 44 | ->]   [ 127 ]

at 0 index, level-1 slot has [2 | 40 | ->] this means, level-2 has 2 elements. So level-2 hash table will have size 2 ^ 2 = 4. the value 40 means universal hash function number 40, h_40 will be used to hash in level 2.

In level-1 there will be collision. We need to guarantee that in level-2 we can find hash functions that won't collide for m_i number of keys.

Proof:
x is a random variable that represents number of collisions in level-2 for a slot i. in i, level-2 has m_i number of keys. then hash table has size (m_i) ^ 2 slots. since, a universal hash function will be used probability of any two keys collide would be 1 / (m_i) ^ 2.

E[x] = sum (1/(m_i ^ 2)) for all keys x and y for given set of keys in level-2 at slot i.
we can make n Choose 2 combinations, so
E[x] = (m_i C 2) * (1/(m_i ^ 2)) < 1 / 2
E[x] <= 1/2

from Markov Inequality, P{x >= t} <= E[x] / t
P{x >= 1} <= E[x] / 2 <= 1/2    [0]
Equation [0], basically says, if we use universal hashing, at least half the cases there will be no collision. So randomly picking some hash functions from universal hashing should quickly yield a good hash function that does not do any collision for the given keys.

Space:
let x is a random variable denoting total space in level-2, then x = sum(n_i ^ 2), where n_0 + n_1 + ... + n_m  = n [n keys and m slots]
E[space] = n + E[x] = O(n)

Reference:
0. MIT OCW 6.046 : Introduction to Algorithms

[Algorithms] Keeping operations on a Hash table constant

In this article, I will discuss how to keep search operation's run time constant in a hash data structure.

Let the table T has m slots. If h is a universal hash function then, for key x and y where x != y
probability(x) = h(y)) = 1 / m
if the number of keys = n, on average every slot will have n / m keys. this is also known as load factor, alpha. So, alpha = n / m.
so each slot will have on average alpha number of keys. So expected number of searches would be O(1 + alpha).
To keep searching constant, we need to keep alpha constant.

As number of keys, n grows alpha starts increasing. If we want to keep alpha ~ 1, we need to increase size of our table. If we can handle
resizing of the table in constant time, we will be able to do operations in hash table in constant time.

Idea is If alpha hits a certain threshold, then we double size of T. This way insertion will be in amortized O(1) time.

Example: Lets say initially T has size m = 1. Insertion has cost O(1) for a hash table as all it does is insert the element at the head.
When we double the table, the cost of insertion goes to O(n) from 1. Fortunately, this does not happen very often, which makes average insertion operation a O(n) time operation. Below I have shown the key number and the order of the operation. When there is only one key, the insertion time is 1. If we add another key, we need to increase size of our table and then copy all the data from old table to new table. This cause O(n) time.

Key#     cost
1             1
2             2
3             1
4             4
5             1
6             1
7             1
8             8
9             1
10           1
11           1
12           1
13           1
14           1
15           1
-----------------
total cost for n insertion  =  (1+1+1..) + (2+4+8) = O(n)  # as the bigger value gets scarce as you keep doubling the table
amortized cost = avg cost per insertion = O(n/n) = O(1)

for n = 1000, the following Haskel code snippet counts average cost of insert operation.
a = sum([2 ^ x | x <- [0..100], 2 ^ x < 1000] ++ take 1000 (repeat 1)) `div` 1000
print a # prints 2

Deletion
Table size = n, number of keys = k. Half the table size when k = n / 4

References:
0. MIT OCW 6.006 Introduction to Algortihms
1. MIT OCW 6.046J Introduction to Algorithms

Quick Haskel

I have been documenting the  concepts and apis of the programming language Haskel. This document has examples of various constructs of the Haskel programming language. It is a live document. Until I complete the contents of [0], I will be updating this document.

function declaration
f x = x + 2   # f(x) = x + 2

conditional
abs x = if x < 0 (-1) * x else x  # an if should always have an else

list
list contains element of the same type.
let myList = [1,2,3]
strings are considered as lists too. "abc" is equivalent to ['a', 'b', 'c']

append to last [slower operation if the first list is big]
myList ++ [5, 6]

append single element to first
7 : myList
[1, 2, 3] is equivalent to 1:2:3:[]

access list element
myList !! 2     # access 2nd element of the list

list comparison
rule: 2 lists can be compared if the elements can be compared. Nonempty list is greater than empty list. element by element is done from start of the list until a match found or one/both of the lists ends.
operator: <, <=, >=, >, ==
a = [1,2,3], b = [4,5,6]
a < b # False

list of list
a = [[], [1,2,3], [4]]

list operations
[<head><......tail......>]
[<.......init.....><last>]
operations does not have side effect meaning they don't modify the list.
head [1,2,3,4,5] #1
tail [1,2,3,4,5] #[2,3,4,5]
init [1,2,3,4,5] #[1,2,3,4]
last [1,2,3,4,5] #5
length [1,2,3] # 3
null [] # True
null [1] # false
reverse [1,2,3] # [3,2,1]
take 1 [7,2,3] # [7]
drop 1 [7,2,3] #[2,3]
maximum [2, 4, 5, 1] # 5
minimum [2, 3, 1, 5] # 1
sum [1, 2, 3] # 6
product [1, 2, 3, 4] # 24
elem 7 [1, 6, 7] # True, 7 belongs to the list
[1..5] #[1,2,3,4,5]
['a'..'d'] # ['a', 'b', 'c', 'd']
[5,4..1] #[5,4,3,2,1]
cycle[1,2,3] #produces infinite list [1,2,3,1,2,3,1,2,3,...infinite]
repeat 5 # [5,5,5,5,5,5,5....infinite size]
repeat [1] # [[1], [1], [1], [1], [1] ... infinite size]
replicate 4 2 # [2, 2, 2, 2]

list comprehension
[x * 2 | x <- [0..5]]  # all x * 2 s such that x belongs to the set [0, 1, 2, 3, 4, 5]
[x * 2 | x <- [0..5], x > 5] # multiple predicate
evenOdd xs = [ if x `mod` 2 == 0 then 0 else 1 | x <- xs ] # function evenOdd takes a list xs and returns a list of 0s and 1s
usage: evenOdd [0..10] # [0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
[x + y | x <- [0..5], y <- [0..3]] # for all x and y in the sets, generates a list that has the value x + y
length' ls = sum [1 | _ <- ls] # generate a list that has 1 for each element of ls, then sum up all the 1s

Tuple
stores heterogenous typed elements. size is fixed.
(1, 1.1, 'a', "saif")
tuple types are defined by the number of elements in it. a list can hold only same typed elements. thus,
[(1,2), (2, 3), (1,2,3)] causes ERROR
[(1, 2), ('a', 1)] also causes ERROR

Pairs
(1, 3)
fst (1,3) # 1
snd (1,3) # 3
zip ['a', 'b', 'c'] ['x', 'y', 'z'] # [('a','x'),('b','y'),('c','z')]
zip "abc" [1..] # [('a',1),('b',2),('c',3)] notice how only 3 elements are taken from the infinite set

## Type ##
Type is fixed.
ghci command :t shows type of a variable or function.
function type
sum :: Int -> Int -> Int
sum a b =  a + b

common types
Int : bounded by underlying system
Integer : unbounded
Float : real number with single precision
Double : real number with double precision
Bool : boolean type
Char : a Unicode character

Type Class
A type class encloses one or more types.
A type can be member of one more type classes.

ghci command. :t (==)
(==) :: (Eq a) => a -> a -> Bool
How to read. (==) takes 2 argument of type class Eq and returns a Bool type.

Eq
applicable function: ==, /= (not equal)

Ord
values of Ord type can be sorted.
functions to apply : >, >=, <, <=.
comparator function returns GT, LT or EQ.

Show
the value can be presented as a string.
function to apply on this type: show # show 3 => "3"

Read
from string, raw type can be formed
applicable function: read
ex: add (read "3") + 3  # 6
read function need enough hint to know which raw type to produce. for example,
this does not work, read "3"
but read "3" + 3 works, because read knows "3" to be converted to Int
the following example works similar to type casting (according to me)
read "3" :: Int # specifically specify we need 3 to be Int.

more examples:
read "[1, 2, 3]" :: [Int]  # [1,2,3]
read "(2, 'a')" :: (Int , Char) # (2, 'a')
[read "True", True, False, True]

Enum
sequentially enumerable values.
applicable functions: succ, pred

Bounded
has an upper and lower bound

Num
values act like numbers

Floating
applicable functions: sin cos
Enclosing type: Float, Double

Integral
enclosing type: Int, Integer

## Syntax in Functions ##
Pattern matching: choosing a function based on input parameters. Pattern matching works very similar to if else construct.
citizen :: String -> String
citizen "BD" = "Bangladeshi"
citizen "USA" = "American"
citizen x = "Unknown citizen"

line 0, is function input and output type declaration. line 1, says what to do if input = "BD", so on and so forth.

can be used to define base case.
fibonacci :: Int -> Int
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n = fibonacci(n-1) + fibonacci(n-2)

If the pattern matching does not contain all the possibilities of input, interpreter will throw an exception.

vector_add :: (Double, Double) -> (Double, Double) -> (Double, Double)
vector_add a b = (fst a + fst b, snd a + snd b)
another way to write
vector_add (x1, y1) (x2, y2) = (x1 + x2, y1 + y2)

Usage of '_'
fst' :: (a, b, c) -> a
fst' (a, _, _) = a

head' :: [a] -> a
head' (a:_) = a

As pattern break up input in parts, also gives a way to access the whole. can be applied on list only.
shead :: [Int] -> Int
shead whole@(frst : rest) = frst

Guards
bmiTell :: Double -> String
bmiTell bmi
  | bmi <= 18.5 = "underweight"
  | bmi <= 25.0 = "normal wieght"
  | bmi <= 30.0 = "fat"
  | otherwise = "unhealthy fat"

guard syntax | boolean-expression = expression-to-be-evaluated

where
clause. provides variable like functionality of imperative programming language.

bmiTell w h
  | bmi <= skinny = "you are fine"
  | bmi <= fat = "you are not fine"
  where bmi = w / h ^ 2
        skinny = 18.5
        fat = 23.5

forming tuple and accessing it
initials :: String -> String -> String
initials first last = [f] ++ "." ++ [l] ++ "."
  where (f:_) = first
        (l:_) = last
where to pattern match
desList :: [a] -> String
desList ls = "the list is " ++ check ls
        where check [] = "empty"
              check [x] = "singleton"
              check xs = "a longer list"

Let
let lets you create an expression that generates a value. let are local in scope.
cylinder :: Double -> Double -> Double
cylinder r h =
  let sideArea = 2 * pi * r * h
      topArea = pi * r ^ 2
  in sideArea + 2 * topArea

pattern: let <variable binding> in <expression>
let square x = x * x in (square 2, square 3, square 4)

list comprehension
calcBMI xs = [bmi | (w, h) <- xs, let bmi = w / h ^ 2, bmi > 25.0]
the value bound through let is visible before '|' and after the let

Case expression
syntax:
case expression of pattern -> result
                   pattern -> result
                   pattern -> result
                   pattern -> result
example:
sum' :: [Int] -> Int
sum' xs = case xs of [] -> error "empty list"
                     _ -> sum xs

case can be used inside a function too.
describeList ::[a] -> String
describeList ls = "The list is " ++ case ls of [] -> "empty"
                                               [x] -> "singleton"
                                               xs -> "a longer list"

Reference:

[0] http://learnyouahaskell.com/

Construction and properties of Universal Hash function

Construction of Universal Hash function
Let m is a prime.
k is the key and decomposed in m-base number system with (r + 1) digits,
k = <k_0, k_1, k_2, ..., k_r> where 0 <= k_i <= m-1
take a random number a with r digits, such that
a = <a_0, a_1, a_2, ..., a_r> where a_i is chosen randomly and 0 <= a_i <= m-1

a universal random function, h(k) = sum(k_i * a_i) mod m

size of the set of universal hash functions, |H| = (m ^ (r+1)) [each a_i can be chosen from m choices]

Theorem: for h element_of H and for x != y, probability of collision = 1 / m
let x = <x_0, x_1, ..., x_r>, y = <y_0, y_1, ..., y_r> and x != y
x and y differ at least at 1 digit. how many h element_of H collides for x and y?
let, a = <a_0, a_1, ..., a_r> for h. if for h, x and y collides then
h(x) = h(y)
sum(a_i * x_i) (=) sum(a_i * y_i)    (mod m)
=> sum(a_i * (x_i - y_i)) (=) 0 (mod m)
=> a_0 * (x_0 - y_0) (=) -(sum(a_i * (x_i - y_i)))      (mod m)
=> a_0 (=) -(sum(a_i * (x_i - y_i))) * inverse(x_0 - y_0)     (mod m)     [Eqn. 0]

the [Eqn. 0] says to collide, we can choose any a_1 to a_r but the choice of a_0 is fixed by [Eqn. 0]. for all other choices of a_0 there will be no collision.
total possible ways to construct H, |H| = m ^ (r+1)
we have 1 option for choice of a_0 and m choices for all other r digits. so, number of collision = 1 * m * m * ... * m = m ^ r = |H| / m
for x != y, probability of collision = (cases when collision occurs) / (total number of cases) = (m ^ r) / (m ^ (r+1)) = 1 / m

Theorem: if there are n keys, then for a key x, E[numboer of collision with x] <= n / m
let C_x be a random variable denoting total number of collisions in keys in Table T with x, and C_xy is the indicator random variable
where, C_xy = 0 if no collision for x and y, and C_xy = 1 if there is collision between x and y.

C_xy = sum(C_xy) for all y in T - {x}
so, E[C_xy] = E(sum(C_xy)) = sum E(C_xy) = sum (1/m) = (n - 1) / m

Summary: Property of Universal Hashing
Let, U is the universe of keys and let H be a finite collection of has functions mapping u to {0, 1, ...., m-1}.

H is universal if for all h element_of H, and for all x and y element_of U, where x != y,
Probability(h(x) == h(y)) = 1 / m.

total number of cases where collision happens, for h and for all pair of different keys = |H| / m

Reference:
[0] https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-8-universal-hashing-perfect-hashing/

Good Hash Functions

Let m = number of slot in the hash table. k is the key we want to hash. We will be discussing some hashing mechanisms.

Division method
A well-known hash method is doing mod
h(k) = k mod m
We need to be careful with choice of m.

m should not have small divisor. For example, if d = 2 is a divisor of m, and the keys are all even,
then the hash function will always choose even slots and all the odd slots will be empty.

we want the h(k) depends on all the bits of k. m should not be a power of 2.
lets say m = 2 ^ k. then the hash value will not depend on all the bits of the key, k.

 001 100 111 mod 2 ^ 3 = 111 (the last 3 bits)
 in general k mod (2 ^ t) = t lower bits of k

pick m, such that it's a prime and not close to power of 2 or 10.

Division method is simple, but division takes a lot of cycles.

Multiplication method
Lets assume the word size of the computer = w.
let, m = 2 ^ r
h(k) = ((A * k) mod (2 ^ w)) >> (w - r), where A is odd, 2 ^ (w-1) < A < 2 ^ (w). A is not close to power of 2.

How it works:
A has w bits, k has w bits. A * k has 2w bits.
A * k mod (2 ^ w) has lower w bits of A * k.
((A * k) mod (2 ^ w)) >> (w - r) gives r bits slot result.

When multiplication is done, there is great mixing of bits of k.
m = 2 ^ 3 = 1000
k = 1001
A = 5 = 101
w = 4
A * k
                        1001
                        0101
-------------------------------
                        1001
                      00000
                    100100
                  0000000
--------------------------------
                 00101101 (hash result will be 110)

notice how the bits in the middle are nicely mixed with many other bits. this is one of the reasons the multiplication method works nicely.
the mod and shift operations are very fast, as it only discards some digits. that is one of the reasons it is faster than the division method.

Reference:
[0] https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-8-hashing-with-chaining/
[1] https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-7-hashing-hash-functions/