GaeBlogX Arista Networks, Software-Defined Networking

2017-06-08
Yanxi Chen

# Some Notes of Introduction to Algorithm

## Fiboniacci Number

$Running\ Time = \theta(\log_2(n))$

## Order Statistics

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

• Quick Select
• Expected running time $\theta(n)$
• Worse case $\theta(n^2)$
• 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 Functions

### Division Method

$h(k) = k\ mod\ m$

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

### Multiplication Method

$h(k)$ $=$ $A\cdot k$ $mod$ $2^w$ » $(w - r)$, $A\ odd\land2^{w-1}$ < $A$ < $2^w$

### Universal Hashing

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 Hashing

Given $n$ keys, construct a static hash table of size $m=O(n)$ such that searching takes $O(1)$ 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 Structures

### Dynamic Order Statistics

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

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

$size[x]=size[left(x)]+size[right(x)]+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)


$Running\ Time = \theta(\log_2(n))$

### Interval Tree

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 Analysis

### Potential Method

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 $\hat{c_i}$ with respect to $\Phi$ is
• Total amortized cost of n operations is

## Competitive Analysis

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

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

## Karp-Rabin Algorihm: Find s in t

• r.append(c): r maintains a string x where $r=h(x)$, 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 $\leq 1/\lvert S\rvert$ that they are actual not the same string.

To implement ADT: use hash simple hash function $h(k)=k\bmod m$ where $m$ is a random prime $\geq\lvert S\rvert$

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

So:

• $r()=u\bmod m$
• $r$ stores $u\bmod m$ and $\lvert x\rvert$, (really $a^{\lvert x\rvert}$), 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