Some Notes of Introduction to AlgorithmPermalink

Fiboniacci NumberPermalink

$RunningTime=\theta \left({\log }_2\right(n\left)\right)$

Order StatisticsPermalink

Given n elements in an array, find $k^{th}$ smallest element.

• Quick Select
  • Expected running time $\theta \left(n\right)$
  • Worse case $\theta \left(n^2\right)$
• Worse-case linear time order statistics

  Select(i, n)
  1. Divide n elements into [n/5] groups of 5 elements each. Find the median of each
  group. O(n)
  2. Recurrsively select the medium x of the [n/5] group medians. T(n/5)
  3. Partition with x as pivot, let k = rank(x). O(n)
  4. if i==k then return x
    if i<k then recurrsively select ith smallest element in left part
    else then recurrsively select (i-k)th smallest element in upper part
  

Hash FunctionsPermalink

Division MethodPermalink

$h\left(k\right)=kmodm$

pick $m$ to be prime and not too close to power of $2$ or $10$.

Multiplication MethodPermalink

$h\left(k\right)$ $=$ $A\cdot k$ $mod$ $2^w$ » $(w-r)$, $Aodd\wedge 2^{w-1}$ < $A$ < $2^w$

Universal HashingPermalink

Let $u$ be a universe of keys, and let $H$ be a finite colleciton of hash functions mapping $U$ to {$0,1,\dots ,m-1$}.

$H$ is $universal$ if $\forall x,y\in U,x\ne y$

i.e. if $h$ is chosen randomly from $H$, the probability of collision between $x$ and $y$ is $1/m$.

Perfect HashingPermalink

Given $n$ keys, construct a static hash table of size $m=O\left(n\right)$ such that searching takes $O\left(1\right)$ time in the worst case.

Idea: 2 level scheme with universal hashing at both levels and NO collisions at level 2.

if $n_i$ items that hashes to level 1 slot $i$, then use $m_i=n_i^2$ slots in the level 2 table $S_i$.

Augmented Data StructuresPermalink

Dynamic Order StatisticsPermalink

Supports: Insert, Delete, Search(x), Select(i), Rank(x).

Idea: use a R-B tree while keeping sizes of the subtree.

$size\left[x\right]=size\left[left\right(x\left)\right]+size\left[right\right(x\left)\right]+1$

Select(root, i):
    k = size[left(x)] + 1 // k = rank(x)
    if i == k then return x
    if i < k then return Select(left(x), i)
    else return Select(right(x), i - k)

$RunningTime=\theta \left({\log }_2\right(n\left)\right)$

Interval TreePermalink

Supports: Intert, Delete, Interval-Search: Find an interval in the set that overlaps a given query interval.

Idea: use a R-B tree while keeping the largest value $m$ in the subtree.

Interval-Search(i) // finds an interval that overlaps i
    x = root
    while x != nil and (low[i] > high[int[x]] or low[int[x]] > high[i]) do // i and int[x] don't overlap
        if left[x] != nil and low[i] <= m[left[x]] then x = left[x]
        else x = right[x]
    return x

Amortized AnalysisPermalink

Potential MethodPermalink

Framework:

• Start with data structure $D_0$
• operation $i$ transforms $D_{i-1}\to D_i$
• cost of the operation is $c_i$
• Define a potential function:

• Amortized cost $\widehat{c_i}$ with respect to $\Phi$ is

• Total amortized cost of n operations is

Competitive AnalysisPermalink

An online algorithm A is $\alpha$-$competitive$ if $\exists k$ such that for any sequence of operations $S$,

where $C_{opt}\left(S\right)$ is the optimal, off-line, “God’s” algorithm.

Karp-Rabin Algorihm: Find s in tPermalink

Rolling Hash ADT:

• r.append(c): r maintains a string x where $r=h\left(x\right)$, add char c to the end of x
• r.skip(): delete the first char of x. (assume it is c).

Then just use ADT to “roll over” t to find s.

Note: If their hashes are equal, there is still a probability $\le 1/\left|S\right|$ that they are actual not the same string.

To implement ADT: use hash simple hash function $h\left(k\right)=kmodm$ where $m$ is a random prime $\ge \left|S\right|$

We can treat $x$ as a multidigit number $u$ in base $a$, where $a$ is just the alphabet size.

So:

• $r\left(\right)=umodm$
• $r$ stores $umodm$ and $\left|x\right|$, (really $a^{\left|x\right|}$), not $u$.

r.append(c)
    u = u * a + ord(c) mod m 
      = [(u mod p) * a + ord(c)] mod m
      = [r() * a + ord(c)] mod m

r.skip(c) // assume char c is skipped
    u = [u − ord(c) * (pow(a, |u| - 1) mod p)] mod p
      = [(u mod p) − ord(c) * (pow(a, |u| - 1) mod p)] mod p
      = [r() − ord(c) * (pow(a, |u| - 1) mod p)] mod p