Induction

Sort#2 Radix Sort

\begin{algorithm}
\caption{RADIXSORT}
	\begin{algorithmic}
		\Input A linked list of numbers $L = \{a_1 , a_2, . . . , a_n\}$ and $k$, the number of digits.
		\Output $L$ sorted in nondecreasing order.
		\For{$j \gets 1$ \To $k$} 
	        \State Prepare 10 empty lists $L_0,L_1,\cdots,L_9$
	        \While{$L$ is \Not empty}
	            \State $a \gets$ next element in $L$.Delect $a$ from $L$.
	            \State $i \gets j$th digit in $a$.Append $a$ to list $L_i$.
            \EndWhile
            \State $L \gets L_0$
            \For{$i \gets 1$ \To 9}
	            \State $L \gets L,L_i$ \Comment{append list $L_i$ to $L$}
            \EndFor
        \EndFor
        \Return $L$
    \end{algorithmic}
\end{algorithm}

Below is the implementation of the pseudocode in Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def RadixSort(arr, k):
    for j in range(k):
        # Prepare 10 empty lists L_0, L_1, ..., L_9
        lists = [[] for _ in range(10)]
        
        # Distribute elements into the corresponding lists based on the j-th digit
        while arr:
            a = arr.pop(0)  # Delect a from L
            digit = (a // (10 ** j)) % 10  # Get the j-th digit
            lists[digit].append(a)  # Append a to list L_i
        
        # Concatenate all lists back into arr
        arr = []
        for sublist in lists:
            arr.extend(sublist)
    
    return arr

Integer Exponentiation

An efficient method can be deduced as follows. Let m=⌊n/2⌋m = \lfloor n/2 \rfloor, and suppose we know how to compute xmx^m. Then, we have two cases: If nn is even, then xn=(xm)2x^n = (x^m)^2; otherwise, xn=x⋅(xm)2x^n = x \cdot (x^m)^2.

\begin{algorithm}
\caption{EXPREC}
\begin{algorithmic}
\Input A real number $x$ and a nonnegative integet $n$.
\Output $x^n$
\State power($x$,$n$)
\Procedure{power}{$x,m$} \Comment{Compute $x^{m}$}
\If{$m$ = 0}
\State $y \gets 1$
\Else
	\State $y \gets \text{power}(x, \lfloor m/2 \rfloor)$
	\State $y \gets y^{2}$
	\If{$m$ is odd}
		\State $y \gets x \cdot y$
	\EndIf
\EndIf
\Return $y$
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{EXP}
\begin{algorithmic}
\Input A real number $x$ and a nonnegative integet $n$.
\Output $x^n$
\STATE $y \gets 1$
\STATE Let $n$ be $d_k d_{k-1} \dots d_0$ in binary notation.
\FOR{$j \gets k$ \DOWNTO $0$}
    \STATE $y \gets y^{2}$
    \IF{$d_j = 1$}
        \STATE $y \gets x \cdot y$
    \ENDIF
\ENDFOR
\Return $y$
\end{algorithmic}
\end{algorithm}

Below is the implementation of these pseudocodes in Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def exprec(x,n):
    if n == 0:
        return 1
    else:
        y = exprec(x, n // 2)
        y = y * y
        if n % 2 == 1:
            y = x * y
        return y

def exp(x,n):
    y = 1
    binary_n = bin(n)[2:]
    for bit in binary_n:   
        y = y * y
        if bit == '1':
            y = x * y
    return y

Evaluating Polynomials (Horner’s Rule)

Suppose we have a sequence of n+1n+1 real numbers a0,a1,…,ana_0, a_1, \ldots, a_n and a real number xx, and we want to evaluate the polynomial

Pn(x)=anxn+an−1xn−1+⋯+a1x+a0.P_n(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0.

The straightforward approach would be to evaluate each term separately. This approach is very inefficient since it requires n+n−1+⋯+1=n(n+1)/2n + n - 1 + \cdots + 1 = n(n+1)/2 multiplications. A much faster method can be derived by induction as follows. We observe that

Pn(x)=anxn+an−1xn−1+⋯+a1x+a0=((⋯(((anx+an−1)x+an−2)x+an−3)⋯ )x+a1)x+a0.\begin{aligned} P_n(x) &= a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0 \\ &= ((\cdots (((a_n x + a_{n-1})x + a_{n-2})x + a_{n-3})\cdots)x + a_1)x + a_0. \end{aligned}

This evaluation scheme is known as Horner’s rule. Use of this scheme leads to the following more efficient method. Suppose we know how to evaluate

Pn−1(x)=anxn−1+an−1xn−2+⋯+a2x+a1.P_{n-1}(x) = a_n x^{n-1} + a_{n-1} x^{n-2} + \cdots + a_2 x + a_1.

Then, using one more multiplication and one more addition, we have

Pn(x)=xPn−1(x)+a0.P_n(x) = x P_{n-1}(x) + a_0.

This implies Algorithm HORNER.

\begin{algorithm}
\caption{HORNER}
\begin{algorithmic}
\Input A sequence of $n+1$ real numbers $a_0, a_1, \dots, a_n$ and a real number $x$.
\Output $P_n(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0$.
\State $p \gets a_n$
\For{$j \gets 1$ \to $n$}
    \State $p \gets x \cdot p + a_{n-j}$
\EndFor
\Return $p$
\end{algorithmic}
\end{algorithm}

Below is the implementation of the pseudocode in Python:

1
2
3
4
5
6
7
8
def horner(A, x):
    n = len(A)
    p = A[n - 1]

    for j in range(0, n - 1):
        p = x * p + A[n - j - 2]
        
    return p

or

1
2
3
4
5
6
7
8
def horner(A, x):
    n = len(A)
    p = A[-1]
    
    for j in range(1, n):
        p = x * p + A[-j-1]

    return p

Generating Permutations

In this section, we study the problem of generating all permutations of the numbers 1,2,…,n1, 2,\dots, n.

The first algorithm

The algorithm uses a recursive backtracking approach to generate all permutations of an array by systematically swapping elements at different positions and exploring each arrangement through depth-first traversal. Note that interchanging back is necessary to restore the original state of the array for proper backtracking, ensuring all permutations are generated correctly without interference between recursive branches.

\begin{algorithm}
\caption{Permutations1}
\begin{algorithmic}
\Input A positive integer $n$.
\Output All permutations of the numbers $1,2,\cdots,n$.
\For{$j \gets 1$ \to $n$}
\State $P[j] \gets j$
\EndFor
\State \Call{perm1}{$1$}
\Procedure{perm1}{m}
\If{$m = n$}
\State \textbf{output} $P[1 \cdots n]$
\Else
\For{$j \gets m$ \to $n$}
\State interchange $P[j]$ and $P[m]$
\State \Call{perm1}{$m+1$}
\State interchange $P[j]$ and $P[m]$
\EndFor
\EndIf
\EndProcedure
\end{algorithmic}
\end{algorithm}

Below is the implementation of the pseudocode in Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def perm1(m):
    if m == n:
        print(P)
    else:
        for j in range(m, n):
            P[j], P[m] = P[m], P[j]
            perm1(m + 1)
            P[j], P[m] = P[m], P[j]

n = 3
P = [0] * n
for i in range(n):
    P[i] = i+1
perm1(0)

Time complexity: Θ(n⋅n!)\Theta(n \cdot n!).

The Second Algorithm

The algorithm uses backtracking to generate all permutations of the numbers 1 to n by recursively placing each number from n down to 1 in every available position.

\begin{algorithm}
\caption{Permutations2}
\begin{algorithmic}
\Input A positive integer $n$.
\Output All permutations of the numbers $1,2,\cdots,n$.
\For{$j \gets 1$ \to $n$}
\State $P[j] \gets 0$
\EndFor
\State \Call{perm2}{$n$}
\Procedure{perm2}{m}
\If{$m = 0$}
\State \textbf{output} $P[1 \cdots n]$
\Else
\For{$j \gets 1$ \to $n$}
\If{$P[j] = 0$}
\State $P[j] \gets m$
\State \Call{perm2}{$m-1$}
\State $P[j] \gets 0$
\EndIf
\EndFor
\EndIf
\EndProcedure
\end{algorithmic}
\end{algorithm}

Below is the implementation of the pseudocode in Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = 3
P = [0] * n

def perm2(m):
    if m == 0:
        print(P)
    else:
        for j in range(n):
            if P[j] == 0:
                P[j] = m
                perm2(m - 1)
                P[j] = 0

perm2(n)

Finding the Majority Element

Let A[1..n]A[1..n] be a sequence of integers. An integer a in AA is called the majority if it appears more than ⌊n/2⌋\lfloor n/2 \rfloor times in AA.
Observation: If two different elements in the original sequence are removed, then the majority in the original sequence remains the majority in the new sequence.
This observation suggests the following procedure for finding an element that is a candidate for being the majority.

\begin{algorithm}
\caption{MAJORITY}
\begin{algorithmic}
\Input An array $A[1 \dots n]$ of $n$ elements.
\Output The majority element if it exists; otherwise none.
\State $c \gets$ \Call{candidate}{$1$}
\State $count \gets 0$
\For{$j \gets 1$ \to $n$}
\If{$A[j] = c$}
\State $count \gets count + 1$
\EndIf
\EndFor
\If{$count > \lfloor n/2 \rfloor$}
\Return $c$
\Else
\Return none
\EndIf

\Procedure{candidate}{$m$}
\State $j \gets m$
\State $c \gets A[m]$
\State $\textit{count} \gets 1$
\While{$j < n$ \and $\textit{count} > 0$}
    \State $j \gets j + 1$
    \If{$A[j] = c$}
        \State $\textit{count} \gets \textit{count} + 1$
    \Else
        \State $\textit{count} \gets \textit{count} - 1$
    \EndIf
\EndWhile
\If{$j = n$}
    \Return $c$
\Else
    \Return \Call{candidate}{$j + 1$}
\EndIf
\EndProcedure
\end{algorithmic}
\end{algorithm}

Below is the implementation of the pseudocode in Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def candidate(m):
    j = m
    c = A[m]
    count = 1
    while j < n - 1 and count > 0:
        j += 1
        if A[j] == c:
            count += 1
        else:
            count -= 1
    if j == n - 1:
        return c
    else:
        return candidate(j + 1)

def majority(A):
    n = len(A)
    c = candidate(0)
    print("Candidate:", c)
    count = 0
    for j in range(n):
        if A[j] == c:
            count += 1
    if count > n // 2:
        return c
    else:
        return None

Divide and Conquer

The binary search algorithm is a classic example of the divide-and-conquer paradigm. It works on a sorted array by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

\begin{algorithm}
\caption{BINARYSEARCHREC}
\begin{algorithmic}
\Input An array $A[1..n]$ of $n$ elements sorted in nondecreasing order and an element $x$.
\Output $j$ if $x=A[j],1\leq j\leq n$, and $0$ otherwise.

\State binarysearch($1$, $n$)

\Procedure{binarysearch}{$low, high$}
    \If{$low > high$}
        \Return $0$
    \Else
        \State $mid \gets \lfloor (low + high) / 2 \rfloor$
        \If{$x = A[mid]$}
            \Return $mid$
        \ElsIf{$x < A[mid]$}
            \Return \Call{binarysearch}{$low$, $mid-1$}
        \Else
            \Return \Call{binarysearch}{$mid+1$, $high$}
        \EndIf
    \EndIf
\EndProcedure
\end{algorithmic}
\end{algorithm}

Below is the implementation of the pseudocode in Python:

1
2
3
4
5
6
7
8
9
10
11
def binarysearch(low, high):
    if low > high:
        return 0
    else:
        mid = (low + high) // 2
        if x == A[mid]:
            return mid
        elif x < A[mid]:
            return binarysearch(low, mid - 1)
        else:
            return binarysearch(mid + 1, high)

Sort#3 Mergesort

\begin{algorithm}
\caption{MERGESORT}
\begin{algorithmic}
\Input An array $A[1 \dots n]$ of $n$ elements.
\Output $A[1 \dots n]$ sorted in nondecreasing order.
\State \Call{mergesort}{$A$,$1$,$n$}
\Procedure{mergesort}{$A$,$low$,$high$}
\If{$low < high$}
\State $mid \gets \lfloor (low + high) / 2 \rfloor$
\State \Call{mergesort}{$A$,$low$,$mid$}
\State \Call{mergesort}{$A$,$mid+1$,$high$}
\State \Call{merge}{$A$,$low$,$mid$,$high$}
\EndIf
\EndProcedure
\end{algorithmic}
\end{algorithm}

The MERGE algorithm is discussed in Algo#1 Basic Concepts in Algorithmic Analysis | TheValuePoint’s Blog.

\begin{algorithm}
\caption{MERGE}
\begin{algorithmic}
\Input An array $A[1..m]$ of elements and three indices $p,q$, and $r$, with $1 \leq p \leq q < r \leq m$, such that both the subarrays $A[p..q]$ and $A[q+1..r]$ are sorted individually in nondecreasing order.
\Output $A[p..r]$ contains the result of merging the two subarrays $A[p..q]$ and $A[q+1..r]$.
\State \textbf{comment:} $B[p..r]$ is an auxiliary array.
\State $s \gets p$; $t \gets q+1$; $k \gets p$
\While{$s \leq q$ and $t \leq r$}
    \If{$A[s] \leq A[t]$}
        \State $B[k] \gets A[s]$
        \State $s \gets s + 1$
    \Else
        \State $B[k] \gets A[t]$
        \State $t \gets t + 1$
    \EndIf
    \State $k \gets k + 1$
\EndWhile
\If{$s = q + 1$}
    \State $B[k..r] \gets A[t..r]$
\Else
    \State $B[k..r] \gets A[s..q]$
\EndIf
\State $A[p..r] \gets B[p..r]$
\end{algorithmic}
\end{algorithm}
The behavior of Algorithm mergesort.

Below is the implementation of the MERGESORT pseudocode in Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def merge(arr,p,q,r):
    B = [0] * (r - p + 1)
    s = p
    t = q + 1
    k = p
    while s <= q and t <= r:
        if arr[s] <= arr[t]:
            B[k - p] = arr[s]
            s += 1
        else:
            B[k - p] = arr[t]
            t += 1
        k += 1

    if s == q+1:
        while t <= r:
            B[k - p] = arr[t]
            t += 1
            k += 1
    else:
        while s <= q:
            B[k - p] = arr[s]
            s += 1
            k += 1
    
    for i in range(r - p + 1):
        arr[p + i] = B[i]
    return arr

def mergesort(arr, low, high):
    if low < high:
        mid = (low + high) // 2
        mergesort(arr, low, mid)
        mergesort(arr, mid + 1, high)
        merge(arr, low, mid, high)

Compared to the bottom-up sorting approach, merge sort is top-down.

\begin{algorithm}
\caption{BOTTOMUPSORT}
	\begin{algorithmic}
	\Input  An array $A[1..n]$ of $n$ elements.
	\Output $A[1..n]$ sorted in nondecreasing order.
	\State $t \gets 1$
	\While{$t < n$}
		\State $s \gets t; \quad t \gets 2s; \quad i \gets 0$
		\While{$i+t \leq n$}
			\State MERGE($A$, $i + 1$, $i + s$, $i + t$)
			\State $i \gets i+t$
	    \EndWhile
	    \If{$i+s < n$}
	    \State MERGE($A$, $i + 1$, $i + s$, n)
	    \EndIf
    \EndWhile
    \end{algorithmic}
\end{algorithm}

Selection: Finding the Median and the kkth Smallest Element

\begin{algorithm}
\caption{SELECT}
\begin{algorithmic}
\Input An array $A[1..n]$ of $n$ elements and an integer $k$, $1 \leq k \leq n$.
\Output The $k$th smallest element in $A$.
\Procedure{select}{$A,k$}
    \State $n \gets |A|$
    \If{$n < 44$}
        \State sort $A$
        \Return $A[k]$
    \EndIf
    \State $q \gets \lfloor n/5 \rfloor$
    \State Divide $A$ into $q$ groups of $5$ elements each. If $5$ does not divide $n$, discard the remaining elements.
    \State Sort each of the $q$ groups individually and extract its median. Let $M$ be the set of medians.
    \State $mm \gets \text{select}(M,\lceil q/2 \rceil)$ \Comment{median of medians}
    \State Partition $A$ into three arrays:
    \State $A_1 = \{ a \mid a < mm \}$
    \State $A_2 = \{ a \mid a = mm \}$
    \State $A_3 = \{ a \mid a > mm \}$
    \If{$|A_1| \geq k$}
        \Return $\text{select}(A_1,k)$
    \ElsIf{$|A_1| + |A_2| \geq k$}
        \Return $mm$
    \Else
        \Return $\text{select}(A_3,k - |A_1| - |A_2|)$
    \EndIf
\EndProcedure
\end{algorithmic}
\end{algorithm}

Below is the implementation of the pseudocode in Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def select(A,low,high,k):
    p = high - low + 1
    if p < 44:
        sub = A[low:high+1]
        sub.sort()
        return sub[k]
    
    q = p // 5

    M = []

    for i in range(q):
        temp = []
        for j in range(5):
            temp.append(A[low + i*5 + j])
        temp.sort()
        M.append(temp[2])

    M.sort()
    mm = select(M, 0, len(M)-1, (q+1)//2 - 1)

    A_1 = []
    A_2 = []
    A_3 = []

    for i in range(low,high+1):
        if A[i] < mm:
            A_1.append(A[i])
        elif A[i] > mm:
            A_3.append(A[i])
        else:
            A_2.append(A[i])

    if k < len(A_1):
        return select(A_1,0,len(A_1)-1,k)
    elif k < len(A_1) + len(A_2):
        return mm
    else:
        return select(A_3,0,len(A_3)-1,k - len(A_1) - len(A_2))

Analysis of the selection algorithm

Analysis of the selection algorithm.

Assuming A1′A_1' is the set of elements less than the median of medians and A3′A_3' is the set of elements greater than the median of medians, we have

∣A1′∣≥3⌈⌊n/5⌋/2⌉≥32⌊n/5⌋and∣A3′∣≤n−32⌊n/5⌋≤n−32(n−45)=0.7n+1.2|A_1'| \geq 3 \lceil \lfloor n/5 \rfloor /2 \rceil \geq \frac{3}{2}\lfloor n/5 \rfloor \qquad \text{and} \qquad |A_3'| \leq n - \frac{3}{2}\lfloor n/5 \rfloor \leq n-\frac{3}{2} \left(\frac{n-4}{5}\right) = 0.7n+1.2

also

∣A3′∣≥32⌊n/5⌋and∣A1′∣≤0.7n+1.2|A_3'| \geq \frac{3}{2}\lfloor n/5 \rfloor \qquad \text{and} \qquad |A_1'| \leq 0.7n+1.2

Now we are in a position to estimate T(n)T(n), the running time of the algorithm. Steps 1 and 2 of procedure select in the algorithm cost Θ(1)\Theta(1) time each. Step 3 costs Θ(n)\Theta(n) time. Step 4 costs Θ(n)\Theta(n) time, as sorting each group costs a constant amount of time. In fact, sorting each group costs no more than seven comparisons. The cost of Step 5 is T(⌊n/5⌋)T(\lfloor n/5\rfloor). Step 6 takes Θ(n)\Theta(n) time. By the above analysis, the cost of Step 7 is at most T(0.7n+1.2)T(0.7n+1.2). Now we wish to express this ratio in terms of the floor function and get rid of the constant 1.21.2. For this purpose, let us assume that 0.7n+1.2≤⌊0.75n⌋0.7n+1.2\leq\lfloor 0.75n\rfloor. Then, this inequality will be satisfied if 0.7n+1.2≤0.75n−10.7n+1.2\leq 0.75n-1, i.e., if n≥44n\geq 44. This is why we have set the threshold in the algorithm to 4444. We conclude that the cost of this step is at most T(⌊0.75n⌋)T(\lfloor 0.75n\rfloor) for n≥44n\geq 44. This analysis implies the following recurrence for the running time of Algorithm select.

T(n)≤{cif n<44,T(⌊n/5⌋)+T(⌊3n/4⌋)+cnif n≥44,T(n)\leq\begin{cases}c&\text{if }n<44,\\ T(\lfloor n/5\rfloor)+T(\lfloor 3n/4\rfloor)+cn&\text{if }n\geq 44,\end{cases}

for some constant cc that is sufficiently large. Since (1/5)+(3/4)<1(1/5)+(3/4)<1, it follows by Theorem 1.5, that the solution to this recurrence is T(n)=Θ(n)T(n)=\Theta(n). In fact, by Example 1.39,

T(n)≤cn1−1/5−3/4=20cn.T(n)\leq\frac{cn}{1-1/5-3/4}=20cn.

Note that each ratio >0.7n>0.7n results in a different threshold. For instance, choosing 0.7n+1.2≤⌊0.71n⌋0.7n+1.2\leq\lfloor 0.71n\rfloor results in a threshold of about 220220. The following theorem summarizes the main result of this section.
The time complexity of Algorithm select is Θ(n)\Theta(n).

Sort#4 Quicksort

A partitioning algorithm

\begin{algorithm}
\caption{split}
\begin{algorithmic}
\Input An array of elements $A[low..high]$.
\Output (1) $A$ with its elements rearranged as described; (2) $w$, the new position of the splitting element $A[low]$.
    \State $i \gets low$
    \State $x \gets A[low]$
    \For{$j \gets low+1$ \textbf{to} $high$}
        \If{$A[j] \leq x$}
            \State $i \gets i + 1$
            \If{$i \neq j$}
                \State interchange $A[i]$ and $A[j]$
            \EndIf
        \EndIf
    \EndFor
    \State interchange $A[low]$ and $A[i]$
    \State $w \gets i$
    \Return $A$ and $w$
\end{algorithmic}
\end{algorithm}
The behavior of Algorithm split.

The sorting algorithm

\begin{algorithm}
\caption{QUICKSORT}
\begin{algorithmic}
\Input An array $A[1..n]$ of $n$ elements.
\Output $A[1..n]$ sorted in nondecreasing order.
\State \Call{quicksort}{$A$,$1$,$n$}
\Procedure{quicksort}{$A$,$low$,$high$}
\If{$low < high$}
    \State \Call{split}{$A[low..high]$,$w$} \Comment{$w$ is the new position of $A[low]$}
    \State \Call{quicksort}{$A$,$low$,$w-1$}
    \State \Call{quicksort}{$A$,$w+1$,$high$}
\EndIf
\EndProcedure
\end{algorithmic}
\end{algorithm}

Below is the implementation of these pseudocodes in Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def split(A, low, high):
    i = low
    x = A[low]

    for j in range(low + 1, high + 1):
        if A[j] <= x:
            i += 1
            if i != j:
                A[i], A[j] = A[j], A[i]

    A[low], A[i] = A[i], A[low]
    w = i
    return (A,w)

def quicksort(A, low, high):
    if low < high:
        A, w = split(A, low, high)
        A = quicksort(A, low, w - 1)
        A = quicksort(A, w + 1, high)
    return A

In the average case, the time complexity of quicksort is O(nlog⁡n)O(n \log n), while in the worst case, it can degrade to Θ(n2)\Theta(n^2). Although no auxiliary storage is required by the algorithm to store the array elements, the space required by the algorithm is O(n)O(n).

The Closest Pair Problem

\begin{algorithm}
\caption{CLOSESTPAIR}
\begin{algorithmic}
\Input A set $S$ of $n$ points in the plane.
\Output The minimum separation realized by two points in $S$.
\State Sort the points in $S$ in nondecreasing order of their $x$-coordinates.
\State $(\delta, Y) \gets $ \Call{cp}{1, n} 
\Return $\delta$

\Procedure{cp}{$low, high$}
\If{$high - low + 1 \leq 3$}
    \State compute $\delta$ by a straightforward method.
    \State Let $Y$ contain the points in nondecreasing order of $y$-coordinates.
\Else
    \State $mid \gets \lfloor (low + high)/2 \rfloor$
    \State $x_0 \gets x(S[mid])$
    \State $(\delta_l, Y_l) \gets $ \Call{cp}{low, mid}
    \State $(\delta_r, Y_r) \gets $ \Call{cp}{mid + 1, high}
    \State $\delta \gets \min\{\delta_l, \delta_r\}$
    \State $Y \gets$ Merge $Y_l$ with $Y_r$ in nondecreasing order of $y$-coordinates.
    \State $k \gets 0$
    \For{$i \gets 1$ \To $|Y|$} \Comment{Extract $T$ from $Y$}
        \If{$|x(Y[i]) - x_0| \leq \delta$}
            \State $k \gets k + 1$
            \State $T[k] \gets Y[i]$
        \EndIf
    \EndFor \Comment{$k$ is the size of $T$}
    \State $\delta' \gets 2\delta$ \Comment{Initialize $\delta'$ to any number greater than $\delta$}
    \For{$i \gets 1$ \To $k - 1$} \Comment{Compute $\delta'$}
        \For{$j \gets i + 1$ \To $\min\{i + 7, k\}$}
            \If{$d(T[i], T[j]) < \delta'$}
                \State $\delta' \gets d(T[i], T[j])$
            \EndIf
        \EndFor
    \EndFor
    \State $\delta \gets \min\{\delta, \delta'\}$
\EndIf
\Return $(\delta, Y)$
\EndProcedure
\end{algorithmic}
\end{algorithm}

Below is the implementation of the pseudocode in Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import math

def distance(p1: tuple, p2: tuple):
    return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)

def brute_force(S):
    min_dist = float('inf')
    for i in range(len(S)):
        for j in range(i + 1, len(S)):
            min_dist = min(min_dist, distance(S[i], S[j]))
    return min_dist

def cp(S, left, right):
    if right - left <= 3:
        return brute_force(S)

    mid = (left + right) // 2
    x_0 = S[mid][0]

    delta_l = cp(S, left, mid)
    delta_r = cp(S, mid + 1, right)
    delta = min(delta_l, delta_r)

    k = 0
    T = []

    for i in range(0, len(S)):
        if abs(Y[i][0] - x_0) < delta:
            k += 1
            T.append(Y[i])

    delta_prime = 2 * delta

    for i in range(0, k-1):
        for j in range (i+1,min(i+7,k)):
            if distance(T[i], T[j]) < delta_prime:
                delta_prime = distance(T[i], T[j])

    delta_prime = min(delta, delta_prime)
    return delta_prime

# S = np.random.rand(200, 2) * 10
S = sorted(S, key=lambda x: x[0])
Y = sorted(S, key=lambda x: x[1])
delta = cp(S, 0, len(S) - 1)

Dynamic Programming

The Longest Common Subsequence Problem

A simple problem that illustrates the principle of dynamic programming is the following. Given two strings AA and BB of lengths nn and mm, respectively, over an alphabet Σ\Sigma, determine the length of the longest subsequence that is common to both AA and BB. Here, a subsequence of A=a1a2,…,anA = a_1a_2,\ldots,a_n is a string of the form ai1ai2,…,aika_{i_1}a_{i_2},\ldots,a_{i_k}, where each iji_j is between 1 and nn and 1≤i1<i2<⋯<ik≤n1 \leq i_1 < i_2 < \cdots < i_k \leq n. For example, if Σ={x,y,z},A=zxyxyz\Sigma = \{x,y,z\}, A = zxyxyz, and B=xyyzxB = xyyzx, then xyyxyy is a subsequence of length 3 of both AA and BB. However, it is not the longest common subsequence of AA and BB, since the string xyyzxyyz is also a common subsequence of length 4 of both AA and BB. Since these two strings do not have a common subsequence of length greater than 4, the length of the longest common subsequence of AA and BB is 4.
State Transition Equation:

L[i,j]={0if i=0 or j=0L[i−1,j−1]+1if ai=bj,max⁡(L[i−1,j],L[i,j−1])if ai≠bj.L[i, j] = \begin{cases} 0 & \text{if } i = 0 \ \text{or } j = 0\\ L[i - 1, j - 1] + 1 & \text{if } a_i = b_j, \\ \max(L[i - 1, j], L[i, j - 1]) & \text{if } a_i \neq b_j. \end{cases} 

\begin{algorithm}
\caption{LCS}
\begin{algorithmic}
\Input  Two strings $A$ and $B$ of lengths $n$ and $m$, respectively, over an alphabet $\Sigma$.
\Output The length of a longest common subsequence of $A$ and $B$.
\State $L[0, 0] \gets 0$
\For{$i \gets 1$ \To $n$}
    \State $L[i, 0] \gets 0$
\EndFor
\For{$j \gets 1$ \To $m$}
    \State $L[0, j] \gets 0$
\EndFor
\For{$i \gets 1$ \To $n$}
    \For{$j \gets 1$ \To $m$}
        \If{$a_i = b_j$}
            \State $L[i, j] \gets L[i - 1, j - 1] + 1$
        \Else
            \State $L[i, j] \gets \max(L[i - 1, j], L[i, j - 1])$
        \EndIf
    \EndFor
\EndFor
\Return $L[n, m]$
\End{Algorithmic}
\end{algorithm}

Below is the implementation of the pseudocode in Python:

1
2
3
4
5
6
7
8
9
10
11
12
def LCS(A, B):
    n = len(A)
    m = len(B)
    L = [[0] * (m + 1) for _ in range(n + 1)] # 注意下面代码的越界问题
    
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if A[i - 1] == B[j - 1]:
                L[i][j] = L[i - 1][j - 1] + 1
            else:
                L[i][j] = max(L[i - 1][j], L[i][j - 1])
    return L[n][m]

Question Variant: The Longest Common Continuous Subsequence Problem

The longest common continuous subsequence problem, often referred to as the longest common substring problem, modifies the definition of a subsequence to require continuity. Given two strings AA and BB of lengths nn and mm, respectively, over an alphabet Σ\Sigma, the goal is to determine the length of the longest substring that appears consecutively in both AA and BB. Here, a substring of A=a1a2,…,anA = a_1a_2,\ldots,a_n is a string of the form aiai+1…aja_i a_{i+1} \ldots a_j where 1≤i≤j≤n1 \leq i \leq j \leq n. For example, using the same alphabet Σ={x,y,z}\Sigma = \{x,y,z\} with A=zxyxyzA = zxyxyz and B=xyyzxB = xyyzx, the substring xyxy appears consecutively in both strings, as does the single character yy, but the common substring xyyzxyyz from the subsequence example is no longer valid because its characters are not contiguous in both strings. In this case, the longest common substring is xyxy with length 2. The problem illustrates a different dynamic programming approach, where the continuity constraint leads to a recurrence that resets the count when characters do not match, distinguishing it from the standard longest common subsequence problem.
State Transition Equation:

L[i,j]={L[i−1,j−1]+1if ai−1=bj−1,0if ai−1≠bj−1.L[i, j] = \begin{cases} L[i - 1, j - 1] + 1 & \text{if } a_{i-1} = b_{j-1}, \\ 0 & \text{if } a_{i-1} \neq b_{j-1}. \end{cases} 

\begin{algorithm}
\caption{LCCS}
\begin{algorithmic}
\Input  Two strings $A$ and $B$ of lengths $n$ and $m$, respectively, over an alphabet $\Sigma$.
\Output The length of a longest common continuous subsequence of $A$ and $B$.
\State $L[0, 0] \gets 0$
\State $MaxLength \gets 0$
\For{$i \gets 1$ \To $n$}
    \State $L[i, 0] \gets 0$
\EndFor
\For{$j \gets 1$ \To $m$}
    \State $L[0, j] \gets 0$
\EndFor
\For{$i \gets 1$ \To $n$}
    \For{$j \gets 1$ \To $m$}
        \If{$a_{i-1} = b_{j-1}$}
            \State $L[i, j] \gets L[i - 1, j - 1] + 1$
            \State $MaxLength \gets \max(L[i, j],MaxLength)$
        \Else
            \State $L[i,j] \gets 0$
        \EndIf
    \EndFor
\EndFor
\Return $MaxLength$
\End{Algorithmic}
\end{algorithm}

Below is the implementation of the pseudocode in Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def LCCS(A, B):
    n = len(A)
    m = len(B)
    L = [[0] * (m + 1) for _ in range(n + 1)]
    max_length = 0
    
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if A[i - 1] == B[j - 1]:
                L[i][j] = L[i - 1][j - 1] + 1
                max_length = max(max_length, L[i][j])
            else:
                L[i][j] = 0
    return max_length

The All-Pairs Shortest Path Problem: Floyd Algorithm

State Transition Equation:

di,jk={li,jif k=0,min⁡(di,jk−1,di,kk−1+dk,jk−1)if k≥1.d_{i,j}^{k} = \begin{cases} l_{i,j} & \text{if } k = 0, \\ \min(d_{i,j}^{k-1}, d_{i,k}^{k-1} + d_{k,j}^{k-1}) & \text{if } k \geq 1. \end{cases}

Thus, in the kkth iteration, we compute Dk[i,j]D_k[i,j] using the formula

Dk[i,j]=min⁡(Dk−1[i,j],Dk−1[i,k]+Dk−1[k,j]).D_k[i,j] = \min(D_{k-1}[i,j], D_{k-1}[i,k] + D_{k-1}[k,j]). 

\begin{algorithm}
\caption{FLOYD}
\begin{algorithmic}
\Input An $n \times n$ matrix $l[1..n,1..n]$ such that $l[i,j]$ is the length of the edge $(i,j)$ in a directed graph $G = (\{1,2,\dots,n \},E)$.
\Output A matrix $D$ with $D[i,j] = $ the distance from $i$ to $j$.
\State $D \gets l$ \Comment{Copy the input matrix $l$ into $D$}
\For{$k \gets 1$ \To $n$}
    \For{$i \gets 1$ \To $n$}
        \For{$j \gets 1$ \To $n$}
            \State $D[i,j] \gets \min(D[i,j], D[i,k] + D[k,j])$
        \EndFor
    \EndFor
\EndFor
\end{algorithmic}
\end{algorithm}

Below is the implementation of the pseudocode in Python:

1
2
3
4
5
6
7
def floyd(D):
    n = len(D)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    return D

The Knapsack Problem

The knapsack problem can be defined as follows. Let U={u1,u2,…,un}U=\{u_{1},u_{2},\ldots,u_{n}\} be a set of nn items to be packed in a knapsack of size CC. For 1≤j≤n1\leq j\leq n, let sjs_{j} and vjv_{j} be the size and value of the jjth item, respectively. Here CC and sj,vj,1≤j≤ns_{j},v_{j},1\leq j\leq n, are all positive integers. The objective is to fill the knapsack with some items from UU whose total size is at most CC and such that their total value is maximum. Assume without loss of generality that the size of each item does not exceed CC. More formally, given UU of nn items, we want to find a subset S⊆US\subseteq U such that

∑ui∈Svi\sum_{u_{i}\in S}v_{i}

is maximized subject to the constraint

∑ui∈Ssi≤C.\sum_{u_{i}\in S}s_{i}\leq C.

This version of the knapsack problem is sometimes referred to in the literature as the 0/1 knapsack problem.
State Transition Equation:

V[i,j]={0if i=0 or j=0,V[i−1,j]if j<si,max⁡(V[i−1,j],V[i−1,j−si]+vi)if i>0 and j≥si.V[i,j] = \begin{cases} 0 & \text{if } i = 0 \text{ or } j = 0, \\ V[i-1,j] & \text{if } j < s_i, \\ \max(V[i-1,j], V[i-1,j-s_i] + v_i) & \text{if } i > 0 \text{ and } j \geq s_i. \end{cases} 

\begin{algorithm}
\caption{KNAPSACK}
\begin{algorithmic}
\Input A set of items $U=\{u_{1},u_{2},\ldots,u_{n}\}$ with sizes $s_{1},s_{2},\ldots,s_{n}$ and values $v_{1},v_{2},\ldots,v_{n}$ and a knapsack capacity $C$.
\Output The maximum value of the function $\sum_{u_{i}\in S}v_{i}$ subject to $\sum_{u_{i}\in S}s_{i}\leq C$ for some subset of items $S\subseteq U$.

\For{$i\gets 0$ \To $n$}
    \State $V[i,0]\gets 0$
\EndFor
\For{$j\gets 0$ \To $C$}
    \State $V[0,j]\gets 0$
\EndFor
\For{$i\gets 1$ \To $n$}
    \For{$j\gets 1$ \To $C$}
        \State $V[i,j]\gets V[i-1,j]$
        \If{$s_{i}\leq j$}
            \State $V[i,j]\gets \max\{V[i,j], V[i-1,j-s_{i}]+v_{i}\}$
        \EndIf
    \EndFor
\EndFor
\Return $V[n,C]$
\end{algorithmic}
\end{algorithm}

Below is the implementation of the pseudocode in Python:

1
2
3
4
5
6
7
8
9
10
11
def knapsack(S, V, C):
    n = len(S)
    dp = [[0 for _ in range(C + 1)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, C + 1):
            dp[i][j] = dp[i - 1][j]
            if S[i - 1] <= j:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - S[i - 1]] + V[i - 1])

    return dp[n][C]

Traveling Salesman Problem

Exercises 6.34 Give a dynamic programming algorithm for the traveling salesman problem: Given a set of nn cities with their intercity distances, find a tour of minimum length. Here, a tour is a cycle that visits each city exactly once. What is the time complexity of your algorithm? This problem can be solved using dynamic programming in time O(n22n)O(n^{2}2^{n}).