COMP20007 Design of Algorithms
Brute Force Methods
Lars Kulik
Lecture 5
Semester 1, 2021
1
Brute Force Algorithms
Straightforward problem solving approach, usually based directly on the problem’s statement.
Exhaustive search for solutions is a prime example.
• Selection sort
• String matching
• Closest pair
• Exhaustive search for combinatorial solutions • Graph traversal
2
Example: Selection Sort
We already saw this algorithm:
function SelSort(A[0..n − 1]) for i ← 0 to n − 2 do
min ← i
for j ← i + 1 to n − 1 do
if A[j] < A[min] then min ← j
swap A[i] and A[min]
The complexity is Θ(n2).
We shall soon meet better sorting algorithms.
3
Properties of Sorting Algorithms
A sorting algorithm is
• in-place if it does not require additional memory except, perhaps, for a few units of memory.
• stable if it preserves the relative order of elements that have identical keys.
• input-insensitive if its running time is fairly independent of input properties other than size.
4
Properties of Selection Sort
While running time is quadratic, selection sort makes only about n exchanges.
So: A good algorithm for sorting small collections of large records.
In-place?
Stable?
Input-insensitive? ✎
5
Brute Force String Matching
Pattern p: A string of m characters to search for. Text t: A long string of n characters to search in.
for i ← 0 to n − m do j←0
while j < m and p[j] = t[i + j] do j←j+1
if j = m then return i
return −1
6
Analysing Brute Force String Matching
For each of n−m+1 positions in t, we make up to m comparisons.
Assuming n is much larger than m, this means O(mn) comparisons.
However, for random text over a reasonably large alphabet (as in English), the average running time is linear in n.
There are better algorithms, in particular for smaller alphabets such as binary strings or strings of DNA nucleobases.
But for many purposes, the brute-force algorithm is acceptable. Later we shall see more sophisticated string search.
7
Brute Force Geometric Algorithms: Closest Pair
Problem: Given n points is k-dimensional space, find a pair of points with minimal separating Euclidean distance.
The brute force approach considers each pair in turn (except that once it has found the distance from x to y, it does not need to consider the distance from y to x).
For simplicity, we look at the 2-dimensional case, the points being (x0, y0), (x1, y1), . . . , (xn−1, yn−1).
8
The Closest Pair Problem (Two-Dimensional Case)
y
• •
•
•
••• •
• •
••
• •
9
x
The Closest Pair Problem (Two-Dimensional Case)
y
• •
•
•
••• •
• •
••
• •
9
x
Brute Force Geometric Algorithms: Closest Pair
min ← ∞
for i ← 0 to n − 2 do
for j ← i + 1 to n − 1 do
d ← sqrt((xi − xj)2 + (yi − yj)2) if d < min then
min ← d p1 ← i p2 ← j
return p1, p2
10
Analysing the Closest Pair Algorithm
It is not hard to see that the algorithm is Θ(n2).
Note, however, that we can speed up the algorithm considerably, by utilising the monotonicity of the square root function.
How?
Does this contradict the Θ(n2) claim?
✎
Later we shall see how a clever divide-and-conquer approach leads to a Θ(n log n) algorithm for this problem.
11
Brute Force Summary
Simple, easy to program, widely applicable. Standard approach for small tasks.
Reasonable algorithms for some problems. But: Generally inefficient—does not scale well.
Use brute force for prototyping, or when it is known that input remains small.
12
Exhaustive Search
Problem type:
• Combinatorial decision or optimization problems
• Search for an element with a particular property
• Domain grows exponentially, for example all permutations
The brute-force approach—generate and test:
• Systematically construct all possible solutions
• Evaluate each, keeping track of the best so far
• When all potential solutions have been examined, return the best found
13
Example 1: Travelling Salesperson (TSP)
Find the shortest tour (visiting each node exactly once before returning to the start) in a weighted undirected graph.
a
2
b
a−b−c−d−a : 18 a−b−d−c−a : 11 a−c−b−d−a : 23 a−c−d−b−a : 11 a−d−b−c−a : 23 a−d−c−b−a : 18
573 8
c
1
d
14
Example 2: Knapsack
Given n items with
• weights: w1,w2,...,wn • values: v1,v2,...,vn
• knapsack of capacity W
find the most valuable selection of items that will fit in the knapsack.
15
Example 2: Knapsack
W = 10
w1 = 7 v1 = 42
w4 = 5 v4 = 25
w2 = 3 v2 = 12
knapsack item 1 item 2 item 3 item 4
w3 = 4 v3 = 40
16
Example 2: Knapsack
Set Weight Value
∅ 0 0 {1} 7 42 {2} 3 12 {3} 4 40 {4} 5 25 {1,2} 10 54 {1,3} 11 NF {1,4} 12 NF
Set Weight Value
{2,3} 7 52 {2,4} 8 37 {3,4} 9 65 {1,2,3} 14 NF {1,2,4} 15 NF {1,3,4} 16 NF {2,3,4} 12 NF {1,2,3,4} 19 NF
NF means “not feasible”: exhausts the capacity of the knapsack.
Later we shall consider a better algorithm based on dynamic programming.
17
Comments on Exhaustive Search
Exhaustive search algorithms have acceptable running times only for very small instances.
In many cases there are better alternatives, for example, Eulerian tours, shortest paths, minimum spanning trees, . . .
For some problems, it is known that there is essentially no better alternative.
For a large class of important problems, it appears that there is no better alternative, but we have no proof either way.
18
Hamiltonian Tours
The Hamiltonian tour problem is this:
In a given undirected graph, is there a simple tour (a path that visits each node exactly once, except it returns to the starting node)?
Is there a Hamiltonian tour of this graph?
13 26
45
19
Eulerian Tours
The Eulerian tour problem is this:
In a given undirected graph, is there a path which visits each
edge exactly once?
Is there a Eulerian tour of this graph?
13 26
45
20
Hard and Easy Problems
Recall that by a problem we usually mean a parametric problem: an infinite family of problem “instances”.
The Hamiltonian Tour problem and the Eulerian Tour problem look very similar, but one is hard and the other is easy.
We will see more examples of this phenomenon later.
For many optimization problems we do not know of solutions that are essentially better than exhaustive search (a whole raft of NP-complete problems, including TSP and knapsack).
In those cases we try to find approximation algorithms that are fast and close to the optimal solution.
We return to this idea later. 21
Next Up
Graphs.
22