# Introduction to Algorithm

# Some Notes of Introduction to Algorithm

## Fiboniacci Number

\[\begin{bmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \\ \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}^n\]$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$

\[\lvert\{h\in H;h(x)=h(y)\}\rvert=\lvert H\rvert/m\]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.

\[m[x]=max\{high[int[x]], m[right(x)], m[left(x)]\}\]```
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$,

\[Cost_A(S)\leq\alpha\cdot C_{opt}(S)+k\]where $C_{opt}(S)$ is the optimal, off-line, “God’s” algorithm.

## Karp-Rabin Algorihm: Find s in t

Rolling Hash ADT:

`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
```