Decrease-and-Conquer

Contents

• Decrease-and-conquer
• Decrease by constant (Topological sorting)
• Decrease by constant factor (Lighter ball)
• Variable size decrease (Selection problem)

Decrease-and-conquer

Three steps:

• Step 1. Decrease
  Reduce a problem of size $n$ to a subproblem of size $n'$.
• Step 2. Conquer
  Solve the subproblem recursively.
• Step 3. Combine
  Build the solution for the original problem from the subsolution.

Types of decrease-and-conquer

• Decrease by constant. $n' = n - c$ for some constant $c$.
• Decrease by constant factor. $n' = n / c$ for some constant $c$.
• Variable size decrease. $n' = n - c$ for some variable $c$.

Decrease by constant

• Size of the instance is reduced by the same constant in each iteration.
• Decrease by $1$ is common.
• Examples:
  • Array sum
  • Array search
  • Find maximum/minimum element
  • Integer product
  • Exponentiation
  • Topological sorting

Decrease by constant factor

• Size of the instance is reduced by the same constant factor in each iteration.
• Decrease by factor $2$ is common.
• Examples:
  • Binary search
  • Search/insert/delete in balanced search tree
  • Fake coin problem
  • Josephus problem

Variable size decrease

• Size of the instance is reduced by a variable in each iteration.
• Examples:
  • Selection problem
  • Quicksort
  • Search/insert/delete in binary search tree
  • Interpolation search

Decrease by constant

Topological sorting

Source removal algorithm.

Topological sort $=$ order in which vertices are removed that have indegree $0$.

\begin{algorithm}
\begin{algorithmic}
\INPUT Directed graph $G = (V, E)$
\OUTPUT A topological order of $V$, or an error if $G$ has a cycle
\FUNCTION{TopologicalSort}{$G = (V, E)$}
\STATE $n \gets |V|$
\STATE Create array $indegree[1 \ldots n] \gets [0, \ldots, 0]$
\STATE Create dynamic array $toposort \gets [\,]$
\STATE Create queue $Q$
\STATE \{ Calculate in-degree for each vertex \}
\FOR{each vertex $u \in V$}
\FOR{each neighbor $v$ of $u$}
\STATE $indegree[v] \gets indegree[v] + 1$
\ENDFOR
\ENDFOR
\STATE \{ Enqueue vertices with in-degree $0$ \}
\FOR{$v \gets 1$ \TO $n$}
\IF{$indegree[v] = 0$}
\STATE $Q.\text{Enqueue}(v)$
\ENDIF
\ENDFOR
\STATE \{ Process vertices \}
\STATE $count \gets 0$
\WHILE{queue $Q$ is not empty}
\STATE $u \gets Q.\text{Dequeue}()$
\STATE $toposort.\text{Add}(u)$
\STATE $count \gets count + 1$
\STATE \{ Reduce in-degree of neighbors \}
\FOR{each neighbor $v$ of $u$}
\STATE $indegree[v] \gets indegree[v] - 1$
\IF{$indegree[v] = 0$}
\STATE $Q.\text{Enqueue}(v)$
\ENDIF
\ENDFOR
\ENDWHILE
\STATE \{ Check for cycle \}
\IF{$count \neq n$}
\RETURN $\text{Error: Graph contains a cycle}$
\ELSE
\RETURN $toposort$
\ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Decrease by constant factor

Lighter ball

Decrease-by-half algorithm

\begin{algorithm}
\begin{algorithmic}
\INPUT Indices $\ell, \ell+1, \ldots, h$ of $(h - \ell + 1)$ balls
\OUTPUT Index of the lighter ball
\REQUIRE Called as \CALL{LighterBall}{$[1 \ldots n]$} with $n \ge 1$
\FUNCTION{LighterBall}{$[\ell, \ldots, h]$}
\IF{$\ell = h$}
\RETURN $\ell$
\ENDIF
\STATE $half \gets \lfloor (h - \ell + 1) / 2 \rfloor$
\STATE $A \gets$ first $half$ balls $[\ell, \ell + 1, \ldots, \ell + half - 1]$
\STATE $B \gets$ second $half$ balls $[\ell + half, \ldots, \ell + 2 \cdot half - 1]$
\STATE $C \gets$ remaining ball $[h]$ if total number of balls is odd
\STATE weigh sets $A$ and $B$
\IF{$weight(A) < weight(B)$}
\RETURN \CALL{LighterBall}{$A$}
\ENDIF
\IF{$weight(A) > weight(B)$}
\RETURN \CALL{LighterBall}{$B$}
\ENDIF
\IF{$weight(A) = weight(B)$}
\RETURN \CALL{LighterBall}{$C$}
\ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Complexity

Weighings.

$$W(n) = \left. \begin{cases} 0 & \text{if } n = 1,\\ W(\lfloor n/2 \rfloor) + 1 & \text{if } n \ge 2. \end{cases} \right\} = \lfloor \log_2 n \rfloor$$

Time complexity.

$$T(n) = \left. \begin{cases} \Theta(1) & \text{if } n = 1,\\ T(n/2) + \Theta(1) & \text{if } n \ge 2. \end{cases} \right\} \in \Theta(\log n)$$

Decrease-by-half algorithm

\begin{algorithm}
\begin{algorithmic}
\INPUT Indices $\ell, \ell+1, \ldots, h$ of $(h - \ell + 1)$ balls
\OUTPUT Index of the lighter ball
\REQUIRE Called as \CALL{LighterBall}{$[1 \ldots n]$} with $n \ge 1$
\FUNCTION{LighterBall}{$[\ell, \ldots, h]$}
\IF{$\ell = h$}
\RETURN $\ell$
\ENDIF
\IF{$\ell = h - 1$}
\RETURN lighter ball among $\ell$ and $h$
\ENDIF
\STATE $third \gets \lfloor (h - \ell + 1) / 3 \rfloor$
\STATE $A \gets$ first $third$ balls $[\ell, \ldots, \ell + third - 1]$
\STATE $B \gets$ second $third$ balls $[\ell + third, \ldots, \ell + 2 \cdot third - 1]$
\STATE $C \gets$ remaining balls $[\ell + 2 \cdot third, \ldots, h]$
\STATE weigh sets $A$ and $B$
\IF{$weight(A) < weight(B)$}
\RETURN \CALL{LighterBall}{$A$}
\ENDIF
\IF{$weight(A) > weight(B)$}
\RETURN \CALL{LighterBall}{$B$}
\ENDIF
\IF{$weight(A) = weight(B)$}
\RETURN \CALL{LighterBall}{$C$}
\ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Complexity

Weighings.

$$W(n) = \left. \begin{cases} 0 & \text{if } n = 1,\\ 1 & \text{if } n = 2,\\ W(\lceil n/3 \rceil) + 1 & \text{if } n \ge 3. \end{cases} \right\} = \lceil \log_3 n \rceil$$

Time complexity.

$$T(n) = \left. \begin{cases} \Theta(1) & \text{if } n = 1 \text{ or } 2,\\ T(n/3) + \Theta(1) & \text{if } n \ge 3. \end{cases} \right\} \in \Theta(\log n)$$

Variable size decrease

Selection problem

• Easiest cases. Minimum $(k = 1)$, maximum $(k = n)$.
• Hardest case. Median $\left(k = \lfloor n/2 \rfloor\right)$.

Selection algorithms

Partial selection sort

\begin{algorithm}
\begin{algorithmic}
\INPUT Array $A[1 \ldots n]$, integer $k$
\OUTPUT The $k$th smallest element of $A$
\FUNCTION{PartialSelectionSort}{$A[1 \ldots n], k$}
\STATE Run $\text{SelectionSort}$ on $A[1 \ldots n]$ for $k$ iterations to find the $k$ smallest elements in sorted order
\RETURN $k$th smallest element
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Time is $\Theta(kn)$.

Partial heapsort

\begin{algorithm}
\begin{algorithmic}
\INPUT Array $A[1 \ldots n]$, integer $k$
\OUTPUT The $k$th smallest element of $A$
\FUNCTION{PartialHeapsort}{$A[1 \ldots n], k$}
\STATE $H \gets$ construct a min-heap from $A[1 \ldots n]$ in-place \{ $\Theta(n)$ \}
\STATE $H.\text{DeleteMin}()$ $k$ times \{ $\Theta(k \log n)$ \}
\RETURN $k$th smallest element
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Time is $\Theta(n + k \log n)$.

Online selection

\begin{algorithm}
\begin{algorithmic}
\INPUT Array $A[1 \ldots n]$, integer $k$
\OUTPUT The $k$th smallest element of $A$
\FUNCTION{OnlineSelection}{$A[1 \ldots n], k$}
\STATE $H \gets$ construct a $k$-sized max-heap from $A[1 \ldots k]$ \{ $\Theta(k)$ \}
\FOR{$i \gets (k + 1)$ \TO $n$}
\IF{$A[i]$ is not more than the heap's maximum}
\STATE $H.\text{Insert}(A[i])$
\STATE $H.\text{DeleteMax}()$
\ENDIF
\ENDFOR
\STATE $k$th smallest element $\gets H.\text{DeleteMax}()$ \{ $\Theta(\log k)$ \}
\RETURN $k$th smallest element
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Time is $\Theta(n \log k)$.

Randomized quickselect

\begin{algorithm}
\begin{algorithmic}
\INPUT Subarray $A[\ell \ldots h]$, rank $k$
\OUTPUT The $k$th smallest element in $A[\ell \ldots h]$
\REQUIRE Invocation \CALL{RandomizedQuickSelect}{$A[1 \ldots n], k$} where $k \in [1, n]$
\FUNCTION{RandomizedQuickSelect}{$A[\ell \ldots h], k$}
\IF{$\ell = h$}
\RETURN $A[\ell]$
\ENDIF
\STATE \{ Randomly select pivot and partition \}
\STATE $s \gets$ \CALL{RandomizedPartition}{$A[\ell \ldots h]$}
\STATE \{ $s$ is the position of pivot in sorted order within $A[\ell \ldots h]$ \}
\STATE $size \gets s - \ell + 1$
\IF{$k = size$}
\RETURN $A[s]$
\ELSE
\IF{$k < size$}
\RETURN  \CALL{RandomizedQuickSelect}{$A[\ell \ldots (s - 1)], k$}
\ELSE
\RETURN \CALL{RandomizedQuickSelect}{$A[(s + 1) \ldots h], k - size$}
\ENDIF
\ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Randomized partition $\rightarrow$ Lomuto

\begin{algorithm}
\begin{algorithmic}
\INPUT Subarray $A[\ell \ldots h]$
\OUTPUT Pivot index after partition
\FUNCTION{RandomizedPartition}{$A[\ell \ldots h]$}
\STATE $i \gets$ uniform random integer in $[\ell \ldots h]$
\STATE $\text{swap}(A[\ell], A[i])$
\RETURN \CALL{LomutoPartition}{$A[\ell \ldots h]$}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\INPUT Subarray $A[\ell \ldots h]$
\OUTPUT Final pivot index
\FUNCTION{LomutoPartition}{$A[\ell \ldots h]$}
\STATE $pivot \gets A[\ell]$ \{ first element is the pivot \}
\STATE $i \gets \ell$
\FOR{$j \gets \ell + 1$ \TO $h$}
\IF{$A[j] \le pivot$}
\STATE $i \gets i + 1$
\STATE $\text{swap}(A[i], A[j])$
\ENDIF
\ENDFOR
\STATE $\text{swap}(A[\ell], A[i])$
\RETURN $i$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Randomized partition $\rightarrow$ Hoare

\begin{algorithm}
\begin{algorithmic}
\INPUT Subarray $A[\ell \ldots h]$
\OUTPUT Pivot index after Hoare partition
\FUNCTION{RandomizedPartition}{$A[\ell \ldots h]$}
\STATE $i \gets$ uniform random integer in $[\ell \ldots h]$
\STATE $\text{swap}(A[\ell], A[i])$
\RETURN \CALL{HoarePartition}{$A[\ell \ldots h]$}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\INPUT Subarray $A[\ell \ldots h]$
\OUTPUT Partition index $j$
\FUNCTION{HoarePartition}{$A[\ell \ldots h]$}
\STATE $pivot \gets A[\ell]$ \{ first element is the pivot \}
\STATE $i \gets \ell$; $j \gets h + 1$
\WHILE{$true$}
\STATE $i \gets i + 1$
\WHILE{$i < h$ \AND $A[i] < pivot$}
\STATE $i \gets i + 1$
\ENDWHILE
\STATE $j \gets j - 1$
\WHILE{$j > \ell$ \AND $pivot < A[j]$}
\STATE $j \gets j - 1$
\ENDWHILE
\IF{$i \ge j$}
\BREAK
\ELSE
\STATE $\text{swap}(A[i], A[j])$
\ENDIF
\ENDWHILE
\STATE $\text{swap}(A[\ell], A[j])$
\RETURN $j$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}