CS240 Course Notes

Professor: Arne Storjohann | Term: Fall 2024

Module 1

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

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

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

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

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

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