Design of Algorithms

Brute Force and Exhaustive Search

Brute Force and Exhaustive Search

Table of Contents

Brute Force

Selection sort

SelectionSort(A[0..n-1])
# sort given array by selection sort
# input: array A[0..n-1] of orderable elements
# output: array A[0..n-1] sorted in non-decreasing order
for i=0 to n-2 do
  min = i
  for j=i+1 to n-1 do
    if A[j] < A[min]:
      min = j
  swap A[i] and A[min]

Bubble sort

BubbleSort(A[0..n-1]) 
# sorts a given array by bubble sort
# input: array A[0..n-1] of orderable elements
# output: array A[0..n-1] sorted in non-decreasing order
for i=0 to n-2 do
    for j=0 to n-2-i do
        if A[j+1] < A[j]:
            swap A[j] and A[j+1]
\[C(n) = \sum_{i=0}^{n-2}\sum_{j=0}^{n-2}1=\sum_{i=0}^{n-2}[(n-2)-0+1]\\\ =\sum_{i=0}^{n-2}(n-1-i)=\frac{n(n-1)}{2}\in\Theta(n^2)\]

First application of brute-force approach often results in an algorithm that can be improved with modest effort

SequentialSearch2(A[0..n], K)
# implements sequential search with search key as a sentinel
# input: array A of n elements and search key K
# output: index of first element in A[0..n-1] whose value is equal to K
# or -1 if no such element
A[n] = k 
i = 0
while A[i] != K do
  i++

if i < n:
    return i
else:
    return -1

String matching

BruteForceStringMatch(T[0..n-1], P[0..m-1])
"""
implements brute force string matching
input: array T[0..n-1] of n characters of text
       array P[0..m-1] of m characters of pattern
output: index of first character that starts a matching substring
        -1 if search is unsuccessful
"""
for i = 0 to n-m do:
    j = 0
    while j < m and P[j] = T[i+j] do:
        j++
    if j = m:
        return i
return -1
T = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
P = "aab"

Closest-Pair

BruteforceClosestPair(P):
"""
find distance between two closest points in the plane by brute force
input: list of P of n (>= 2) points p1(x1,y1), ... pn(xn, yn)
output: distance between closest pair of points
"""
d = infinity
for i = 1 to n-1:
    for j = i + 1 to n do
        d = min(d sqrt((p[i].x- p[j].x)^2 + (p[i].y-p[j].y)^2))
return d
\[C(n)=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}2=2\sum_{i=1}^{n-1}(n-i)=n(n-1)\in\Theta(n^2)\]

Travelling Salesman Problem

Knapsack Problem

Assignment Problem


Edit this page.