Brute Force

Contents

• Exhaustive search
  • Linear search
  • String matching
  • Closest pair
  • Traveling salesperson problem (TSP)
  • Knapsack problem
  • Maximum subarray sum
• Straightforward approach
  • Counting inversions
  • Random permutation generation

Brute force

• There are two interpretations of brute force search
  1. Exhaustive search
  2. Straightforward approach

Exhaustive search

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{ExhaustiveSearch}{}
\FOR{each solution $\mathcal{S}$ in the search space}
\IF{solution $\mathcal{S}$ is valid}
\STATE \textbf{print} solution $\mathcal{S}$
\ENDIF
\ENDFOR
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Negatives

• Combinatorial explosion or curse of dimensionality

Positives

• Might be the only technique that works for some problems (e.g. linear search)
• Might be used for benchmarking solutions
• Exhaustive search + pruning = Backtracking; backtracking is a very powerful algorithm design technique
• Might be fast for small instances of problems (e.g. insertion sort is used to sort subarrays of size $\le 30$)
• Used to find the shortest proofs or axioms in mathematics
• Used in computer-generated/aided proofs
• Benchmarking cryptographic algorithms using brute force attack
• Used in games where computer is a player

String matching

Example:
Text: abaabbaab
Pattern: abba
Output: Index $4$

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{StringMatching}{$T[1 \ldots n], P[1 \ldots m]$}
\FOR{$i \gets 0$ \TO $(n - m)$}
\STATE $j \gets 1$
\STATE \{ Check if pattern matches starting at position $i$ \}
\WHILE{$j \le m$ \AND $P[j] = T[i + j]$}
\STATE $j \gets j + 1$
\ENDWHILE
\STATE \{  If we reached end of pattern, match found \}
\IF{$j > m$}
    \RETURN $(i + 1)$ \COMMENT{return starting position (1-indexed)}
\ENDIF
\ENDFOR
\RETURN $-1$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Closest pair

• For every two distinct points $p_i = (x_i, y_i)$ and $p_j = (x_j, y_j)$, the distance between them can be computed as $d(p_i, p_j) = \sqrt{ (x_i - x_j)^2 + (y_i - y_j)^2 }$
• Find the points that leads to smallest such distance

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{ClosestPair}{$x[1 \ldots n], y[1 \ldots n]$}
\STATE $minimum \gets \infty$
\FOR{$i \gets 1$ \TO $(n-1)$}
\FOR{$j \gets (i + 1)$ \TO $n$}
\STATE $distance \gets \sqrt{ (x[i] - x[j])^2 + (y[i] - y[j])^2 }$
\IF{$distance < minimum$}
\STATE $minimum \gets distance$
\STATE $a \gets i$; $b \gets j$
\ENDIF
\ENDFOR
\ENDFOR
\RETURN $\{ (x[a], y[a]), (x[b], y[b]) \}$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Traveling salesperson problem (TSP)

Knapsack problem

\begin{algorithm}
\begin{algorithmic}
\INPUT Item weights $w[1 \ldots n]$, values $v[1 \ldots n]$, capacity $W$
\OUTPUT Maximum value achievable within capacity $W$ (and selected subset)
\FUNCTION{Knapsack}{$w[1 \ldots n], v[1 \ldots n], W$}
\RETURN \CALL{KnapsackRec}{$W, n$}
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\INPUT Remaining capacity $capacity$, number of items considered $n$
\OUTPUT Best pair $(value, subset)$ using first $n$ items
\FUNCTION{KnapsackRec}{$capacity, n$}
\STATE \{ Base case: no items or no capacity \}
\IF{$n = 0$ \OR $capacity = 0$}
\RETURN $\langle 0, \{ \} \rangle$
\ENDIF
\STATE \{ If current item's weight exceeds capacity, skip it \}
\IF{$w[n] > capacity$}
\RETURN \CALL{KnapsackRec}{$capacity, n-1$}
\ELSE
\STATE \{ Exclude current item \}
\STATE $\langle valueexclude, subsetexclude \rangle \gets$ \CALL{KnapsackRec}{$capacity, n-1$}
\STATE \{ Include current item \}
\STATE $\langle valueinclude, subsetinclude \rangle \gets$ \CALL{KnapsackRec}{$capacity - w[n], n-1$}
\STATE $valueinclude \gets valueinclude + v[n]$
\STATE{}
\STATE \{ Return the better option \}
\IF{$valueinclude > valueexclude$}
\STATE $subsetinclude \gets subsetinclude.\text{Add}(n)$ \COMMENT{ add current item}
\RETURN $\langle valueinclude, subsetinclude \rangle$
\ELSE
\RETURN $\langle valueexclude, subsetexclude \rangle$
\ENDIF
\ENDIF
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Maximum subarray sum

Example:
Input: $[-2, 1, -3, 4, -1, 2, 1, -5, 4]$
Output: $6$

\begin{algorithm}
\begin{algorithmic}
\INPUT Array $A[1 \ldots n]$
\OUTPUT Maximum subarray sum
\FUNCTION{MaxSubarraySum-BruteForce}{$A[1 \ldots n]$}
\STATE $maxsum \gets -\infty$
\STATE \{ Consider all possible starting points \}
\FOR{$start \gets 1$ \TO $n$}
\STATE \{ Consider all possible ending points \}
\FOR{$end \gets start$ \TO $n$}
\STATE $currentsum \gets 0$
\STATE \{ Calculate sum from start to end \}
\FOR{$k \gets start$ \TO $end$}
\STATE $currentsum \gets currentsum + A[k]$
\ENDFOR
\STATE \{ Update maximum sum \}
\IF{$currentsum > maxsum$}
\STATE $maxsum \gets currentsum$
\ENDIF
\ENDFOR
\ENDFOR
\RETURN $maxsum$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\INPUT Array $A[1 \ldots n]$
\OUTPUT Maximum subarray sum
\FUNCTION{MaxSubarraySum-BruteForceImproved}{$A[1 \ldots n]$}
\STATE $maxsum \gets -\infty$
\STATE \{ Consider all possible starting points \}
\FOR{$start \gets 1$ \TO $n$}
\STATE $currentsum \gets 0$
\STATE \{ Consider all possible ending points \}
\FOR{$end \gets start$ \TO $n$}
\STATE \{ Update running sum from start to end \}
\STATE $currentsum \gets currentsum + A[end]$
\STATE \{ Update maximum sum \}
\IF{$currentsum > maxsum$}
\STATE $maxsum \gets currentsum$
\ENDIF
\ENDFOR
\ENDFOR
\RETURN $maxsum$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Straightforward approach

• Second interpretation of brute force search
• Simplest way of solving a problem

Counting inversions

Example:
Input: $[2, 4, 1, 3, 5]$
Inversion pairs: $(2, 1)$, $(4, 1)$, $(4, 3)$
Output: $3$

\begin{algorithm}
\begin{algorithmic}
\INPUT Array $A[1 \ldots n]$
\OUTPUT Number of inversions in $A$
\FUNCTION{CountInversions}{$A[1 \ldots n]$}
\STATE $count \gets 0$
\FOR{$i \gets 1$ \TO $(n-1)$}
\FOR{$j \gets (i+1)$ \TO $n$}
\IF{$A[i] > A[j]$}
\STATE $count \gets count + 1$
\ENDIF
\ENDFOR
\ENDFOR
\RETURN $count$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Random permutation generation

Does not generate a uniformly random permutation

\begin{algorithm}
\begin{algorithmic}
\INPUT Array $A[1 \ldots n]$
\OUTPUT A non-uniform random permutation of $A$
\FUNCTION{GenerateNonuniformRandomPermutation}{$A[1 \ldots n]$}
\FOR{$i \gets 1$ \TO $(n-1)$}
\STATE $j \gets \text{Random}([1 \ldots n])$
\STATE $\text{swap}(A[i], A[j])$
\ENDFOR
\RETURN $A[1 \ldots n]$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

• There are $n^{n - 1}$ equally-likely sequences of random choices but only $n!$ permutations. When $n^{n - 1}$ is not a multiple of $n!$, we cannot assign an equal number of choice-sequences to each permutation, so some permutations are more likely than others.
• Example: for $n=3$ there are $3^{3−1}=9$ possible choice-sequences but $3! = 6$ permutations, so probabilities cannot all be $1/6$ — the output is biased.
• Intuition: We always allow swapping with earlier positions again, so items get moved multiple times in uneven ways.

Generates a uniformly random permutation

\begin{algorithm}
\begin{algorithmic}
\INPUT Array $A[1 \ldots n]$
\OUTPUT A uniformly random permutation of $A$
\FUNCTION{GenerateUniformRandomPermutation}{$A[1 \ldots n]$}
\FOR{$i \gets 1$ \TO $(n-1)$}
\STATE $j \gets \text{Random}([i \ldots n])$
\STATE $\text{swap}(A[i], A[j])$
\ENDFOR
\RETURN $A[1 \ldots n]$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}