CS240 Course Notes

Professor: Arne Storjohann | Term: Fall 2024

Module 1: Introduction & Asymptotic Analysis

Much of Computer Science is problem solving: Write a program that converts the given input to the expected output.

When first learning to program, we emphasize correctness. With this course, we will also be concerned with efficiency. We will study efficient methods of storing, accessing, and organizing large collections of data.

Typical operations include: Inserting new data items, deleting data items, searching for specific data items, sorting.

We consider various abstract data types (ADTs), and how to realize them efficiently using appropriate data structures. There is a strong emphasis on mathematical analysis in this course.

Useful Logarithms facts:

• $y={\log }_b(x)$ means $b^y=x$
• $\log (x)$ in this course means ${\log }_2(x)$
• $\log (x\cdot y)=\log (x)+\log (y)$, $\log (x^y)=y\log (x)$, $\log (x)\le x$
• ${\log }_b(a)=\frac{{\log }_{c}a}{{\log }_{c}b}=\frac{1}{{\log }_a(b)}$, $a^{{\log }_{b}c}=c^{{\log }_{b}a}$
• $\log (n!)=\log n+\log (n-1)+\cdots +\log 2+\log 1\in \Theta (n\log n)$

Useful Sums:

• ${\sum }_{i=0}^{n-1}i=\frac{(n-1)n}{2}$
• ${\sum }_{i=0}^{n-1}(a+di)=na+\frac{dn(n-1)}{2}\in \Theta (n^2)$ if $d\ne 0$.

Geometric Sequences:

$$\begin{array}{rl}\sum _{i=0}^{n-1}{2}^i& =2^n-1\\ \sum _{i=0}^{n-1}a{r}^i& =\{\begin{array}{ll}a\frac{r^n-1}{r-1}\in \Theta (r^{n-1})& \text{if }r>1\\ na\in \Theta (n)& \text{if }r=1\\ a\frac{1-r^n}{1-r}\in \Theta (1)& \text{if }0<r<1\end{array}\end{array}$$

Harmonic Sequence:

• $H_n:-{\sum }_{i=1}^n\frac{1}{i}=\ln n+\gamma +o(1)\in \Theta (\log n)$

Algorithms and Problems

Problem: Description of possible input and desired output.

Problem Instance: One possible input for the specified problem.

Algorithm: Step-by-step process for carrying out a series of computations, given an arbitrary instance $I$.

Solving a problem: An algorithm $A$ solves a problem $\Pi$ if, for every instance $I$ of $\Pi$, $A$ computes a valid output for the instance $I$ in finite time.

Program: A program is an implementation of an algorithm using a specified computer language.

Pseudocode: Communicate an algorithm to another person.

insertion-sort(A, n)
A: array of size n
for (i <- i; i < n; i++) do
	for (j <- i; j > 0 and A[j-1] > A[j]; j--) do
		swap A[j] and A[j-1]

Omits obvious details, and should be precise about exit-conditions.

For problem $\Pi$ to program that solves it:

• Design an algorithm $\mathcal{A}$ that solves $\Pi$ $\to$ Algorithm Design.
• Assess correctness and efficiency of each $\mathcal{A}$ $\to$ Algorithm Analysis. Correctness $\to$ CS245.
• If acceptable, implement algorithms.
• If multiple acceptable algorithms, run experiments to determine the best solution.

This course will focus on the first two points.

Question

What do we mean by efficiency?

In this course, we are primarily concerned with the amount of time a program takes to run (run time).

We also may be interested in the amount of additional memory the program requires (auxiliary space).

The amount of time and or memory required by a program will usually depend on the given problem instance.

RAM model:

• Each memory cell stores one datum, typically a number, character, or reference.
• Any access to a memory location takes constant time.
• Any primitive operation takes constant time.

We compare algorithms by considering the growth rate: What is the behaviour of algorithms as size $n$ gets large?

We use order notation (big-$O$ and friends). Ignore constants and lower order terms.

We study relationships between functions.

Definition

$O$-notation: $f(x)\in O(g(x))$ ($f$ is asymptotically upper-bounded by $g$) if there exists constants $c>0$ and $n_0\ge 0$ such that $|f(x)|\le c|g(x)|$ for all $x\ge n_0$.

In order to prove that $2n^2+3n+11\in O(n^2)$ from first principles, we need to find $c$ and $n_0$ such that the following condition is satisfied:

$$\begin{array}{r}2n^2+3n+11\le c{n}^2\forall n\ge n_0\end{array}$$

Many, but not all, choices of $c$ and $n_0$ will work.

We also have that $2n^2+3n+11\in O(n^{10})$. We want a tight asymptotic bound.

Definition

$\Omega$-notation: $f(x)\in \Omega (g(x))$ ($f$ is asymptotically lower-bounded by $g$) if there exists constants $c>0$ and $n_0\ge 0$ such that $c|g(x)|\le |f(x)|$ for all $x\ge n_0$.

Definition

$\Theta$-notation: $f(x)\in \Theta (g(x))$ ($f$ is asymptotically tightly-bounded by $g$) if there exists constants $c_1$, $c_2$ $>0$ and $n_0\ge 0$ such that $c_1|g(x)|\le |f(x)|\le c_2|g(x)|\forall x\ge n_0$.

Equivalently:

$$\begin{array}{r}f(n)\in \Theta (g(n))⟺f(n)\in O(g(n))\wedge f(n)\in \Omega (g(n))\end{array}$$

We also say that the growth rates of $f$ and $g$ are the same.

How growth rates affect running time. It is interesting to see how the running time is affected when the size of the problem instance doubles.

$$\begin{array}{rlrl}\text{Constant complexity}:T(n)& =c& & ⇝T(2n)=c\\ \text{Logarithmic complexity}:T(n)& =c\log n& & ⇝T(2n)=T(n)+c\\ \text{Linear complexity}:T(n)& =cn& & ⇝T(2n)=2T(n)\\ \text{Linearithmic complexity}:T(n)& =cn\log n& & ⇝T(2n)=2T(n)+2cn\\ \text{Quadratic complexity}:T(n)& =c{n}^2& & ⇝T(2n)=4T(n)\\ \text{Cubic complexity}:T(n)& =c{n}^3& & ⇝T(2n)=8T(n)\\ \text{Exponential complexity}:T(n)& =c{2}^n& & ⇝T(2n)=(T(n){)}^2/c\end{array}$$

We have $f(n)=n\in \Theta (n)$.

Question

How to express that $f(n)$ grows slower than $n^2$.

Definition

$o$-notation: $f(x)\in o(g(x))$ ($f$ is asymptotically strictly smaller than $g$) if for all constants $c>0$, there exists a constant $n_0\ge 0$ such that $|f(x)|\le c|g(x)|\forall x\ge n_0$.

Definition

$\omega$-notation: $f(x)\in \omega (g(x))$ ($f$ is asymptotically strictly larger than $g$) if for all constants $c>0$, there exists a constant $n_0\ge 0$ such that $|f(x)|\ge c|g(x)|\forall x\ge n_0$.

Suppose that $f(n)>0$ and $g(n)>0$ for all $n\ge n_0$. Suppose that

$$\begin{array}{r}L=\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}\end{array}$$

Then

$$\begin{array}{r}f(n)\in \{\begin{array}{ll}o(g(n))& \text{if }L=0\\ \Theta (g(n))& \text{if }0<L<\infty \end{array}\end{array}$$

If the fraction goes towards $\infty$, then $f(n)\in \omega (g(n))$.

This can be computed using l’Hôspital’s rule. This result gives sufficient but not necessary conditions for the stated conclusion to hold.

Many rules are easily proved from first principle.

Identity rule: $f(n)\in \Theta (f(n))$.

Transitivity:

• If $f(n)\in O(g(n))$ and $g(n)\in O(h(n))$ then $f(n)\in O(h(n))$.
• If $f(n)\in \Omega (g(n))$ and $g(n)\in \Omega (h(n))$ then $f(n)\in \Omega (h(n))$.
• If $f(n)\in O(g(n))$ and $g(n)\in o(h(n))$ then $f(n)\in o(h(n))$.

Suppose that $f(n)>0$ and $g(n)>0$ for all $n\ge n_0$. Then:

• $f(n)+g(n)\in O(\max \{f(n),g(n)\})$
• $f(n)+g(n)\in \Omega (\max \{f(n),g(n)\})$

Relationships between order notations

$$\begin{array}{rl}f(n)\in \Theta (g(n))& ⟺g(n)\in \Theta (f(n))\\ f(n)\in O(g(n))& ⟺g(n)\in \Omega (f(n))\\ f(n)\in o(g(n))& ⟺g(n)\in \omega (f(n))\\ f(n)\in \Theta (g(n))& ⟺f(n)\in O(g(n))\wedge f(n)\in \Omega (g(n))\\ f(n)\in o(g(n))& ⟹f(n)\in O(g(n))\\ f(n)\in o(g(n))& ⟹f(n)\notin \Omega (g(n))\\ f(n)\in \omega (g(n))& ⟹f(n)\in \Omega (g(n))\\ f(n)\in \omega (g(n))& ⟹f(n)\notin O(g(n))\end{array}$$

Avoid doing arithmetic with asymptotic notations. Do not write $O(n)+O(n)=O(n)$.

Techniques for run-time analysis:

• Identify primitive operations that require $\Theta (1)$ time
• The complexity of a loop is expressed as the sum of the complexities of each iteration of the loop.
• Nested loops: start with the innermost loop and proceed outwards. This gives nested summations.

Let $T_{\mathcal{A}}(I)$ denote the running time of an algorithm $\mathcal{A}$ on instance $I$.

Worst-case (best-case) complexity of an algorithm: The worst-case (best-case) running time of an algorithm $\mathcal{A}$ is a function $T:{\mathbb{Z}}^{+}\to \mathbb{R}$ mapping $n$ to the longest (shortest) running time for any input instance of size $n$:

$$\begin{array}{rl}{T}_{\mathcal{A}}^{\text{worst}}(n)& =\underset{I\in {\mathcal{I}}_n}{\max }\{T_{\mathcal{A}}(I)\}\\ T_{\mathcal{A}}^{\text{best}}(n)& =\underset{I\in {\mathcal{I}}_n}{\min }\{T_{\mathcal{A}}(I)\}\end{array}$$

Average-case complexity of an algorithm: The average-case running time of an algorithm $\mathcal{A}$ is a function $T:{\mathbb{Z}}^{+}\to \mathbb{R}$ mapping $n$ to the average running time of $\mathcal{A}$ over all instances of size $n$:

$$\begin{array}{r}{T}_{\mathcal{A}}^{\text{avg}}(n)=\sum _{I\in {\mathcal{I}}_n}{T}_{\mathcal{A}}(I)\cdot (\text{relative frequency of }I)\end{array}$$

Question

Suppose algorithm ${\mathcal{A}}_1$ has worst-case run-time $O(n^3)$ and algorithm $A_2$ has worst-case run-time $O(n^2)$, and both the same problem. Is ${\mathcal{A}}_2$ more efficient?

No! $O$-notation is an upper-bound. ${\mathcal{A}}_1$ may well have worst-case run-time $O(n)$. We should always give $\Theta$-bounds.

Question

Suppose the run-times are $\Theta (n^3)$ and $\Theta (n^2)$, respectively. We consider ${\mathcal{A}}_2$ to be better. But is it always more efficient?

No! The worst-case run-time of ${\mathcal{A}}_1$ may only be achieved on some instances. Possibly ${\mathcal{A}}_1$ is better on most instances.

Merge-sort

Step 1: Describe the overall idea

Input: Array $A$ of $n$ integers.

1. We split $A$ into subarrays $A_L$ and $A_R$ that are roughly half as big.
2. Recursively sort $A_L$ and $A_R$
3. After $A_L$ and $A_R$ have been sorted, use a function merge to merge them into a single sorted array.

Step 2: Give pseudo-code or detailed description

merge-sort(A,n)
if (n <= 1) then return
else
	m = (n-1)/2
	merge-sort(A[0..m], m+1)
	merge-sort(A[m+1..n-1], r)
	merge(A[0..m], A[m +1...n-1])

Do not pass array $A$ by value, instead indicate the range of the array that needs to be sorted. merge an auxiliary array $S$. Allocate this only once.

merge(A,l,m,r,S)
A[0..n-1] is an array, A[l..m] is sorted, A[m+1..r] is sorted
S[0..n-1] is an array
copy A[l..r] into S[l..r]
(i_L, r_R) <- (l, m+1)
for (k <- l, k <= r: k++) do
	if (i_L > m) A[k] <- S[i_R ++]
	else if (i_R > r) A[k] <- S[i_L ++]
	else if (S[i_L] <= S[i_R]) A[k] <- S[i_L ++]
	else A[k] <- S[i_R ++]

Step 3: Argue correctness. Typically state loop-invariants. Sometimes obvious enough from idea-description and comments.

Step 3: Analyze the run-time

• First analyze work done outside recursion
• If applicable, analyze subroutines separately. If there are recursions: how big are the subproblems? The run-time then becomes a recursive function.

The recurrence relation for $T(n)$ is as follows

$$\begin{array}{r}T(n)=\{\begin{array}{ll}T\left(\lfloor \frac{n}{2}\rfloor \right)+T\left(\lfloor \frac{n}{2}\rfloor \right)+cn& \text{if }n>1\\ c& \text{if }n=1\end{array}\end{array}$$

The following is the corresponding sloppy recurrence

$$\begin{array}{r}T(n)=\{\begin{array}{ll}2T\left(\frac{n}{2}\right)+cn& \text{if }n>1\\ c& \text{if }n=1\end{array}\end{array}$$

This resolves to $T(n)\in O(n\log n)$.

Module 2: Priority Queues

Definition

Abstract Data Type (ADT): A description of information and a collection of operations on that information. (Covered in CS135).

The information is accessed only through the operations.

We can have various realizations of an ADT, which specify how the information is stored and how the operations are performed.

Recall:

Stack: An ADT consisting of a collection of items with operations:

• push: Add an item to the stack.
• pop: Remove and return the most recently added item.

Items are removed in LIFO order. We can have extra operations size, is-empty, and top.

Queue: An ADT consisting of a collection of items with operations:

• enqueue: Add an item to the queue
• dequeue: Remove and return the least recently inserted item.

Items are removed in FIFO order.

We can have extra operations size, is-empty, and peek/format.

Priority Queue generalizes both ADT Stack and ADT Queue.

It is a collection of items (each with a priority or key) with operations:

• insert: Inserting an item tagged with a priority
• delete-max: Removing and returning an item of highest priority.

We can have extra operations: size, is-empty, get-max.

This is a maximum-oriented priority queue. A minimum-oriented priority queue replaces operation delete-max by delete-min.

Using a priority queue to sort:

PQ-Sort(A[0..n-1])
for i <- 0 to n-1 do
	PQ.insert (an item with priority A[i])
for i <- n-1 down to 0 do
	A[i] <- priority of PQ.delete-max()

Written as: $O$(initialization $+n\cdot$ insert + $n\cdot$ delete-max$)$

Realizations of Priority Queues

Realization 1: Unsorted arrays

Run-time of operations:

• insert: $\Theta (1)$
• delete-max: $\Theta (n)$

We assume dynamic arrays, expand by doubling as needed. Amortized over all insertions this takes $\Theta (1)$ extra time.

PQ-sort with this realization yields selection-sort.

Realization 2: Sorted arrays

Run-time of operations:

• insert: $\Theta (n)$
• delete-max: $\Theta (1)$

PQ-sort with this realization yields insertion-sort. insert can be implemented to have $\Theta (1)$ best-case run-time. insertion-sort then has $\Theta (n)$ best-case run-time.

Realization 3: Heaps

A binary heap is a certain type of binary tree. A binary tree is either empty, or consists of a node and two binary trees (left subtree and right subtree).

Level $\ell =$ all nodes with $\ell$ distance from the root. Root is on level $0$.

Height $h=$ maximum number for which level $h$ contains nodes. Single-node tree has height $0$, empty tree has height $-1$.

Any binary tree with height $h$ has $n\le 2^{h+1}-1$ nodes. So height $h\le \log (n+1)-1\Omega (\log n)$.

A heap is a binary tree with the following two properties:

1. Structural property: All the levels of a heap are completely filled, except possibly for the last level. The filled items in the last level are left-justified.
2. Heap-order property: For any node $i$, the key of the parent of $i$ is larger than or equal to key of $i$.

The full name for this is max-oriented binary heap.

Lemma: The height of a heap with $n$ nodes is $\Theta (\log n)$.

Heaps should not be stored as binary trees. Let $H$ be a heap of $n$ items and let $A$ be an array of size $n$. Store root in $A[0]$ and continue with elements level-by-level from top to bottom, in each level-to-right.

It is easy to navigate using this array representation:

• The root node is at index 0
• The last node is $n-1$
• The left child is of node $i$ is node $2i+1$
• The right child of node $i$ is node $2i+2$
• The parent of node $i$ is node $\lfloor \frac{i-1}{2}\rfloor$
• These nodes exist if the index falls in the range $\{0,\dots ,n-1\}$

We hide implementation details using helper-functions.

insert in heaps: Place the new key at the first free leaf. Use fix-up to restore heap order.

insert(x)
l <- last()+ 1
A[l] <- x
increase size
fix-up(A, l)

fix-up(A,i)
while parent(i) exists and A[parent(i)].key < A[i].key do
	swap A[i] and A[parent(i)]
	i <- parent(i)

Time: $O($ height of heap $)=O(\log n)$ (and this is tight).

delete-max in heaps

The maximum item of a heap is just the root node. We replace the root by the last leaf (last leaf is taken out). The heap-order property might be violated, perform a fix-down.

fix-down(A,i)
while i is not a leaf do
	j <- left child of i
	if (i has right child and A[right child of i].key > A[j].key)
		j <- right child of i
	if A[i].key >= A[j].key break
	swap A[j] and A[i]
	i <- j

Time: $O($ height of heap $)=O(\log n)$ (and this is tight).

delete-max()
l <- last()
swap A[root()] and A[l]
decrease size
fix-down(A, root(), size)
return A[l]

Time: $O($ height of heap $)=O(\log n)$ (and this is tight).

Binary heap are a realization of priority queues where the operations insert and delete-max take $\Theta (\log n)$ time.

Any priority queue can be used to sort in time

Using the binary-heaps implementation of PQs, we obtain:

PQ-sort-with-heaps(A)
for i <- 0 to n-1 do
	H.insert(A[i])
for <- n-1 down to 0 do
	A[i] <- H.delete-max()

Both operations run in $O(\log n)$ time for heaps $⇝$ PQ-sort using heaps takes $O(n\log n)$ time.

Can improve this with two simple tricks $\to$ heap-sort.

1. Can use the same array for input and heap $⇝O(1)$ auxiliary space.
2. Heaps can be built faster if we know all input in advance.

Problem: Given $n$ items all at once (in $A[0\cdots n-1]$) build a heap containing all of them.

Solution 1: Start with an empty heap and insert items one at a time.

simple-heap-building(A)
for i <- 0 to A.size() - 1 do
	H.insert(A[i])

This corresponds to doing fix-up’s. Worst-case running time: $O(n\log n)$

We can use fix-down’s instead.

heapify(A)
n <- A.size()
for i <- parent(last()) downto root() do
	fix-down(A, i, n)

This yields a worst-case complexity of $\Theta (n)$. A heap can be built in linear time.

Efficient sorting with heaps: Idea is to use PQ-sort with heaps.

heap-sort()A
n <- A.size()
for i <- parent(last()) downto 0 do
	fix-down(A,i,n)
 
while n > 1
	swap items at A[root()] and A[last()]
	decrease n
	fix-down(A, root(), n)

The for-loop takes $\Theta (n)$ time and the while-loop takes $\Theta (n\log n)$ time.

Problem: Find the $k$th smallest item in an array $A$ of $n$ numbers.

Solution 1: Make $k+1$ passes through the array, deleting the minimum number each time. Complexity $\Theta (kn)$.

Solution 2: Sort $A$, then return $A[k]$. Complexity $\Theta (n\log n)$.

Solution 3: Create a min-heap with heapify(A). Call delete-min(A) $k+1$ times. Complexity: $\Theta (n+k\log n)$.

Question

We can achieve $\Theta (n\log n)$ worst-case time easily, but can we do better?

Yes.

Module 3: Sorting, Average-case and Randomization

We introduce (and solve) a new problem, and then analyze the average-case run-time of our algorithm.

Recall the definition of average-case run-time:

$$\begin{array}{r}{T}_{\mathcal{A}}^{\text{avg}}(n)=\sum _{\text{instance }I\text{ of size }n}{T}_{\mathcal{A}}(I)\cdot (\text{relative frequency of }I)\end{array}$$

Assume that the set ${\mathcal{I}}_n$ of size-$n$ instances is finite. Assume that all instances can occur equally frequently. Then we can use the following simplified formula

$$\begin{array}{r}{T}^{\text{avg}}(n)=\frac{{\sum }_{I:\mathrm{size}(I)=n}T(I)}{\#\text{instances of size }n}=\frac{1}{|{\mathcal{I}}_n|}\sum _{i\in {\mathcal{I}}_n}T(I)\end{array}$$

To learn how to analyze this, we will do simpler examples first.

silly-test(π, n)
π: a permutation of {0, ..., n-1}, stored as an array
if π[0] = 0 then for j = 1 to n do print 'bad case'
else print 'good case'

$$\begin{array}{r}{T}^{\text{avg}}(n)=\frac{1}{n!}\sum _{\pi \in {\Pi }_n}T(\pi )=\frac{1}{n!}\left(\sum _{\begin{array}{c}\pi \in {\Pi }_n\\ \text{in bad case}\end{array}}T(\pi )+\sum _{\begin{array}{c}\pi \in {\Pi }_n\\ \text{in good case}\end{array}}T(\pi )\right)\end{array}$$

$(n-1)!$ permutations have $\pi [0]=0⟹$ run-time $c\cdot n$. The remaining $n!-(n-1)!$ permutations have run-time $c$.

$$\begin{array}{rl}{T}^{\text{avg}}(n)& =\frac{1}{n!}\left(\#\{\pi \in {\Pi }_n\text{ in base case}\}\cdot cn+\#\{\pi \in {\Pi }_n\text{ in good case}\}\cdot c\right)\\ & =\frac{1}{n!}\left((n-1)!\cdot cn+(n!-(n-1)!)\cdot c\right)\le \frac{1}{n}cn+c=2c\in O(1)\end{array}$$

Another not-so-contrived example

all-0-test(w,n)
// test whether all entries of bitstring w[0..n-1] are 0
if (n=0) return true
if (w[n-1] = 1) return false
all-0-test(w,n-1)

Define $T(w)=\#$ bit-comparisons on input $w$. This is asymptotically the same as the run-time.

Worst-case run-time: Always go into the recursion until $n=0$. $T(n)=1+T(n-1)=1+1+\cdots +T(0)=n\in \Theta (n)$.

Best-case run-time: Return immediately. $T(n)=1\in \Theta (1)$.

Average-case run-time?

Recall $T^{\text{avg}}(n)=\frac{1}{|{\mathcal{B}}_n|}{\sum }_{w\in {\mathcal{B}}_n}T(w)$ \quad ${\mathcal{B}}_n=\{\text{bistrings of length }n\}$.

Recursive formula for one non-empty bitstring $w$:

$$\begin{array}{r}T(w)=\{\begin{array}{ll}1& \text{if }w[n-1]=1\\ 1+T(\underset{\text{length }n-1}{\underbrace{w[\mathrm{0..}n-2]}})& \text{otherwise}\end{array}\end{array}$$

Natural guess for the recursive formula for $T^{\text{avg}}(n)$:

$$\begin{array}{r}{T}^{\text{avg}}(n)=\underset{\begin{array}{c}\text{half have}\\ w[n-1]=1\end{array}}{\underbrace{\frac{1}{2}}}\cdot 1+\underset{\begin{array}{c}\text{half have }\\ w[n-1]=0\end{array}}{\underbrace{frac12}}(1+T^{???}(n-1))\end{array}$$

This holds with $\le$ but is useless if ??? is worst. This is not obvious if ??? is avg.

$$\begin{array}{rl}{T}^{\text{avg}}(n)& =\frac{1}{|{\mathcal{B}}_n|}\sum _{x\in {\mathcal{B}}_n}T(w)\\ & =\frac{1}{|{\mathcal{B}}_n|}\sum _{\begin{array}{c}x\in {\mathcal{B}}_n\\ w[n-1]=1\end{array}}1+\frac{1}{|{\mathcal{B}}_n|}\sum _{\begin{array}{c}x\in {\mathcal{B}}_n\\ w[n-1]=0\end{array}}\left(1+T(w[\mathrm{0..}n-2])\right)\\ & =\frac{1}{2}+\frac{1}{2}+\frac{1}{|{\mathcal{B}}_n|}\sum _{w^{\prime }\in {\mathcal{B}}_n-1}\sum _{\begin{array}{c}w\in {\mathcal{B}}_n\\ w[n-1]=0\\ w[\mathrm{0..}n-2]=w^{\prime }\end{array}}T(w^{\prime })\end{array}$$

Observe: $w$ is uniquely determined by $w^{\prime }$ and $w[n-1]=0$.

$$\begin{array}{rl}& =1+\frac{1}{|{\mathcal{B}}_n|}\sum _{w^{\prime }\in {\mathcal{B}}_{n-1}}T(w^{\prime })\\ & =1+\frac{|{\mathcal{B}}_{n-1}|}{|{\mathcal{B}}_n|}\frac{1}{|{\mathcal{B}}_{n-1}|}\sum _{w^{\prime }\in {\mathcal{B}}_{n-1}}T(w^{\prime })=1+\frac{1}{2}{T}^{\text{avg}}(n-1)\end{array}$$

This recursion resolves $T^{\text{avg}}(n)\in O(1)$.

Question

Why can’t we always write ‘avg’ for ’???’ in $T^{\text{avg}}(n)=1+\frac{1}{2}{T}^{???}(n-1)$?

Consider

silly-all-0-test(w,n)
if (n = 0) then return true
if (w[n-1] = 1) then return false
if (n>1) then w[n-2] <- 0
silly-all-0-test(w,n-1)

Only one more line of code in each recursion, so same formula applies.

But observe that now $T(w)=\{\begin{array}{ll}1& \text{if }w[n-1]=1\\ n& \text{if }w[n-1]=0\end{array}$

So $T^{\text{avg}}(n)=1+\frac{n}{2}\in \Theta (n)$. The ‘obvious’ recursion did not hold. Average-case analysis is highly non-trivial for recursive algorithms.

We saw SELECTION: Given an array $A$ of $n$ numbers, and $0\le k<n$, find the element that would be at position $k$ of the sorted array.

SELECTION can be done with heaps in time $\Theta (n+k\log n)$.

Special case: MEDIANFINDING = SELECTION with $k=\lfloor \frac{n}{2}\rfloor$. With previous approaches, this takes time $\Theta (n\log n)$, no better than sorting.

Question

Can we do selection in linear time?

Yes, the algorithm quick-select.

quick-select and the related quick-sort rely on two subroutines:

• choose-pivot(A): Return an index $p$ in $A$. We will use the pivot-value $v\leftarrow A[p]$ to rearrange the array.
• partition(A,p): Rearrange $A$ and return pivot-index $i$ so that
  • the pivot-value $v$ is in $A[i]$,
  • all items in $A[0,\dots ,i-1]$ are $\le v$, and
  • all items in $A[i+1,\dots ,n-1]$ are $\ge v$.

$p=$ index of pivot-value before partition (we choose it), $i=$ index of pivot-value after partition (no control).

Partition Algorithm

partition(A,p)
v <- A[p]
for each element x in A do
	if x < v then smaller.append(x)
	else if x > v then larger.append(x)
	else equal.append(x)
i <- smaller.size
j <- equal.size
Overwrite A[0...i-1] by elements in smaller
Overwrite A[i...i+j-1] by elements in equal
Overwrite A[i+j...n-1] by elements in larger
return i

Efficient in-place partition (Hoare)

partition(A,p)
swap(A[n-1], A[p])
i <- -1
j <- n-1
v <- A[n-1]
loop
	do i <- i+1 while A[i] < v
	do j <- j-1 while j > i and A[j] > v
	if i >= j then break 
	else swap(A[i], A[j])
swap(A[n-1], A[i])
return i

Running time $\Theta (n)$.

quick-select(A,k)
p <- choose-pivot(A)
i <- partition(A,p)
if i = k then return A[i]
else if i > k then return quick-select(A[0...i-1], k)
else if i < k then return quick-select(A[i+1...n-1], k-(i+1))

Let $T(n,k)$ be the number of key-comparisons in a size-$n$ array with parameter $k$. partition uses $n$ key-comparisons.

Worst-case run-time: Sub-array always gets smaller, so $\le n$ recursions. Each takes $\le n$ comparisons $⟹O(n^2)$ time. This is tight: If pivot-value is always the maximum and $k=0$ $T^{\text{worst}}(n,0)\ge n+(n-1)+(n-2)+\cdots +1\in \Omega (n^2)$.

Best-case run-time: First chosen pivot could be the $k$th element. No recursive calls; $T(n,k)=n\in \Theta (n)$.

Average case analysis is complicated. We detour into a randomized version.

A randomized algorithm is one which relies on some random numbers in addition to the input. Randomization is a good idea if an algorithm has bad worst-case time but seems to perform much better on most instances.

The run-time will depend on the input and the random numbers used. We assume that there exists a pseudo-random number generator.

Goal: Shift the dependency of run-time from what we can’t control (input) to what we can control (random numbers).

randomized-all-0-test(w,n)
if n = 0 return true
if (random(2)=0) then
	w[n-1] = 1 - w[n-1]
if w[n-1] = 1 return false
randomized-all-0-test(w,n-1)

This is all-0-test, except that we flip last bit based on a coin toss. random(n) returns an integer uniformly from $\{0,1,2,\dots ,n-1\}$.

The run-time of the algorithm now depends on the random numbers. Define $T_{\mathcal{A}}(I,R)$ to be the run-time of a randomized algorithm $\mathcal{A}$ for an instance $I$ and the sequence $R$ of outcomes of random trials.

The expected run-time $T^{\text{exp}}(I)$ for instance $I$ is the expected value:

$$\begin{array}{r}{T}^{\text{exp}}(I)=\mathbf{E}[T(I,R)]=\sum _{R}T(I,R)\cdot \text{Pr}(R)\end{array}$$

Now take the maximum over all instances of size $n$ to define the expected run-time (formally: worst-instance expected-luck run-time) of $\mathcal{A}$.

$$\begin{array}{r}{T}^{\text{exp}}(n):=\underset{I\in {\mathcal{I}}_n}{\max }{T}^{\text{exp}}(I)\end{array}$$

Expected run-time of randomized-all-0-test.

Define $T(w,R):=\#$ bit-comparisons used on input $w$ if the random outcomes are $R$.

The random outcomes $R$ consist of two parts $R=⟨x,R^{\prime }⟩$.

• $x:$ outcome of first coin toss
• $R^{\prime }:$ random outcomes (if any) for the recursions

We have $Pr(R)=Pr(x)\cdot Pr(R^{\prime })$.

Recursive formula for one instance:

$$\begin{array}{r}T(w,r)=T(w,⟨x,R^{\prime }⟩)=\{\begin{array}{ll}1& \text{if }x=w[n-1]\\ 1+T(w[0\dots n-2],R^{\prime })& \text{otherwise}\end{array}\end{array}$$

Natural guess for the recursive formula for $T^{\text{exp}}(n):$

$$\begin{array}{r}{T}^{\text{exp}}(n)=\underset{Pr(x=w[n-1])}{\underbrace{\frac{1}{2}}}\cdot 1+\underset{Pr(x\ne w[n-1])}{\underbrace{\frac{1}{2}}}(1+T^{\text{exp}}(n-1))=1+\frac{1}{2}{T}^{\text{exp}}(n-1)\end{array}$$

In contrast to average-case analysis, the natural guess usually is correct for the expected run-time.

Proof for randomized-all-0-test.

$$\begin{array}{rl}{T}^{\text{exp}}(w)& =\sum _{R}Pr(R)T(w,R)=\sum _x\sum _{R^{\prime }}Pr(x)Pr(R^{\prime })T(w,⟨x,R^{\prime }⟩)\\ & =Pr(x=w[n-1])\sum _{R^{\prime }}Pr(R^{\prime })\cdot +Pr(x\ne w[n-1])\sum _{R^{\prime }}Pr(R^{\prime })(1+T(w[-\dots n-2],R^{\prime }))\\ & =\frac{1}{2}+\frac{1}{2}+\frac{1}{2}\underset{T^{\text{exp}}(\text{some instance of size }n-1)}{\underbrace{\sum _{R^{\prime }}Pr(R^{\prime })\cdot T(w[0\dots n-2],R^{\prime })}}\\ & \le 1+\frac{1}{2}\underset{w^{\prime }\in {\mathcal{B}}_{n-1}}{\max }{T}^{\text{exp}}(w^{\prime })=1+\frac{1}{2}{T}^{\text{exp}}(n-1)\text{holds for all }w\end{array}$$

Therefore $T^{\text{exp}}(n)={\max }_{w\in {\mathcal{B}}_n}{T}^{\text{exp}}(w)\le 1+\frac{1}{2}{T}^{\text{exp}}(n-1)$.

Question

Does the expected time of a randomized version always have something to do with the average-case time?

Yes if the randomization is a shuffle (choose instance randomly).

Average-case run-time and expected run-time are not the same. Average-case is the average over instances usually applied to a deterministic algorithm. Expected is the weighted average over random outcomes, applied only to a randomized algorithm.

For analyzing the average-case run-time of quick-select, we make two assumptions:

• All input-items are distinct.
• All possible orders of the input-items occur equally often.

Goal is to create a randomized version of quick-select.

First idea: Shuffle the input, then do quick-select.

shuffled-quick-select(A,k)
for (j <- 1 to n-1) do swap(A[j], A[random(j+1)])
quick-select(A,k)

We know $T_{\text{quick-select}}^{\text{avg}}(n)=T_{\text{shuffled-quick-select}}^{\text{exp}}(n)$.

Second idea: Do the shuffling inside the recursion.

randomized-quick-select(A,k)
swap A[n-1] witih A[random(n)]
i <- partition(A,n-1)
if i = k then return A[i]
else if i > k then
	return randomized-quick-select(A[0 ... i-1], k)
else if i < k then
	return randomized-quick-select(A[i+1 ... n-1], k-(i+1))

Let $T(A,k,,R)=\#$ key-comparisons of randomized-quick-select on input $⟨A,k⟩$ if the random outcomes are $R$.

Write random outcomes $R$ as $R=⟨i,R^{\prime }⟩$. Observe: $Pr(\text{pivot-index is }i)=\frac{1}{n}$. We recurse in an array of size $i$ or $n-i-1$.

$$\begin{array}{r}T(A,k,⟨i,R^{\prime }⟩)=n+\{\begin{array}{ll}T(\text{size-}i\text{ array},k,R^{\prime })& \text{if }i>k\\ T(\text{size-}(n-i-1)\text{ array},k-i-1,R^{\prime })& \text{if }i<k\\ 0& \text{otherwise}\end{array}\end{array}$$

As for rand-all-0-test: over all $R$, the recursions can use $T^{\text{exp}}(\text{array-size})$.

$$\begin{array}{rl}{T}^{\text{exp}}(A,k)& =\sum _{R}P(R)\cdot T(⟨A,k⟩,R)=\sum _{i=0}^{n-1}\sum _{R^{\prime }}P(i)\cdot P(R^{\prime })\cdot T(⟨A,k⟩,⟨i,R^{\prime }⟩)\\ & =\frac{1}{n}\sum _{i=0}^{k-1}\sum _{R^{\prime }}P(R^{\prime })\left(n+T(⟨A[i+1\dots n-1],k-i-1⟩,R^{\prime })\right)\\ & +\frac{1}{n}\cdot n+\frac{1}{n}\sum _{i=k+1}^{n-1}\sum _{R^{\prime }}P(R^{\prime })\left(n+T(⟨A[0\dots i-1],k⟩,R^{\prime })\right)\\ & =n+\frac{1}{n}\sum _{i=0}^{k-1}\sum _{R^{\prime }}P(R^{\prime })T(⟨A[i+1\dots n-1],k-i-1⟩,R^{\prime })\\ & +\frac{1}{n}\sum _{i=k+1}^{n-1}\sum _{R^{\prime }}P(R^{\prime })T(⟨A[0\dots i-1],k⟩,R^{\prime })\\ & =n+\frac{1}{n}\sum _{i=0}^{k-1}\underset{\le T^{\text{exp}}(n-i-1)}{\underbrace{T^{\text{exp}}(⟨A[i+1\dots n-1],k-i-1⟩)}}+\frac{1}{n}\sum _{i=k+1}^{n-1}\underset{\le T^{\text{exp}}(i)}{\underbrace{T^{\text{exp}}(⟨A[0\dots i-1],k⟩)}}\\ & \le n+\frac{1}{n}\sum _{i=0}^{n-1}\max \{T^{\text{exp}}(i),T^{\text{exp}}(n-i-1)\}\text{ independent of }A,k\end{array}$$

Tedious but straightforward. This recursion resolves to $O(n)$.

randomized-quick-select is generally the fastest solution to the selection problem.

Hoare developed partition and quick-select. He then used them to sort based on partitioning.

quick-sort(A)
if n <= 1 then return
p <- choose-pivot(A)
i <- partition(A,p)
quick-sort(A[0, 1, ..., i-1])
quick-sort(A[i+1, ..., n-1])

Worst-case run-time: $\Theta (n^2)$

Best-case run-time: $\Theta (n)$

Average-case run-time we prove via randomization.

$T^{\text{exp}}(n)\le n+\frac{1}{n}{\sum }_{i=0}^{n-1}\left(T^{\text{exp}}(i)+T^{\text{exp}}(n-i-1)\right)=n+\frac{2}{n}{\sum }_{i=1}^{n-1}{T}^{\text{exp}}(i)$.

$T^{\text{exp}}(n)\in O(n\log n)$

We have seen many sorting algorithms.

Question

Can one do better than $\Theta (n\log n)$ running time?

Yes and no, depends on what we allow.

No: Comparison-based sorting lower bound is $\Omega (n\log n)$

Yes: Non-comparison-based sorting can achieve $O(n)$ (under restrictions).

All algorithms so far are comparison-based. Data is accessed by comparing two elements, and moving elements around.

Theorem

Any comparison-based sorting algorithm requires in the worst case $\Omega (n\log n)$ comparisons to sort $n$ distinct items.

Easy to understand via a decision tree.

Non-Comparison-Based Sorting

Assume keys are numbers in base $R$ ($R$: radix). All digits are in $\{0,\dots ,R-1\}$.

Assume all keys have the same number $m$ of digits. Can achieve after padding with leading $0$s.

Can sort based on individual digits.

bucket-sort(A, n, sort-key())
sort-key(): maps items of A to {0,...,R-1}
Initialize an array B[0..R-1] of empty queues (buckets)
for i <- 0 to n-1 do
	Append A[0] at the end of B[sort-key(A[i])]
i <- 0
for j <- 0 to R-1 do
	while B[j] is non-empty do
		move front element of B[j] to A[i++]

bucket-sort is stable, equal items stay in original order.

Run-time is $\Theta (n+R)$, auxiliary space $\Theta (n+R)$. It is possible to replace the lists by arrays $⇝$ count-sort.

Most-significant-digit(MSD)-radix-sort

Sort array of $m$-digit radix-$R$ numbers recursively: sort by 1st digit, then each group by 2nd digit etc.

MSD-radix-sort(A,n,d<-1)
A: array of size n, contains m-digit radix-R numbers
if (d <= m and (n > 1))
	bucket-sort(A, n, return dth digit of A[i])
	l <- 0
	for j <- 0 to R-1
		Let r >= l - 1 be maximal s.t. A[l..r] have dth digit j
		MSD-radix-sort(A[l..r], r - l + 1, d+1)
		l <- r + 1

• $\Theta (m)$ levels of recursion in worst-case
• $\Theta (n)$ subproblems on most levels in worst-case
• $\Theta (R+(\text{size of sub-array}))$ time for each bucket-sort call.

Run-time $\Theta (mnR)$ - slow. Many recursions and allocated arrays.

LSD-radix-sort(A,n)
A: array of size n, contains m-digit radix-R numbers
for d <- least significant to most significant do
	bucket-sort(A,n,return dth digit of A[i])

Time cost $\Theta (m(n+r))$ with auxiliary space $\Theta (n+R)$.

Module 4: Dictionaries

Definition

Dictionary: An ADT consisting of a collection of items, each of which contains a key and some data. This is called a key value pair. Keys can be compared and are typically unique.

Common assumptions:

Dictionary has $n$ KVPs, each KVP uses constant space, keys can be compared in constant time.

In an unordered array or linked list, search is $\Theta (n)$, insertion is $\Theta (1)$, delete is $\Theta (n)$.

In an ordered array, search is $\Theta (\log n)$, insertion is $O(n)$, delete is $\Theta (n)$.

Recall binary search only applies to a sorted array.

Binary search trees: All nodes have two (possibly empty) subtrees. Every node stores a KVP, empty subtrees aren’t shown.

Every $k$ in $T.\text{left}$ is less than the root key, and every key $k$ in $T.\text{right}$ is greater than the root key.

BST as a realization of ADT dictionary.

BST::search(k): Start at root, compare $k$ to current node’s key. Stop if found or subtree empty, else recurse at subtree.

Deletion in a BST: First search for the node $x$ that contains the key. If $x$ is a leaf, delete it. If $x$ has one non-empty subtree, move child up. Otherwise, swap key at $x$ with key at successor node and then delete that node. The successor is the next-smallest among all keys in the dictionary.

BST::search, BST::insert, BST::delete all have cost $\Theta (h)$, where $h=$ height of tree $=$ max path length from root to leaf.

Question

If $n$ items are inserted one-at-a-time, how big is $h$?

Worst-case: $n-1=\Theta (n)$

Best-case: $\Theta (\log n)$. Any binary tree with $n$ nodes has height $h\ge \log (n+1)-1$. Layer $i$ has at most $2^i$ nodes. So $n\le {\sum }_{i=0}^h{2}^i=2^{h+1}-1$.

Goal is to create a subclass of BSTs where the height is always good. We need to impose a structural property, argue that the property implies logarithmic height, and discuss how to maintain the property during operations.

AVL Trees: An AVL Tree is a BST with an additional height-balance property at every node: The heights of left and right subtree differ by at most $1$.

If node $v$ has left subtree $L$ and right subtree $R$, then

$$\begin{array}{rl}\text{balance}(v)& :=\text{height}(R)-\text{height}(L)\text{must be in }\{-1,0,1\}\\ \text{balance}(v)& =-1\text{ means }v\text{ is left-heavy}\\ \text{balance}(v)& =+1\text{ means }v\text{ is right-heavy}\end{array}$$

Need to store at each node $v$ the height of the subtree rooted at it.

Theorem

An AVL tree on $n$ nodes has $\Theta (\log n)$ height. search, BST::insert, BST::delete all cost $\Theta (\log n)$ in the worst case.

AVL Insertion (AVL::insert(k,v))

First, insert $(k,v)$ with the usual BST insertion. We assume that this returns the new leaf $z$ where the key was stored. Then, move up the tree from $z$. Update height (we can do this in constant time). If the height difference becomes $\pm 2$ at nodes $z$, then $z$ is unbalanced. Must re-structure the tree to rebalance.

There are many different BSTs with the same keys.

The goal is to change the structure locally without changing the order. Longterm goal is to restructure so the subtree becomes balanced.

Right rotation on node $z$

flowchart TD
z((z)) --> c((c))
z --> D[/D\]
c --> g
c --> C[/C\]
g((g)) --> A[/A\]
g --> B[/B\]

Becomes

flowchart TD
c((c)) --> g((g))
c --> z((z))
g --> A[/A\]
g --> B[/B\]
z --> C[/C\]
z --> D[/D\]

rotate-right(z)
c <- z.left, z.left <- c.right, c.right <- z
setHeightFromSubtrees(z), setHeightFromSubtrees(c)
return c

Left rotation is used to fix a right-right imbalance.

A double right rotation on node $z$ starts with a left rotation at $c$, then a right rotation at $z$.

flowchart TD
z((z)) --> c((c))
z --> D[/D\]
c --> A[/A\]
c --> g((g))
g --> B[/B\]
g --> C[/C\]

Becomes

flowchart TD
z((z)) --> c((c))
z --> D[/D\]
c --> g
c --> C[/C\]
g((g)) --> A[/A\]
g --> B[/B\]

Which then becomes

flowchart TD
g((g)) --> c((c))
g --> z((z))
c --> A[/A\]
c --> B[/B\]
z --> C[/C\]
z --> D[/D\]

Symmetrically, there is a double left rotation.

AVL insertion revisited. When there is an imbalance at $z$ do (single or double) rotation. Choose $c$ as child where subtree has bigger height.

AVL::insert(k,v)
z <- BST::insert(k,v)
while(z is not NULL)
	if (|z.left.heigth - z.right.height| > 1) then
		Let c be taller child of z
		Let g be taller child of c
		restructure(g,c,z)
		break
	setHeightFromSubtrees(z)
	z <- z.parent

We can argue that for insertion, one rotation restores all heights of subtrees.

restructure(g,c,z)
node g is a child of c which is a child of z
p <- z.parent
(make the right rotation)
make u the appropriate child of p and return u

The middle key of $g,c,z$ becomes the new root.

AVL Deletion (AVL::delete(k))

Remove the key $k$ with BST::delete. Find node where structure change happened. Go back up to the root, update heights, and rotate if needed.

AVL::delete(k)
z <- BST::delete(k)
Assume z is the parent of the BST node that was removed
while (z is not NULL)
	if (|z.left.height - z.right.height| > 1) then
		Let c be taller child of z
		Let g be taller child of c
		z <- restructure(g,c,z)
	setHeightFromSubtrees(z)
	z <- z.parent

Ties must be broken to avoid double rotation.

AVL Tree Summary

• Search: $\Theta (\text{height})$
• Insert: $\Theta (\text{height})$. Restructure will be called at most once
• Delete: $\Theta (\text{height})$. Restructure may be called $\Theta (\text{height})$ times.

Worst-case cost for all operations is $\Theta (\text{height})=\Theta (\log n)$.

Module 5: Other Dictionary Implementations

So far we’ve seen unordered arrays, ordered arrays, binary search trees, and balanced binary search trees.

If the KVPs were inserted in random order, then the expected height of the binary search tree would be $O(\log n)$.

We did not consider an ordered list as a realization of ADT dictionary. insert and delete take $\Theta (1)$ time in an ordered list, once we know where to place them. The bottleneck is in search.

In an ordered array, we can do binary search to achieve $O(\log n)$. In an ordered list, we cannot skip to the middle, and so cannot do binary search. Search takes $\Theta (n)$ time in an ordered list, this is slow.

To speed up search in an ordered list, add links to help us move forward quicker. Choose randomly when to add links.

Skip Lists

A hierarchy of ordered linked lists (levels) $L_0,L_1,\dots ,L_h$.

Each list $L_i$ contains the special keys $-\infty$ and $+\infty$ (sentinels). List $L_0$ contains the KVPs of $S$ in non-decreasing order. Each list is a subsequence of the previous one, i.e., $L_0\supseteq L_1\supseteq \cdots \supseteq L_h$. List $L_h$ contains only the sentinels.

A node is an entry in one list, a KVP is one non-sentinel entry in $L_0$.

There are usually mode nodes than KVPs. Each node $p$ has references $p.\text{after}$ and $p.\text{below}$. Each key $k$ belongs to a tower of nodes. Height of tower of $k$: maximal index $i$ such that $k\in L_i$. Height of skip list: maximal index $h$ such that $L_h$ exists.

Search in skip list. For each list, find predecessor.

get-predecessors(k)
p <- root
P <- stack of nodes, initially containing p
while p.below != NULL do
	p <- p.below
	while p.after.key < k do p <- p.after
	P.push(p)
return P

skipList::search(k)
P <- get-predecessors(k)
p_0 <- P.top()
if p_0.after.key = k return KVP at p_0.after
else return "not found, but would be after p_0"

It is easy to remove a key since we can find all predecessors. We eliminate lists if there are multiple ones with only sentinels.

skipList::delete(k)
P <- get-predecessors(k)
while P is non-empty
	p <- P.pop()
	if p.after.key = k
		p.after <- p.after.after
	else break
 
p <- left sentinel of the root-list
while p.below after is the infinity-sentinel
	// the two top lists are both only sentinels, remove one
	p.below <- p.below.below
	p.after.below <- p.after.below.below

Inserting in skip lists skipList::insert(k,v). There is no choice as to where to put the tower of $k$. Only choice, how tall should we make the tower of $k$? We choose randomly.

Repeatedly toss a coin until you get tails. Let $i$ be the number of times the coin came up heads. We want key $k$ to be in lists $L_0,\dots L_i$, so $i\to$ height of tower of $k$.

$$\begin{array}{r}P(\text{tower of key }k\text{ has height }\ge i)={\left(\frac{1}{2}\right)}^i\end{array}$$

Before we can insert, must check that these lists exist. Then we do the actual insertion. Use get-predecessors(k) to get stack $P$. The top $i$ items of $P$ are the predecessors $p_0,p_1,\cdots ,p_i$ of where $k$ should be in each list $L_0,L_1,\dots ,L_i$. Insert $(k,v)$ after $p_0$ in $L_0$, and $k$ after $p_j$ in $L_j$ for $1\le j\le i$.

skipList::insert(k,v)
for (i <- 0; random(2) = 1; i++) {}
for (h <- 0, p <- root.below, p != NULL; p <- p.below, h++) {}
while i >= h
	create new sentinel-only list; link it in below topmost list
	h++
P <- get-predecessors(k)
p <- P.pop()
zbelow <- new node with (k,v)
zbelow.after <- p.after; p.after <- zbelow
while i > 0
	p <- P.pop()
	z <- new node with k
	z.after <- p.after; p.after <- z; z.below <- zbelow; zbelow <- z

Analysis of skip lists.

Expected space usage: $O(n)$. Expected height: $O(\log n)$.

skipList::get-predecessors: $O(\log n)$ expected time.

Search, insert, delete: $O(\log n)$ expected time.

Recall unsorted array realization:

• Search: $\Theta (n)$
• Insert: $\Theta (1)$
• Delete: $\Theta (1)$

Question

Can we do something to make search more effective in practice?

No. If items are accessed with equal likelihoods. We can show that the average-case cost for search is then $\Theta (n)$.

We can make search more effective if search requests are biased (some items are accessed much more frequently than others). Intuition is that frequently accessed items should be in the front. Two scenarios - do we know the access distribution beforehand or not?

Optimal Static Ordering

Scenario: We know access distribution, and want the best order of a list.

Key	A	B	C	D	E
Frequency of access	2	8	1	10	5

Recall:

$$\begin{array}{rl}{T}^{\text{avg}}(n)& =\sum _{I\in {\mathcal{I}}_n}T(I)\cdot (\text{relative frequency of }I)\\ & =\text{expected run-time on randomly chosen input}\\ & =\sum _{I\in {\mathcal{I}}_n}T(I)\cdot Pr(\text{randomly chosen instance is }I)\end{array}$$

Count of cost $i$ if search-key ($=$ instance $I$) is at $i$th position $(i\ge 1$).

$T^{\text{avg}}(n)=$ expected access cost $={\sum }_{i\ge 1}i\cdot \underset{\text{access-probability of that key}}{\underbrace{Pr(\text{search for key at position }i)}}$

Order $A\to B\to C\to D\to E$ has expected access cost of $\approx 3.31$.

Order $D\to B\to E\to A\to C$ is better (access cost of $\approx 2.54$).

Claim: Over all possible static orderings, the one that sorts items by non-increasing access-probability minimizes the expected access cost.

Dynamic Ordering: MTF

Scenario: We do not know the access probabilities ahead of time.

Idea: Modify the order dynamically, i.e., while we are accessing. Rule of thumb (temporal locality), a recently accessed item is likely to be used again.

Move-To-Front heuristic (MTF): Upon a successful search, move the accessed item to the front of the list.

We can also do MTF on an array, but should then insert and search from the back so that we have room to grow.

There are other heuristics we can also use. Upon a successful search, swap the accessed item with the item immediately preceding it (transpose heuristic). Keep counters how often items were accessed, and sort in non-decreasing order (frequency-count heuristic).

Module 6: Dictionaries for Special Keys

So far we’ve seen balanced binary search trees and skip lists. Various other realizations sometimes faster on insert, but search always takes $\Omega (\log n)$ time.

Interpolation Search

Scenario: Numbers in sorted array [40, 50, 70, 90, 100, 110, 120].

binary-search(A,n,k)
l <- 0, r <- n-1
while (l <= r)
	m <- (l + r) / 2
	if (A[m] equals k) then return "found at A[m]"
	else if (A[m] < k) then l <- m + 1
	else r <- m -1 
return "not found"

Compare at index $\lfloor \frac{\ell +r}{2}\rfloor =\ell +\lfloor \frac{1}{2}(r-\ell )\rfloor$. If keys are numbers, where would you expect key $k=100$?

Interpolation search is similar to binary search, but compare at index.

$$\begin{array}{r}\ell +\lfloor \frac{\stackrel{\text{distance from left key}}{\overbrace{k-A[\ell ]}}}{\underset{\text{distance between left and right keys}}{\underbrace{A[r]-A[\ell ]}}}\cdot \underset{\text{number of indices in range}}{\underbrace{(r-\ell )}}\rfloor \end{array}$$

interpolation-search(A,k)
while (l <= r)
	if (k < A[l] or k > A[r]) return "not found"
	if (k = A[r]) then return "found at A[r]"
	m = expression above
	if (A[m] equals k) then return "found at A[m]"
	else if (A[m] < k) then l <- m + 1
	else r <- m-1

In the worst case, this can be very slow $\Theta (n)$. But it works well on average. We can show $T^{\text{avg}}(n)\le T^{\text{avg}}(\sqrt{n})+\Theta (1)$. This resolves to $T^{\text{avg}}(n)\in O(\log \log n)$.

Scenario: Keys in dictionary are words. Need brief review.

Words ($=$ strings): sequences of characters over alphabet $\Sigma \{\text{be},\text{bear},\text{beer}\}$.

Convention: Words have end-sentinel $. w.size = $|w|=\#$ non-sentinel characters: |\text{be}\| = 2$.

Trie (a radix tree): A dictionary for bit-strings. Comes from retrieval. A tree based on bitwise comparisons, edge labelled with corresponding bit. Similar to radix sort: use individual bits, not the whole key. Due to end-sentinels, all key-value pairs are at leaves.

Tries: Search

Follow links that corresponds to current bits in $w$. Repeat until no such link or $w$ found at a leaf. Similar as for skip lists, we find search-path separately first.

Trie::get-path-to(w)
P <- empty stack; z <- root; d <- 0; P.push(z)
while d <= |w|
	if z has a child-link labelled with w[d]
		z <- child at this link; d++; P.push(z)
	else break
return P

Trie::search(w)
P <- get-path-to(w), z <- P.top
if (z is not a leaf) then
	return "not found, would be in sub-trie of z"
return key-value pair at z

For later applications of tries, we want another search-operation. prefix-search(w): find word $w^{\prime }$ in trie for which $w$ is a prefix. Testing whether $w^{\prime }$ exists is easy.

To find $w^{\prime }$ quickly, we need leaf-references. Every node $z$ stores reference $z.\text{leaf}$ to a leaf in subtree. Convention: store leaf with the longest word.

Trie::prefix-search(w)
P <- get-path-to(w), p <- P.top()
if number of nodes on P is w.size or less
	return "no extension of w found"
return p.leaf

Trie::insert(w). $P\leftarrow$ get-path-to(w) gives ancestors that exist already. Expand the trie from $P.top()$ by adding necessary nodes that correspond to extra bits of $w$. Update leaf-references.

search(w), prefix-search(w), insert(w), delete(w) all take time $\Theta (|w|)$. Search time is independent of number of $n$ words stored in the trie! Search-time is small for short words.

The trie for a given set of words is unique (expend for order of children and ties among leaf-references).

Tries can be wasteful with respect to space. Worst-case space is $\Theta (n\cdot (\text{maximum length of a word}))$.

Question

What can we do to save space?

Pruned Tries: Stop adding nodes to trie as soon as the key is unique.

A node has a child only if it has at least two descendants. Saves spaces if there are only few bit-strings that are long. This is a more efficient version of tires, but the operations get a bit more complicated.

We have (implicitly) seen pruned tries before: For equal-length bit-strings, pruned trie equals recursion tree of MSD radix-sort.

Compressed Tries: Compress paths of nodes with only one child. Each node stores an index, corresponding to the level of the node in the uncompressed trie. These are known as Patricia-Tries (Practical Algorithm to Retrieve Information Coded in Alphanumeric)

As for tries, follow links that correspond to current bits $w$. Main difference: stored indices say which bits to compare.

CompressedTrie::get-path-to(w)
P <- empty stack; z <- root: P.push(z)
while z is not a leaf and (d <- z.index <= w.size) do
	if (z has a child-link labelled with w[d]) then
		z <- child at this link; P.push(z)
	else break
return P

CompressedTrie::search(w)
P <- get-path-to(w), z <- P.top
if (z is not a leaf or word stored at z is not w) then
	return "not found"
return key-value pair at z

search(w) and prefix-search(w) are easy. insert(w) and delete(w) are conceptually simple. Search for path $P$ to word, uncompress this path, insert/delete $w$ as in an uncompressed trie, compress path from root to where change happened.

All operations take $O(|w|)$ time for a word $w$. Compressed tries use $O(n)$ space. We have $n$ leaves, every internal node has two or more children. Can show that there are more leaves than internal nodes.

To represent strings over any fixed alphabet $\Sigma$, any node will have at most $|\Sigma |+1$ children.

Variation: Compressed multi-way tries: compress paths as before.

Operations search(w), prefix-search(w), insert(w), and delete(w) are exactly as for tries for bit-strings. Run-time $O(|w|\cdot (\text{time to find the appropriate child}))$. Each node now has up to $|\Sigma |+1$ children.

Question

How should they be stored?

Time/space tradeoffs. Arrays are fast, lists are space-efficient. Dictionary best in theory, not worth it in practice unless $|\Sigma |$ is huge. In practice, we use hashing.

Module 7: Dictionaries via Hashing

Dictionaries via Hashing

Special situation: For a known $M\in \mathbb{N}$, every key $k$ is an integer with $0\le k<M$. We can then implement a dictionary easily: Use an array $A$ of size $M$ that stores $(k,v)$ via $A[k]\leftarrow v$.

• search(k): Check whether $A[k]$ is NULL.
• insert(k,v): $A[k]\leftarrow v$
• delete(k): $A[k]\leftarrow$ NULL

Each operation is $\Theta (1)$. Total space is $\Theta (M)$.

Two disadvantages of direct addressing. It cannot be used if the keys are not integers. It wastes space if $M$ is unknown or $n<<M$.

Hashing idea: Map (arbitrary) keys to integers in range $\{0,\dots ,M-1\}$ (for an integer $M$ of our choice), then use direct addressing.

We know that all keys come from some universe $U$. We pick a table-size $M$. We pick a hash function $h:U\to \{0,1,\dots ,M-1\}$. Store dictionary in a hash table. An item with key $k$ wants to be stored in slot $h(k)$.

Generally hash function $h$ is not injective, so many keys can map to the same integer. We get collisions: we want to insert $(k,v)$ into the table, but $T[h(k)]$ is already occupied. There are many strategies to resolve collisions.

Hashing with Chaining

Simplest collision-resolution strategy: Each slot stores a bucket containing $0$ or more KVPs. A bucket could be implemented by any dictionary realization. The simplest approach is to use unsorted lists with MTF for buckets. This is called collision resolution by chaining.

• insert(k, v): Add $(k,v)$ to the front of the list at $T[h(k)]$
• search(k): Look for key $k$ in the list at $T[h(k)]$. Apply MTF-heuristic.
• delete(k): Perform a search, then delete from the linked list.

insert takes time $O(1)$. search and delete have run-time $O(1+\text{length of a list at }T(h(k)))$.

Complexity of chaining: insert takes time $\Theta (1)$. search and delete have run-time $\Theta (1+\text{size of bucket }T[h(k)])$.

The average bucket size is $\frac{n}{M}=:\alpha$ ($\alpha$ is also called the load factor).

However, this does not imply that the average-case cost of search and delete is $\Theta (1+\alpha )$. Consider the case where all keys hash to the same slot. The average bucket-size is still $\alpha$. But the operations take $\Theta (n)$ time on average.

To get meaningful average-case bounds, we need assumptions on hash-functions and keys.

We can switch to randomized hashing. Assume that the hash-function is chosen randomly. We assume the following:

Uniform Hashing Assumption: Any possible hash-function is equally likely chosen has hash-function.

UHA implies that the distribution of keys is unimportant. Claim: Hash-values are uniform. Formally: $P(h(k)=i)=\frac{1}{M}$ for any key $k$ and slot $i$.

Proof: Let ${\mathcal{H}}_j$ (for $j=0,\dots ,M-1)$ be hash-functions with $h(k)=j$. For any $i\ne j$, can map ${\mathcal{H}}_i$ to ${\mathcal{H}}_j$ and vice versa. So $P(h(k)=i)=P(h\in {\mathcal{H}}_i)=\frac{1}{M}$

Claim: Hash-values of any two keys are independent of each other.

Back to complexity of chaining. Each bucket has expected length $\frac{n}{M}\le \alpha$. $n$ other keys are in this slot with probability $\frac{1}{M}$. Each key in dictionary is expected to collide with $\frac{n-1}{M}$ other keys. $n-1$ other keys are in same slot with probability $\frac{1}{M}$. Expected search and delete is hence $\Theta (1+\alpha )$.

For hashing with chaining, the run-time bound depends on $\alpha$. We keep the load factor small by rehashing when needed.

For Hashing with Chaining: Rehash so that $\alpha \in \Theta (1)$ throughout. Rehashing costs $\Theta (M+n)$ time. Rehashing happens rarely enough that we can ignore this term when amortizing over all operations. We re-hash when $\alpha$ gets too small.

The amortized expected cost for hashing with chaining is $O(1)$ and the space is $\Theta (n)$.

Probe Sequences

Main Idea: Avoid the links needed for chaining by permitting only one item per slot, but allowing a key $k$ to be in multiple slots.

search and insert follow a probe sequence of possible locations for key $k$: $⟨h(k,0),h(k,1),h(k,2),\dots ,h(k,M-1)⟩$ until an empty spot is found.

Simplest method for open addressing: linear probing.

$h(k,j)=(h(k)+j)(\mathrm{mod}M)$, for some hash function $h$.

delete becomes problematic. Cannot leave an empty spot behind; the next search might otherwise not go far enough. We can try to move later items in probe sequence forward. Better idea is lazy deletion. Mark the spot as deleted, search continues past deleted spots, insertion reuses deleted spots.

Keep track of how many items are ‘deleted’ and re-hash if there are too many.

probe-sequencce::insert(T,(k,v))
for (j=0; j<m; j++) 
	if T[h(k,j)] is NULL or "deleted"
		T[h(k,j)] = (k,v)
		return "success"
return "failure to insert"

probe-sequence-search(T,k)
for (j=0; j < m; j++) 
	if T[h(k,j)] is NULL return "item not found"
	if T[h(k,j)] has key k return T[h(k,j)]
return "item not found"

Some hashing methods require two hash functions $h_0,h_1$. These hash functions should be independent in the sense that the random variables $P(h_0(k)=i)$ and $P(h_1(k)=j)$ are independent. Using two modular hash-functions often leads to dependencies.

Better idea: Use multiplication method for second hash function:

$$\begin{array}{r}h(k)=\lfloor M(kA-\lfloor ka\rfloor )\rfloor \end{array}$$

$A$ is some floating-point number with $0<A<1$. $kA-\lfloor kA\rfloor$ computes fractional part $kA$, which is in $[0,1)$. Multiple with $M$ to get floating-point number in $[0,M)$. Round down to get integer in $\{0,\dots ,M-1\}$.

Assume there are two independent hash functions $h_0,h_1$.

Assume further that $h_1(k)\ne 0$ and that $h_1(k)$ is relative prime with the table-size $M$ for all keys $k$. Choose $M$ prime. Modify standard hash-functions to ensure $h_1(k)\ne 0$.

Double-hashing: open-addressing with probe seqeunce

$$\begin{array}{r}h(k,j)=(h_0(k)+j\cdot h_1(k))(\mathrm{mod}M)\end{array}$$

search, insert, delete work just like for linear probing, with this different probe sequence.

Cuckoo Hashing

We use two independent hash functions $h_0,h_1$, and two tables $T_0,T_1$.

Main idea: An item with key $k$ can only be at $T_0[h_0(k)]$ or $T_1[h_1(k)]$. search and delete always take constant time.

insert always initially puts the new item into $T_0[h_0(k)]$. Evict item that may have been there already. If so, evicted item inserted at alternate position. This may lead to a loop of evictions. Can show that if insertion is possible, then there are at most $2n$ evictions.

Can show: expected number of evictions during insert is $O(1)$. So in practice, stop evictions much earlier than $2n$ rounds. This crucially requires load factor $\alpha <\frac{1}{2}$. Here $\alpha =n/(\text{size of }{T}_0+\text{ size of }{T}_1)$.

Cuckoo hashing is wasteful on space. In fact, space is $\omega (n)$ if insert forces lots of re-hashing. Can show the expected space is $O(n)$.

For any open addressing scheme, we must have $\alpha \le 1$. For the analysis, we require $0<\alpha <1$. Cuckoo hashing requires $0<\alpha <1/2$.

All strategies have $O(1)$ expected time for search, insert, delete. Cuckoo Hashing has $O(1)$ worst-case time for search, delete. Probe sequences use $O(n)$ worst-case space, Cuckoo Hashing uses $O(n)$ expected space.

For any hash-functions the worst-case run-time is $\Theta (n)$ for insert.

Hash Function Strategies

Recall UHA: Hash function is randomly chosen among all possible hash-functions.

Satisfying this is impossible: There are too many hash functions; we would not know how to look up $h(k)$.

We have to compromise, choose a hash-function that is easy to compute.

Two basic methods for integer keys (module method and multiplication method). Every hash function must do badly for some sequences of inputs: If the universe contains at least $M\cdot n$ keys, then there are $n$ keys that all hash to the same value.

Carter-Wegman’s universal hashing: Choose hash-function randomly.

Requires: all keys are in $\{0,\dots ,p-1\}$ for some big prime $p$. At initialization, and whenever we re-hash: Choose $M<p$ arbitrarily, power of $2$ is okay. Choose (and store) two random numbers $a,b$ $(b=$ random(p)$)$. $(a=1+$ random(p-1)$)$. $h(k)$ can be computed quickly.

Analysis of these Carter-Wegman hash functions. Choosing $h$ in this way does not satisfy uniform hashing assumptions. But can show: two keys collide with probability at most $\frac{1}{M}$. This suffices to prove the run-time bounds for hashing with chaining.

Question

What if the keys are multi-dimensional, such as strings?

Standard approach is to flatten string $w$ to integer $f(w)\in \mathbb{N}$.

Module 8: Range-Searching in Dictionaries for Points

So far, search(k) looks for one specific item. New operation range-search: look for all items that fall within a given range. Input: A range, i.e., an interval $Q=(x,x^{\prime })$. It may be open or closed at the ends. We want to report all KVPs in the dictionary whose key $k$ satisfies $k\in Q$.

As usual $n$ denotes the number of input-items. Let $s$ be the output-size (the number if items in the range). We need $\Omega (s)$ time simply to report the items. Typical run-time: $O(\log n+s)$.

Unsorted list/array/hash table: Range search requires $\Omega (n)$ time: We have to check for each item explicitly whether it is in the range.

Sorted array: Range search in $A$ can be done in $O(\log n+s)$ time.

BST: Range searches can similarly be done in time $O(\text{height}+s)$ time.

Range searches are of special interest for multi-dimensional data.

Each item has $d$ aspects (coordinates): $(x_0,x_1,\cdots ,x_{d-1})$ so corresponds to a point in $d$-dimensional space.

We concentrate on $d=2$ (points in Euclidean plane).

(Orthogonal) $d$-dimensional range search: Given a query rectangle $Q=[x_1,x_1^{\prime }]\times \cdots \times [x_d,x_d^{\prime }]$, find all points that lie within $Q$.

The time for range searches depends on how the points are stored. Could store a 1-dimensional dictionary (key is the combination of aspects). However, range search on one aspect is not straightforward.

Better idea: Design new data structures specifically for points (quadtrees, kd-trees, range-trees). Assumption: Points are in general position: No two points on a horizontal line, no two points on a vertical line.

Quadtrees

We have $n$ points $P=\{(x_0,y_0),(x_1,y_1),\cdots ,(x_{n-1},y_{n-1})\}$ in the plane. Find a bounding box $R=[0,2^k)\times [0,2^k)$: a square containing all points. Assume that all coordinates are non-negative. Find max-coordinate in $P$, use the smallest $k$ such that it is $<2^k$.

Structure (how to build the quadtree that stores $P$):

• Root $r$ of the quadtree is associated with region $R$
• If $R$ contains 0 or 1 points, then root $r$ is a leaf that stores point.
• Else, split: Partition $R$ into four equal subsquares (quadrants) $R_{NE},R_{NW},R_{SW},R_{SE}$.
• Partition $P$ into sets $P_{NE},P_{NW},P_{SW},P_{SE}$ of points in these regions. Points on split lines belong to right/top side.
• Recursively build tree $T_i$ for points $P_i$ in region $R_i$ and make them children of the root.

graph TD

    A["[0,16] × [0,16]"]

    B["[0,8] × [8,16]"]
    C["[0,8] × [0,8]"]

    P4((p4))
    P5((p5))

    A --> B
    A --> C
    A --> P4
    A --> P5

    B --> D((∅))
    B --> E((∅))
    B --> F["[0,4] × [8,12]"]
    B --> P8((p8))

    F --> P9((p9))
    F --> P3((p3))
    F --> G((∅))
    F --> P1((p1))


    C --> P6((p6))
    C --> P0((p0))
    C --> P2((p2))
    C --> P7((p7))

search: Analogous to binary search trees and tries

insert: Search for the point, split the leaf while there are two points in one region.

delete: Search for the point, remove the point, if the parent has only one point left: delete parent.

QTree::range-search(r <- root, Q)
r: The root of a quadtree, Q: Query-rectangle
R <- region associated with node r
if (R \subseteq Q) then
	report all points below r and return
else if (R \cap Q is empty) then return
 
if (r is a leaf) then
	p <- point stored at r
	if p is not NULL and in Q then report it and return
	else return
for each child v of r do QTree::range-search(v,Q)

Question

What is the height of a quadtree?

Can have very large height for bad distributions of points. Even with $n=3$ points, the height could be arbitrarily large.

There exists a (weaker) bound that depends on the spread factor of points $P$:

$$\begin{array}{r}\frac{\text{sidelength of }R}{\text{minimum distance between points in }P}\end{array}$$

Can show: height $h$ of quadtree is in $\Theta (\log (\text{spread factor}))$.

Complexity to build initial tree: $\Theta (nh)$ worst-case.

Complexity of range search: $\Theta (nh)$ worst-case even if the answer is $\varnothing$.

Quadtrees easily generalize to higher dimensions, but are rarely used beyond dimension 3.

Quadtrees are very easy to compute. No complicated arithmetic, space can potentially be wasteful if points are not well-distributed. We can use quadtrees to store pixelated images.

kd-trees

We have $n$ points $P=\{(x_0,y_0),(x_1,y_1),\cdots ,(x_{n-1},y_{n-1})\}$. Quadtrees split square into quadrants regardless of where points are. kd-tree idea: split the region at upper median of coordinates. Each node of the kd-tree keeps track of a splitting line in one dimension.

Convention: Points on split lines belong to right/top side. Continue splitting, switching between vertical and horizontal lines, until every point is in a separate region.

Build kd-tree with initial split by $x$ on points $P$:

• If $|P|\le 1$ create a leaf and return
• Else $X:=$ randomized-quick-select(P, n/2) (select by $x$-coordinate
• Partition $P$ by $x$-coordinate into $P_{x<X}$ and $P_{x\ge X}$. $\lfloor \frac{n}{2}\rfloor$ points on one side and $\lceil \frac{n}{2}\rceil$ points on the other.
• Create left subtree recursively (splitting by $y$) for points $P_{x<X}$.
• Create right subtree recursively (splitting by $y$) for points $P_{x\ge X}$.

Run-time: Find $X$ and partition $P$ in $\Theta (n)$ expected time using randomized-quick-select. Both subtrees have $\approx n/2$ points.

$$\begin{array}{r}{T}^{\text{exp}}(n)=2T^{\text{exp}}(n/2)+O(n)\end{array}$$

This resolve to $\Theta (n\log n)$ expected time. This can be reduced to $\Theta (n\log n)$ worst-case time by pre-sorting.

Height: $h(1)=0,h(n)\le h(\lceil n/2\rceil )+1$. This resolves to $O(\log n)$ (tight).

Space: All interior nodes have exactly two children. Therefore have $n-1$ interior nodes. Space is $\Theta (n)$.

search: as in binary search tree using indicated coordinate.

insert: search, insert as new leaf.

delete: search, remove leaf.

Problem: After insert or delete, the split might no longer be at exact median and the height is no longer guaranteed to be $\lceil {\log }_{2}n\rceil$. We can maintain $O(\log n)$ height by occasionally re-building entire subtrees. But range-search will be slower.

kd-trees do not handle insertion/deletion well.

Range search is exactly as for quad-trees, except that there are only two children and leaves always store points.

We assume that each node stores its associated region. To save space, we could instead pass the region as a parameter and compute the region for each child using the splitting line.

We spend $O(1)$ time at each visited node.

Observe: $\#$ visited nodes is $O(\beta (n))$ where $\beta (n)$ is the number of “boundary” nodes. Neither $R\subseteq Q$ nor $R\cap Q=\varnothing$.

Can show: $\beta (n)$ satisfies the following recurrence relation:

$$\begin{array}{r}\beta (n)\le 2\beta (n/4)+O(1)\end{array}$$

This implies $\beta (n)\in O(\sqrt{n})$.

Therefore, the complexity of range search in kd-trees is $O(s+\sqrt{n})$.

Storage is $O(n)$, height is $O(\log n)$, construction time is $O(n\log n)$, range search time is $O(s+n^{1-1/d})$. This assumes that $d$ is constant (where $d$ is for $d$-dimensional space).

Both quadtrees and kd-trees are intuitive and simple. But both may be very slow for range searches. Quadtrees are also potentially wasteful in space.

New idea: Range trees

Tree of trees (a multi-level data structure). So fare, nodes in our trees stored a key-value pair and references to children and (maybe) the parent. But we can store much more in a node! Each node stores in another binary search tree. They are wasteful in space, but permit much faster range search.

2-dimensional range trees.

Primary structure: Balanced binary search tree $T$ that stores $P$ and uses $x$-coordinates as keys.

Every node $z$ of $T$ stores an associate structure $T_{\text{ass}}(z)$:

• Let $P(z)$ be all points in subtree of $z$ in $T$ (including point at $z$)
• $T_{\text{ass}}(z)$ stores $P(z)$ in a balanced binary search tree, using the $y$-coordinates as key. Note: Point of $z$ is not necessarily in the root of $T_{\text{ass}}(z)$.

Primary tree $T$ uses $O(n)$ space.

Question

How many nodes do all associate trees together have?

$b$ is a child of $a$, $c$ is a child of $b$. Point of $a$ is only in associate tree $T_{\text{ass}}(a)$. Point of $b$ is in associate trees $T_{\text{ass}}(a)$, $T_{\text{ass}}(b)$. Point of $c$ is in associate trees $T_{\text{ass}}(a)$, $T_{\text{ass}}(b)$, $T_{\text{ass}}(c)$.

Key insight: Point of $z$ is in associate tree $T_{\text{ass}}(u)$ if and only if $u$ is an ancestor of $z$ in $T$.

A range tree with $n$ points uses $O(n\log n)$ space. This is tight for some primary trees.

search: search by $x$-coordinate in $T$.

insert: First, insert point by $x$-coordinate into $T$. Then, walk back up to the root and insert the point by $y$-coordinate in all associate trees $T_{\text{ass}}(z)$ of nodes $z$ on path to the root.

delete: Analogous to insertion.

Problem: We want the binary search trees to be balanced. This makes insert/delete very slow if we use AVL-trees. Solution: Completely rebuild highly unbalanced subtrees. Run-time for insert/delete becomes $O({\log }^{2}n)$ amortized.

BST::range-search-recursive(r <- root, x_1, x_2)
r: root of a binary search tree, x_1, x_2: search keys
Returns keys in subtree at r that are in range [x_1, x_2]
if r = NULL then return
if x_1 <= r.key <= x_2 then
	L <- BST::range-search-recursive(r.left, x_1, x_2)
	R <- BST::range-search-recursive(r.right, x_1, x_2)
	return L \cup r.{key} \cup R
if r.key < x_1 then
	return BST::range-search-recursive(r.right, x_1, x_2)
if r.key > x_2 then
	return BST::range-search-recursive(r.left, x_1, x_2)

Keys are reported in in-order.

BST Range Search analysis. Assume that the binary search tree is balanced. Search for path $P_1$: $O(\log n)$. Search for path $P_2$: $O(\log n)$.

$O(\log n)$ boundary nodes. We spend $O(1)$ time on each. We spend $O(1)$ time per topmost inside node $v$. They are children of boundary nodes, so this takes $O(\log n)$ time. For 1d range search, also report the descendants of $v$.

We have ${\sum }_{z\text{ topmost inside}}\#\{\text{descendants of }z\}\le s$ since subtrees of topmost inside nodes are disjoint. So this takes time $O(s)$ overall.

Run-time for 1d range search: $O(\log n+s)$. This is no faster overall, but topmost inside nodes will be important for 2d range search.

Range search for $Q=[x_1,x_2]\times [y_1,y_2]$ is a two stage process: Perform a range search (on the $x$-coordinates) for the interval $[x_1,x_2]$ in primary tree $T$ (BST::range-search(T, x_1, x_2)). Get boundary and topmost inside nodes as before. For every boundary node, test to see if the corresponding point is within the region $Q$.

For every topmost inside node $v$:

• Let $P(z)$ be the points in the subtree of $z$ in $T$.
• We know that all $x$-coordinates of points in $P(z)$ are within range.
• Recall: $P(z)$ is stored in $T_{\text{ass}}(z)$.
• To find points in $P(z)$ where the $y$-coordinates are within range as well, perform a range search in $T_{\text{ass}}(z)$: BST::range-search(T_ass(z), y_1, y_2).

Range Trees: Range Search Run-Time

$O(\log n)$ time to find boundary and topmost inside nodes in primary tree. There are $O(\log n)$ such nodes. $O(\log n+s_v)$ time for each topmost inside node $v$, where $s_v$ is the number of points in $T_{\text{ass}}(v)$ that are reported. Two topmost inside nodes have no common point in their trees $⟹$ every point is reported in at most one associate structure $⟹$ ${\sum }_{v\text{ topmost inside }}{s}_v\le s$.

Time for range search in range-tree is proportional to

$$\begin{array}{r}\sum _{v\text{ topmost inside}}(\log n+s_v)\in O({\log }^{2}n+s)\end{array}$$

Range trees can be generalized to $d$-dimensional space.

Space is $O(n(\log n{)}^{d-1})$, construction time $O(n(\log n{)}^d)$, range search time is $O(s+(\log n{)}^d)$.

Space/time trade-off compared to kd-trees.

Module 9: String Matching

Pattern Matching

Search for a string (pattern) in a large body of text.

$T[0\dots n-1]$, the text (or haystack) being searched within.

$P[0\dots m-1]$, the pattern (or needle) being searched for.

Strings over alphabet $\Sigma$. Return the first $i$ such that

$$\begin{array}{r}P[j]=T[i+j]\text{ for }0\le j\le m-1\end{array}$$

This is the first occurrence of $P$ in $T$. If $P$ does not occur in $T$, return FAIL.

Definition

Substring $T[i\dots j]0\le i\le j\le n$: a string of length $j-i+1$ which consists of characters $T[i],\dots ,T[j]$ in order.

Definition

A prefix of $T$: A substring $T[0\dots i]$ of $T$ for some $0\le i<n$.

Definition

A suffix of $T$: A substring $T[i\dots n-1]$ of $T$ for some $0\le i\le n-1$.

Pattern matching algorithms consist of guesses and checks. A guess is a position $i$ such that $P$ might start at $T[i]$. Valid guesses (initially) are $0\le i\le n-m$. A check of a guess is a single position $j$ with $0\le j<m$ where we compare $T[i+j]$ to $P[j]$. We must perform $m$ checks of a single correct guess, but may make (many) fewer checks of an incorrect guess.

We will diagram a single run of any pattern matching algorithm by a matrix of checks, where each row represents a single guess.

Brute-force Algorithm. Idea: Check every possible guess.

BruteforcePM(T[0..n-1], P[0..m-1])
T: String of length n (text), P: String of length m (pattern)
for i <- 0 to n-m do
	match <- true
	j <- 0
	while j < m and match do
		if T[i+j] = P[j] then
			J <- j + 1
		else 
			match <- false
	if match then
		return i
return FAIL

Example: $T=abbbababbab$, $P=abba$.

a	b	b	b	a	b	a	b	b	a	b
a	b	b	$a$
	$a$
		$a$
			$a$
				a	b	$b$
					$a$
						a	b	b	a

Question

What is the worst possible input?

$P=a^{m-1}b,T=a^n$.

Worst case performance $\Theta ((n-m+1)m)$. $m\le n/2⟹\Theta (mn)$.

More sophisticated algorithms (KMP and Boyer-Moore). Do extra preprocessing on the pattern $P$. We eliminate guesses based on completed matches and mismatches.

KMP Algorithm

Knuth-Morris-Pratt algorithm.

Compares the pattern to the text in left-to-right. Shifts the pattern more intelligently than the brute-force algorithm. When a mismatch occurs, what is the most we can shift the pattern.

T	a	b	c	d	c	a	b	c	?	?	?
	a	b	c	d	c	a	b	a
						a	b	c	d	c	a

KMP answer: the largest prefix of $P[0\dots j]$ that is a suffix of $P[i\dots j]$.

KMP Failure Array: Preprocess the pattern to find matches of prefixes of the pattern with the pattern itself.

The failure array $F$ of size $m$: $F[j]$ is defined as the length of the largest prefix of $P[0\dots j]$ that is also a suffix of $P[1\dots j]$. $F[0]=0$.

If a mismatch occurs at $P[j]\ne T[i]$ we set $j\leftarrow F[j-1]$.

Consider $P=abacaba$.

$j$	$P[1\dots j]$	$P$	$F[j]$
0	-	abacaba	0
1	b	abacaba	0
2	b$a$	$a$bacaba	1
3	bac	abacaba	0
4	bac$a$	$a$bacaba	1
5	bac$ab$	$ab$acaba	2
6	bac$aba$	$aba$caba	3

KMP(T, P)
F <- failureArrayy(P)
i <- 0
j <- 0
while i < n do
	if T[i] = P[j] then
		if j = m-1 then
			return i-j
		else
			i <- i + 1
			j <- j + 1
	else
		if j > 0 then
			j <- F[j-1]
		else 
			i <- i+1
return -1

$P=abacaba$ $T=abaxyabacabbaababacaba$

a	b	a	x	y	a	b	a	c	a	b	b
a	b	a	c
		(a)	b
			a
				a
					a	b	a	c	a	b	a
									(a)	(b)	a

failureArray(P)
F[0] <- 0
i <- 1
j <- 0
while i < m do
	if P[i] = P[j] then
		F[i] <- j + 1
		i <- i + 1
		j <- j + 1
	else if j > 0 then
		j <- F[j-1]
	else 
		F[i] <- 0
		i <- i + 1

For failureArray, at each iteration of the while loop, either $i$ increases by one, or the guess index $i-j$ increases by at least one $(F[j-1]<j$). There are no more than $2m$ iterations of the while loop. Running time: $\Theta (m)$.

Bayer-Moore Algorithm

Based on three key ideas.

Reverse-order searching: Compare $P$ with a subsequence of $T$ moving backwards.

Bad character jumps: When a mismatch occurs at $T[i]=c$. If $P$ contains $c$, we can shift $P$ to align the last occurrence of $c$ in $P$ with $T[i]$. Otherwise, we can shift $P$ to align $P[0]$ with $T[i+1]$.

Good suffix jumps: If we have already matched a suffix of $P$, then get a mismatch, we can shift $P$ forward to align with the previous occurrence of that suffix. Similar to failure array in KMP.

When a mismatch occurs, Boyer-Moore chooses whichever of bad character or good suffix shifts the pattern further to the right. Can skip large parts of $T$.

$P=aldo$ $T=whereiswaldo$

w	h	e	r	e	i	s	w	a	l	d	o
			o
							o
								a	l	d	o

Last-occurrence function: Preprocess the pattern $P$ and the alphabet $\Sigma$. Build the last-occurrence function $L$ mapping $\Sigma$ to integers. $L(c)$ is defined as the largest index $i$ such that $P[i]=c$ or $-1$ if no such index exists.

Example

Example: $\Sigma =\{a,b,c,d\},P=abacab$.

c	a	b	c	d
$L(c)$	4	5	3	-1

The last-occurrence function can be computed in time $O(m+|\Sigma |)$. In practice, $L$ is stored in a size-$|\Sigma |$ array.

Suffix skip array: Preprocess $P$ to build a table. Suffix skip array $S$ of size $m$: For $0\le i<m$, $S[i]$ is the largest index $j$ such that $P[i+1\dots m-1]=P[j+1\dots j+m-1-i]$ and $P[j]\ne P[i]$. Any negative indices are considered to make the given condition true.

Similar to the KMP failure array, with an extra condition.

Example

$P=bonobobo$

$i$	0	1	2	3	4	5	6	7
$P[i]$	b	o	n	o	b	o	b	o
$S[i]$	-6	-5	-4	-3	2	-1	2	6

Computed similarly to KMP failure array in $\Theta (m)$ time.

boyer-moore(T,P)
L <- last occurrance array computed from P
S <- suffix skip array computed from P
i <- m-1, j <- m-1
while i < n and j >= 0 do
	if T[i] = P[j] then
		i <- i-1
		j <- j-1
	else
		i <- i + m - 1 - min(L[T[i]], S[j])
		j <- m - 1
if j = -1 return i + 1
else return FAIL

Worst-case running-time $\in O(n+|\Sigma |)$. Faster than KMP in practice on English text.

Question

What if we want to search for many patterns $P$ within the same fixed text $T$?

Idea: Preprocess the text $T$ rather than the pattern $P$.

Observation: $P$ is a substring of $T$ if and only if $P$ is a prefix of some suffix of $T$. So we want to store all suffixes of $T$ in a trie.

To save space use a compressed trie, store suffixes implicitly via indices into $T$. This is called a suffix tree.

Text $T$ has $n$ characters and $n+1$ suffixes. We can build the suffix tree by inserting each suffix of $T$ into a compressed trie. This takes time $\Theta (n^2)$. There is a way to build a suffix tree of $T$ in $\Theta (n)$ time.

Suffix trees: String matching

Assume we have a suffix tree of text $T$.

To search for pattern $P$ does not have the final $. $P$ is the prefix of some suffix of $T$. In the uncompressed trie, searching for $P$ would be easy: $P$ exists in $T$ if and only if the search for $P$ until one of the following occurs:

1. If search fails due to “no such child” then $P$ is not in $T$.
2. If we reach end of $P$, say at node $v$, then jump to leaf $\ell$ in subtree of $v$.
3. Else we reach a leaf $\ell =v$ while characters of $P$ left.

Either way, left index at $\ell$ gives the shift that we should check. This takes $O(|P|)$ time.

	Brute-Force	KMP	Boyer-Moore	Suffix trees
Preprocessing:	-	$O(m)$	$O(m+\Vert \Sigma \Vert )$	$O(n^2)$
Search time:	$O(nm)$	$O(n)$	$O(n)$	$O(m)$
Extra space:	-	$O(m)$	$O(m+\Vert \Sigma \Vert )$	$O(n)$

Module 10: Data Compression

Question

The problem: How to store and transmit data efficiently?

Source text: The original data, string $S$ of characters from the source alphabet ${\Sigma }_s$.

Coded text: The encoded data, string $C$ of characters from the code alphabet ${\Sigma }_C$.

Encoding: An algorithm mapping source texts to coded texts.

Decoding: An algorithm mapping coded texts back to their original source text.

$$\begin{array}{r}S\stackrel{\text{encode}}{\to }C\stackrel{\text{transmit}}{\to }C\stackrel{\text{decode}}{\to }\end{array}$$

Source “text” can be any sort of data. The code alphabet ${\Sigma }_C$ is usually $\{0,1\}$. We consider here only lossless compression: Can recover $S$ from $C$ without error.

Main objective: For data compression, we want to minimize the size of the coded text. We will measure the compression ratio:

$$\begin{array}{r}\frac{|C|\cdot \log |{\Sigma }_C|}{|S|\cdot \log |{\Sigma }_S|}\end{array}$$

We consider the efficiency of the encoding/decoding algorithms. We always need time $\Omega (|S|+|C|)$, but sometimes need more.

Observation: No lossless encoding scheme can have compression ratio $<1$ for all input strings.

Definition

A character encoding maps each character in the source alphabet to a string in code alphabet

$$\begin{array}{r}E:{\Sigma }_S\to {\Sigma }_C^{\ast }\end{array}$$

ASCII is a fixed-length code. Each codeword $E(c)$ has the same length. Encoding/decoding is easy, just concatenate/decode the next 7 bits.

Better idea: Variable-length codes.

Motivation: Some letters in ${\Sigma }_S$ occur more often than others. For example, consider the frequency of letters in typical English text. We can use shorter codes for more frequent characters.

So as before, map source alphabet to codewords $E:{\Sigma }_S\to {\Sigma }_C^{\ast }$. Not all codewords have the same length, this ought to make the code text shorter. Morse code is a variable-length code.

Assume that we have some character encoding $E:{\Sigma }_S\to {\Sigma }_C^{\ast }$. Note that $E$ is a dictionary with keys in ${\Sigma }_S$.

singleChar::encoding(E,S,C)
while S is non-empty:
	w <- E.search(S.pop())
	append each bit of w to C

The decoding algorithm must map ${\Sigma }_C^{\ast }$ to ${\Sigma }_S^{\ast }$. The code must be lossless (i.e. uniquely decodable). This is false for Morse code.

From now on only consider prefix-free codes $E$: no codeword is a prefix of another.

This corresponds to a trie with characters of ${\Sigma }_S$ only at the leaves.

Any prefix-free code is uniquely decodable.

prefixFree::decoding(C,S,T)
while C is non-empty:
	z <- T.root
	while z is not a leaf:
		if C is empty or z has no child labelled C.top()
			return "invalid encoding"
		z <- child of z that is labelled with C.pop()
	S.append(character stored at z)

Runtime is $O(|C|)$.

prefixFree::encoding(S,C,T)
E <- array of trie-nodes indexed by \Sigma_S
for all leaves l in T do E[character at l] <- l
while S is non-empty
	w <- empty bitstring
	v <- E[S.pop()]
	while v is not the root
		w.prepend(character from v to its parent)
	append each bit of w to C

Runtime is $O(|T|+|C|)$. We assume that all interior nodes of $T$ have two children, otherwise encoding scheme can be improved. Therefore $|T|\le 2|{\Sigma }_S|-1$ and run-time is $O(|{\Sigma }_S|+|C|)$.

Huffman’s Algorithm

Question

How do we determine the best trie for a given source text $S$?

Idea: Frequent characters should have short codewords. Infrequent characters should be ‘far down’ the trie.

Greedy Algorithm: Always pair up most infrequent characters.

1. We store a set of encoding-tries. Initially each $c\in {\Sigma }_S$ adds “C” (height-0 trie holding $c$).
2. Our tries have weight: Sum of frequencies of all letters in trie.
3. Find the two tries with the minimum weight and merge them.
4. Repeat Step 3 until there is only one trie left.

We can store these tries via a min-ordered heap.

Huffman::encoding(S,C)
S: Input-stream with characters in alphabet
C: Output-stream
f: array indexed by S alpahabet, initially all-0
while S is non-empty do increase f[S.pop()] by 1
Q <- min-oriented priority queue that stores tries
for all c in S alphabet with f[c] > 0 do Q.insert([c], f[c])
while Q.size() > 1 do
	(T_1, f_1) <- Q.delete-min()
	(T_2, f_2) <- Q.delete-min()
	Q.insert(trie with T_1, T_2 as subtries, f_1 + f_2)
T <- Q.delete-min()
C.append(encoding trie T)
Re-set input-stream S
prefixFree::encoding(S,C,T)

The constructed trie is optimal in the sense that $C$ is shortest. The constructed trie is not unique. Decoder does not know the trie (either send the decoding trie along, or send character-frequencies and tie-breaking rules). Encoding must pass through text twice. Cannot use a stream unless it can be re-set.

Run-time:

• Encoding: $O(|{\Sigma }_S|\log |{\Sigma }_S|+|C|)$
• Decoding: $O(|C|)$

Run-Length Encoding

Example of multi-character encoding: multiple source-text characters receive one code-word.

Requires: Input must be a bitstring $({\Sigma }_S=\{0,1\})$. Decoding dictionary is uniquely defined and not explicitly stored.

Good to use when $S$ has long runs.

Send the leftmost bit of $S$. Then send a sequence of integers indicating run lengths. We don’t have to give the bit for runs since they alternate.

Various ideas for encoding one integer $k$:

• Base-2 encoding: $E_{b2}(k):=$ the string $w$ such that $(w{)}_2$ = $k$
• Bijective base-2 encoding: $E_{bb2}(k):=E_{b2}(k+1)$ with the leading 1 removed

$k$	1	2	3	4	5	6	7	8
$E_{b2}(k)$	1	10	11	100	101	110	111	1000
$E_{bb2}(k)$	0	1	00	01	10	11	000	001
	A	B	AA	AB	BA	BB	AAA	AAB

For a sequence of integers, we need a separator-symbol

Question

Can we develop codes that do not need a separator-symbol?

Elias gamma code (for an integer $k$). To encode $k$, take binary representation $E_{b2}(k)$ of $k$. Add leading zeroes so that initial 1 is in the middle. This means adding $\lfloor \log k\rfloor$ leading zeroes.

$k$	1	2	3	4	5	6	7	8
$E_{b2}(k)$	1	10	11	100	101	110	111	1000
$\lfloor \log k\rfloor$	0	1	1	2	2	2	2	3
$E_{\gamma }(k)$	1	010	011	00100	00101	00110	00111	0001000

Definition

To do run-length encoding: Write initial bit to output, determine the run-lengths $k_1,k_2,\dots ,k_d$, write $E_{\gamma }(k_1),E_{\gamma }(k_2),\cdots E_{\gamma }(k_d)$ .

RLE::encoding(S,C)
S:input-stream of bits, C:output-stream
b <- S.top(); C.append(b)
while S is non-empty do
	k <- 1
	while (S is non-empty and S.top() = b) do k++; S.pop()
	w <- empty string
	while k > 1
		C.append(0)
		w.prepend(k mod 2)
		k <- k/2
	w.prepend(1)
	append each bit of w to C
	b <- 1 - b

Claim: A sequence of Elias gamma codes can be decoded uniquely. Each Elias gamma code has form $0^{\ell }1{\ast }^{\ell }$. Can determine $\ell$ by scanning until we encounter a 1. Convert this 1 plus the next $\ell$ bits into the integer.

RLE::decoding(C,S)
C:input-stream of bits, S: output-stream
b <- C.pop()
while C is non-empty
	l <- 0
	while C.pop() = 0 do l++
	k <- 1
	for (j <- 1 to l) do k <- k * 2 + C.pop()
	for (j <- 1 to k) do S.append(b)
	b <- 1 - b

If C.pop() is called when there are no bits left, then $C$ was not valid input.

An all-0 string of length $n$ would be compressed to $0E_{\gamma }(n)$, which has $2\lfloor \log n\rfloor +2\in o(n)$ bits.

Huffman and RLE take advantage of frequent/repeated single characters.

Observation: Certain substrings are much more frequent than others.

Ingredient 1 for Lempel-Ziv-Welch compression: take advantage of such substrings without needing to know beforehand what they are.

ASCII, UTF-8, and RLE use fixed dictionaries.

In Huffman, the dictionary is not fixed, but it is static: the dictionary is the same for the entire encoding/decoding.

Ingredient 2 for LZW: adaptive encoding:

• There is a fixed initial dictionary $D_0$.
• For $i\ge 0$, $D_i$ is used to determine the $i$th character to output,
• After writing the $i$th character to output, encoder updates $D_i$ to $D_{i+1}$

Challenge: Decoder must know how encoder changed the dictionary.

Convert $S$ into a list of code-numbers. Start with a dictionary $D_0$ that stores ASCII. Every step adds to dictionary a multi-character string, using code-numbers 128, 129, $\dots$

Encoding alternates two steps:

• Find longest string $w$ that is already in $D_i$. So all of $w$ can be encoded with one number.
• Add the substring that would have been useful to dictionary: add $wc$ where $c$ is the character that follows $w$ in $S$.

Need to match characters $\to$ use a trie. To find $w$: parse in trie until we reach node $z$ with ‘no such child’ for next character $c$. To add $D_i$: add child of $z$ with link labelled $c$.

LZW::encoding(S,C)
idx <- 128
while S is non-empty do
	z <- root of trie D
	while (S is non-empty and z has a child c labelled S.top())
		z <- c; S.pop()
	C.append(code-number stored at z)
	if S is non-empty
		create child of z labelled S.top() with code-number idx
		idx++

Run-time: $O(|S|)$, assuming we can look up child in $O(1)$ time.

LZW::decoding(C,S)
D ← dictionary that maps {0, . . . , 127} to ASCII
idx ← 128
k ← C.pop(); s ← D.search(k); S.append(s)
while there are more codes in C do
	sprev ← s; k ← C.pop()
	if k < idx do s ← D.search(k)
	else if k = idx do s ← sprev sprev [0] // special situation
	else return FAIL
	append each character of s to S
	D.insert(idx,sprev s[0])
	idx++

Dictionary $D$ maps consecutive integers to words. Use an array.

Decoding run-time is $O(|S|)$. $\Theta (|s|)$ each round to append $s$ to output.

Dictionary wastes space, words may get long. To save space, store strings as code of prefix $+$ one character.

Encoding and decoding take $O(|S|)$. Encoding and decoding need to go through the string only once $⟹$ can do compression while streaming the text.

bzip2

Combine multiple compression schemes. Key ingredient is to use text transforms. Change input into a different text that compresses better.

$T_0\stackrel{\text{Burrows-Wheeler transform}}{\to }{T}_1\stackrel{\text{Move-to-front transform}}{\to }{T}_2\stackrel{\text{Modified RLE}}{\to }{T}_3\stackrel{\text{Huffman encoding}}{\to }{T}_4$

$T_1$ is a permutation. If $T_0$ has repeated substrings, then $T_1$ has long runs of characters. $T_2$ uses ASCII-numbers. If $T_1$ has long runs of characters, then $T_2$ has long runs of 0 and skewed frequencies. If $T_2$ has long runs of zeroes, then $T_3$ is shorter. Skewed frequencies remain. Compresses well since frequencies are skewed.

Move-to-front transform: Dictionary $D:\{0,\dots ,127\}\to$ ASCII is unordered array with MTF. Character $c$ gets mapped to index $i$ with $D[i]=c$. A character in $S$ repeats $k$ times $⟺C$ has run $k-1$ zeroes. We would expect lots of small numbers in the output.

Modified run-length encoding: Input is a list of ‘characters’ in $\{0,\dots ,127\}$. Encode only the runs of $0$s. Encode run-length $k$ with bijective base-2 encoding, using two new characters $A,B$.

Huffman encoding is the same as before.

Burrows-Wheeler Transform

Given: Source text $S$ as an array with end-sentinel.

Step 1: Write down cyclic shifts. $i$th cyclic shift - move $i$ characters from front to back. We treat end-sentinel $ like any other character.

Observe: Every column contains a permutation of $S$.

Step 2: Sort lexicographically. Use MSD-radix-sort. $\Theta (n)$ strings of length $\Theta (n)⟹\Theta (n^2)$ worst-case time. But usually much faster.

Observation: Every column continues to contain a permutation of $S$.

Step 3: Extract rightmost column.

The Burrows-Wheeler transform consists of the last characters of the cyclic shifts of $S$ after sorting them lexicographically.

Same sorting permutation for cyclic shifts and suffixes. That’s the suffix array $A^s$. Can compute this in $O(n\log n)$ time. Read BWT encoding from it: C[i] = \begin{cases} S[A^s[i] -1] & \text{if } A^s[i] > 0 \\ \ & \text{otherwise} \end{cases}$.

Given string $C$ obtained from BWT encoding. We can reconstruct the first and last column of the matrix of cyclic shifts.

BWT::encoding(C,S)
for all indices i of C
	A[i] <- (C[i], i)
for all indices j of C
	if C[j] = $ break
do
	S.append(character stored in A[j])
	j <- index stored in A[j]
while appended character is not $

BWT encoding cost is $O(n\log n)$. BWT decoding cost is $O(n+|{\Sigma }_S|)$. Encoding and decoding both use $O(n)$ space.

They need all of the text. BWT is a block compression method that compresses one block at a time.

bzip2 encoding cost is $O(n(\log n+|\Sigma |))$ with a big constant. bzip2 decoding cost is $O(n|\Sigma |)$ with a big constant.

Module 11: External Memory

Recall the RAM model of a computer. Any access to a memory location takes the same constant time. This is not realistic.

Typical current computer architecture includes registers, cache L1, L2, main memory, disk or cloud.

Question

How to adapt our algorithms to take the memory hierarchy into account, avoiding transfers as much as possible?

Define a new computer model that models one such ‘gap’ across which we must transfer.

Assumption: During a transfer, we automatically load a whole block. This is realistic.

New objective: Revisit all algorithms with the objective of minimizing block transfers.

Stream based algorithms (with $O(1)$ resets) use $\Theta \left(\frac{n}{B}\right)$ block transfers.

Recall: Dictionaries store $n$ KVPs and support search, insert, and delete. AVL-trees were optimal in time and space in RAM model. $\Theta (\log n)$ run time $⟹O(\log n)$ block transfers per operation. Inserts happen at varying locations of the tree. Nearby nodes are unlikely to be on the same block, typically $\Theta (\log n)$ transfers per operation.

We would like to have fewer block transfers. The goal is $O({\log }_{B}n)$ transfers.

Design a tree-structure that guarantees that many nodes on search-paths are within one block.

Idea: Store complete subtrees with $\log b$ levels in one block of memory. Each block/subtree then covers height $\log b$. Search-path hits $\frac{\log n}{\log b}$ blocks $⟹{\log }_{b}n$ block-transfers. Since $b\in \Theta (B)$, we have ${\log }_{b}n\in \Theta ({\log }_{B}n)$.

View the entire content of a block as one node.

Define multiway-tree: A node can store multiple keys.

Definition

A $d$-node stores $d$ keys, has $d+1$ subtrees, and stored keys are between the keys in the subtrees.

We always have one more subtree than keys.

To allow insert/delete, we permit a varying numbers of keys in nodes. We also rigidly restrict where empty subtrees may be. This gives much smaller height than for AVL-trees $⟹$ fewer block transfers.

Definition

An $a$-$b$-tree (for some $b\ge 3$ and $2\le a\le \lfloor \frac{b}{2}\rfloor$) satisfies

1. Every non-root is a $d$-node for some $a-1\le d\le b-1$.
2. Between $a$ and $b$ subtrees, between $a-1$ and $b-1$ keys.
3. The root is a $d$-node for $1\le d\le b-1$.
4. Between 2 and $b$ subtrees, between $1$ and $b-1$ keys.
5. All empty subtrees are at the same level.

For $2$-$4$-trees, every node has between $1$ and $3$ keys.

Typically, we specify the order $b$ and then set $a=\lfloor \frac{b}{2}\rfloor$. With small height we can store many keys.

Theorem

An $a$-$b$-tree with $n$ keys has $O({\log }_a(n))$ height.

How many keys must an $a$-$b$-tree of height $h$ have?

$$\begin{array}{rl}\#\text{non-root nodes}& \ge \sum _{i=1}^{h}2a^{i-1}=2\sum _{j=0}^{h-1}{a}^j=2\frac{a^h-1}{a-1}\\ n=\#\text{KVPs}& \ge \underset{\text{root}}{\underbrace{1}}+\underset{\ge a-1\text{KVPs at non-root}}{\underbrace{a-1}}2\frac{a^h-1}{a-1}=2a^h-1\end{array}$$

Therefore $h\le {\log }_a\left(\frac{n+1}{2}\right)$.

Search is similar to BST: Compare search-key to keys at node. If not found, continue in appropriate subtree until empty.

abTree::search(k)
z <- root, p <- NULL
while z is not NULL
	let < T_0, k_1, ..., k_d, T_d > be key-subtree list at z
	if k >= k_1 
		i <- maximal index such that k_i <= k
		if k_i = k then return KVP at k_i
		else p <- z, z <- root of T_i
	else p <- z, z <- root of T_0
return "not found, would be in p"

$\#$ visited nodes: $O({\log }_{a}n)$. Finding $i$ is not constant time.

For insert, do abTree::search and add key and empty subtree at leaf. If the leaf had room then we are done. Else overflow: More keys/subtrees than permitted. Resolve overflow by node splitting.

abTree::insert(k)
z <- abTree::search(k)
Add k and an empty subtree in key-subtree-list of z
while z has b keys (overflow -> node split)
	Let < L_0, k_1, ..., k_b, T_b > be a key-subtree list at v
	if (z has no parent) create a parent of z without KVPs
	move upper median k_m of keys to parent p of z
	z' <- new node with < T_0, k_1, ..., k_m-1, T_m-1 > 
	z'' <- new node with < T_m, k_m+1, ..., k_b, T_b > 
	Replace <z> by <z', k_m, z''> in key-subtree-list of p
	z <- p

An $a$-$b$ tree has height $O({\log }_{a}n)$. If $a\approx b/2$, then this height-bound is tight. Level $i$ contains at most $b^i$ nodes. Each node contains at most $b-1$ KVPs. So $n\le b^{h+1}-1$ and $h\in \Omega ({\log }_{b}n)$.

search and insert visit $O({\log }_{a}n)$ nodes. delete can also be implemented with $O({\log }_{a}n)$ node-visits. But usually use lazy deletion, space is cheap in external memory.

Definition

A red-black tree is a binary search tree such that:

• Every node has a colour (red or black),
• Every red node has a black parent (in particular the root is black),
• Any empty subtree $T$ has the same black-depth (number of black nodes on path from root to $T$).

Rather than proving properties or describing operations directly, we convert back to $2$-$4$-trees.

Lemma: Any red-black tree $T$ can be converted into a $2$-$4$-tree $T^{\prime }$.

Black node with $0\le d\le 2$ red children becomes a $(d+1)$-node. This covers all nodes. Empty subtrees on same level due to the same black-depth.

insert can be done in $O(\log n)$ worst-case time. delete can also be done in $O(\log n)$ time.

A $B$-tree is an $a$-$b$-tree tailored to the external memory model. Every node is one block of memory (of size $B$). The order $b$ is chosen maximally such that $(b-1)$-node fits into a block of memory. Typically $b\in \Theta (B)$. $a$ is set to $\lfloor b/2\rfloor$ as before.

search, insert, and delete each requires visiting $\Theta (\text{height})$ nodes. Work within a node is done in internal memory $⟹$ no block-transfer. The height is $\Theta ({\log }_{a}b)=\Theta ({\log }_{B}n)$ $($since $a=\lfloor b/2\rfloor \in \Theta (B))$.

So all operations require $\Theta ({\log }_{B}n)$ block transfers. This is asymptotically optimal.

Hash functions don’t adapt well to external memory. We must occasionally re-hash to keep load factor $\alpha$ small. And re-hashing must load all $n/B$ blocks. This is unacceptably slow.

Goal: Data structure for hash-values that typically uses $O(1)$ block transfers, and never needs to load all blocks.

Idea: Keys $⇝$ hash-values $=$ integers $⇝$ fixed-length bit-strings. Store trie of bit-strings whose leaves are blocks of memory.

Assumption: We store fixed-length bit-strings.

Build trie $D$ (the directory) of bit-strings in internal memory. Stop splitting in $D$ when remaining items fit in one block. Each leaf of $F$ refers to a block of external memory. The blocks store KVPs in no particular order.

search(k): Search for $k$ in $D$ until we reach leaf $\ell$. Load block at $\ell$. Search for $k$ in block. 1 block transfer.

delete(k): search(k) loads block, delete $k$ from block, transfer updated block back. 2 block transfers.

insert(k): Search for $k$ in $D$ until we reach leaf $\ell$. Load block $P$ at $\ell$. If $P$ is at capacity, leaf $\ell$ gets two new children, create two new blocks, split items in $\ell$ by next bit. Insert $k$ into appropriate block. Transfer updated block back. Typically 2-3 block transfers.

If all items in $P$ have the same next bit, then split repeatedly. For big $B$ this is extremely unlikely.

Hashing collisions mean duplicate bit-strings, so all colliding items are in the same block. We do not care how collisions are resolved within the block.

If more than $B$ items have the same hash-value $\to$ if all bit-strings in block are the same, we cannot split. This means either the load factor is too big or the hash-function is bad. We extend the hash function.