Designing and Analysis of Algorithm
Unit – 2 Brute Force & Exhaustive Search
Brute force is a straightforward approach to solving a problem , usually directly based
on the problem statement and definitions of the concepts involved
What is a brute-force algorithm?
A brute-force algorithm is a problem-solving technique that systematically considers all possible
solutions to a problem in order to find the best one. This approach is often inefficient, but it is
always correct and can be used to solve any problem, given enough time and resources.
Examples of brute-force algorithms
• Searching for an element in a list by checking every element in the list.
• Sorting a list of numbers by comparing every pair of numbers and swapping them if they
are in the wrong order.
• Finding the shortest path between two points on a map by trying every possible path.
• Solving the traveling salesman problem by trying every possible route that the salesman
can take.
Advantages and disadvantages of the brute-force approach
Advantages:
• Brute-force algorithms are simple to design and implement.
• Brute-force algorithms are always correct.
• Brute-force algorithms can be used to solve any problem, given enough time and
resources.
Disadvantages:
• Brute-force algorithms can be very inefficient, especially for large problems.
• Brute-force algorithms may require a lot of memory to store all of the possible solutions.
When to use the brute-force approach
The brute-force approach is typically used when there is no known efficient algorithm for solving a
problem, or when the problem is small enough that the brute-force approach is practical.
Selection Sort
Selection sort is a sorting algorithm that organizes a list of elements by repeatedly
scanning the entire list to find the smallest element and moving it to its proper position in
the sorted list. The process can be broken down into a series of passes, numbered from 0 to
n-2, where n is the total number of elements in the list
We start selection sort by scanning the entire given list to find its smallest element
and exchange it with the first element, putting the smallest element in its final position in
the sorted list. Then we scan the list, starting with the second element, to find the smallest
among the last n-1 elements and exchange it with the second element, putting second
smallest element in its final position. Generally, on the ith pass through the list, which we
number from 0 to n-2, the algorithm searches for the smallest item among the last n-i
elements and swaps its with Ai
After n 1 passes, the list is sorted.
Here is a pseudocode of this algorithm, which, for simplicity, assumes that the list is implemented as an array.
ALGORITHM
SelectionSort(A[0..n-1])
//Sorts a given array by selection sort
//Input: An array A[0..n-1] of orderable elements
//Output: Array A[0..n-1] sorted in ascending 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]
The analysis of selection sort is straightforward. The input's size is given by the number of
elements n; the algorithm's basic operation is the key comparison A[j] A[min]. The number of times
it is executed depends only on the array's size and is given by the following sum:
89 45 68 90 29 34 17
17 45 68 90 29 34 89
17 29 68 90 45 34 89
17 29 34 90 45 68 89
17 29 34 45 90 68 89
17 29 34 45 68 90 89
17 29 34 45 68 89 90
Example of sorting with selection sort. Each line corresponds to one iteration of
the algorithm, i.e., a pass through the list tail to the right of the vertical bar; an element
in bold indicates the smallest element found. Elements to the left of the vertical bar are
in their final positions and are not considered in this and subsequent iterations.
Thus, selection sort is a ⊖(n2) algorithm on all inputs. Note, however, that the
number of key swaps is only ⊖(n) or, more precisely, n-1 (one for each repetition of the i
loop). This property distinguishes selection sort positively from many other sorting
algorithms.
Bubble Sort
Another brute-force application to the sorting problem is to compare
adjacent elements of the list and exchange them if they are out of order. By doing
it repeatedly, we end up "bubbling up" the largest element to the last position on
the list. The next pass bubbles up the second largest element, and so on until, after
n - 1 passes, the list is sorted. Pass i (0 ≤i≤n-2) of bubble sort can be represented by
the following diagram:
Here is a pseudocode of this algorithm.
ALGORITHM
BubbleSort(A[0..n-1])
//Sorts a given array by bubble sort
//Input: An array A[0..n-1] of orderable elements
//Output: Array A[0..n-1] sorted in ascending 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]
The number of key comparisons for the bubble-sort version given
above is the same for all arrays of size n; it is obtained by a sum that is
almost identical to the sum for selection sort:
First two passes of bubble sort on the list 89, 45, 68, 90, 29, 34, 17. A
new line is shown after a swap of two elements is done. The elements to
the right of the vertical bar are in their final positions and are not
considered in subsequent iterations of the algorithm.
The number of key swaps, however, depends on the input. For the
worst case of decreasing arrays, it is the same as the number of key
comparisons:
As is often the case with an application of the brute-force strategy, the
first version of an algorithm obtained can often be improved with a modest
amount of effort. Specifically, we can improve the crude version of bubble
sort given above by exploiting the following observation: if a pass through
the list makes no exchanges, the list has been sorted and we can stop the
algorithm. Though the new version runs faster on some inputs, it is still in
⊖(n²) in the worst and average cases. In fact, even among elementary
sorting methods, bubble sort is an inferior choice, and, if it were not for its
catchy name, you would probably have never heard of it.
A first application of the brute-force approach often results in an
algorithm that can be improved with a modest amount of effort.
Sequential Search
Sequential search, also known as linear search, is a simple and brute-
force algorithm used to find a specific element in a list. It compares each
element in the list with the search key until either a match is found
(successful search) or the entire list has been examined without finding a
match (unsuccessful search).
The algorithm simply compares successive elements of a given list
with a given search key until either a match is encountered (successful
search) or the list is exhausted without finding a match (unsuccessful
search). A simple extra trick is often employed in implementing sequential
search: if we append the search key to the end of the list, the search for the
key will have to be successful, and therefore we can eliminate a check for
the list's end on each iteration of the algorithm. Here is a pseudocode for
this enhanced version, with its input implemented as an array.
Another straightforward improvement can be incorporated in
sequential search if a given list is known to be sorted: searching in such a
list can be stopped as soon as an element greater than or equal to the
search key is encountered.
Sequential search provides an excellent illustration of the brute-force
approach, with its characteristic strength (simplicity) and weakness (inferior
efficiency). The efficiency results obtained for the standard version of
sequential search change for the enhanced version only very slightly, so
that the algorithm remains linear in both worst and average cases.
Brute-Force String Matching
Recall the string-matching problem introduced in Section 1.3: given a string
of n characters called the text and a string of m characters (m <= n) called
the pattern, find a substring of the text that matches the pattern. To put it
more precisely, we want to find i—the index of the leftmost character of
the first matching substring in the text-such that
If matches other than the first one need to be found, a string-
matching algorithm can simply continue working until the entire text is
exhausted.
A brute-force algorithm for the string-matching problem is quite obvious:
align the pattern against the first m characters of the text and start
matching the corresponding pairs of characters from left to right until either
all m pairs of the characters match (then the algorithm can stop) or a
mismatching pair is encountered. In the latter case, shift the pattern one
position to the right and resume character comparisons, starting again with
the first character of the pattern and its counterpart in the text. Note that
the last position in the text which can still be a beginning of a matching
substring is n - m (provided the text's positions are indexed from 0 to n-1).
Beyond that position, there are not enough characters to match the entire
pattern; hence, the algorithm need not make any comparisons there.
An operation of the algorithm is illustrated in above example
Note that for this example, the algorithm shifts the pattern almost always
after a single character comparison. However, the worst case is much
worse: the algorithm may have to make all m comparisons before shifting
the pattern, and this can happen for each of the n-m+1 tries. (Problem 6
asks you to give a specific example of such a situation.) Thus, in the worst
case, the algorithm is in (nm). For a typical word search in a natural
language text, however, we should expect that most shifts would happen
after very few comparisons(check the example again).
Therefore, the average-case efficiency should be considerably better than
the worst-case efficiency. Indeed it is: for searching in random texts, it has
been shown to be linear, i.e., ⊖(n+m) = ⊖(n). There are several more
sophisticated and more efficient algorithms for string searching. The most
widely known of them--by R. Boyer and J. Moore
Closest-Pair and Convex-Hull Problems
by Brute Force
Closest-Pair Problem
The closest-pair problem calls for finding two closest points in a set of
n points. For simplicity, we consider the two-dimensional case, although the
problem can be posed for points in higher-dimensional spaces as well. We
assume that the points in question are specified in a standard fashion by
their (x, y) Cartesian coordinates and that the distance between two points
Pi =(xi, yi) and Pj = (xj, yj) is the standard Euclidean distance
The brute-force approach to solving this problem leads to the
following obvious algorithm: compute the distance between each pair of
distinct points and find a pair with the smallest distance. Of course, we do
not want to compute the distance between the same pair of points twice.
To avoid doing so, we consider only the pairs of points (Pi, Pj) for which i < j.
The basic operation of the algorithm is computing the Euclidean
distance between two points. In the age of electronic calculators with the
square-root but- ton, one might be led to believe that computing the
square root is as simple an operation as, say, addition or multiplication.
Actually, it is not. For starters, even for most integers, square roots are
irrational numbers that therefore can be found only approximately.
Moreover, computing such approximations is not a trivial matter. But, in
fact, computing square roots can be avoided! (Can you think how?) The
trick is to realize that we can simply ignore the square root function and
compare the values (x¡ -xj) 2 + (yi - yj)2 themselves. We can do this because
the smaller a number of which we take the square root, the smaller its
square root, or, as mathematicians say, the square root function is strictly
increasing.
So, if we replaced-sqrt((xi-xj)²+(yi-yj)2) by dsqr(xi-xj)²+(yi-yj)², the basic
operation of the algorithm will be squaring a number. The number of times
it will be executed can be computed as follows:
Convex – Hull Problem
DEFINITION A set of points (finite or infinite) in the plane is called convex if
for any two points P and Q in the set, the entire line segment with the endpoints
at P and Q belongs to the set.
All the sets depicted in Figure 3.4a are convex, and so are a straight line,
a triangle, a rectangle, and, more generally, any convex polygon,' a circle, and
the entire plane. On the other hand, the sets depicted in Figure 3.4b, any finite
set of two or more distinct points, the boundary of any convex polygon, and a
circumference are examples of sets that are not convex.
Now we are ready for the notion of the convex hull. Intuitively, the convex hull
of a set of n points in the plane is the smallest convex polygon that contains all
of them (either inside or on its boundary). If this formulation does not quite fire
up your enthusiasm, consider the problem as one of barricading n sleeping
tigers by a fence of the shortest length. This interpretation is due to D. Harel
[Har92]; it is somewhat lively, however, because the fence posts have to be
erected right at the spots where some of the tigers sleep! There is another,
much tamer interpretation of this notion. Imagine that the points in question
are represented by nails driven into a large sheet of plywood representing the
plane. Take a rubber band and stretch it to include all the nails, then let it snap
into place. The convex hull is the area bounded by the snapped rubber band
(Figure 3.5).
A formal definition of the convex hull that is applicable to arbitrary sets,
including sets of points that happen to lie on the same line, follows.
DEFINITION The convex hull of a set S of points is the smallest convex set
containing S. (The "smallest" requirement means that the convex hull of S must
be a subset of any convex set containing S.)
If S is convex, its convex hull is obviously S itself. If S is a set of two points,
its convex hull is the line segment connecting these points. If S is a set of three
points not on the same line, its convex hull is the triangle with the vertices at the
three points given; if the three points do lie on the same line, the convex hull is
the line segment with its endpoints at the two points that are farthest apart. For
an example of the convex hull for a larger set, see Figure 3.6.
A study of the examples makes the following theorem an expected result.
THEOREM The convex hull of any set S of n > 2 points (not all on the same line)
is a convex polygon with the vertices at some of the points of S. (If all the points
do lie on the same line, the polygon degenerates to a line segment but still with
the endpoints at two points of S.)
The convex-hull problem is the problem of constructing the convex hull for a
given set S of n points. To solve it, we need to find the points that will serve as
the vertices of the polygon in question. Mathematicians call vertices of such a
polygon "extreme points." By definition, an extreme point of a convex set is a
point of this set that is not a middle point of any line segment with endpoints in
the set. For example, the extreme points of a triangle are its three vertices, the
extreme points of a circle are all the points of its circumference, and the
extreme points of the convex hull of the set of eight points in Figure 3.6 are P1,
Ps. P6, P7, and P3.
Extreme points have several special properties other points of a convex set do
not have. One of them is exploited by a very important algorithm called the sim-
plex method (Section 10.1). This algorithm solves linear programming problems,
problems of finding a minimum or a maximum of a linear function of n variables
subject to linear constraints (see Problem 10 in Exercises 3.3 for an example and
Sections 6.6 and 10.1 for a general discussion). Here, however, we are interested
in extreme points because their identification solves the convex-hull problem.
Actually, to solve this problem completely, we need to know a bit more than just
which of n points of a given set are extreme points of the set's convex hull: we
need to know which pairs of points need to be connected to form the boundary
of the convex hull. Note that this issue can also be addressed by listing the
extreme points in a clockwise or a counterclockwise order.
So how can we solve the convex-hull problem in a brute-force manner? If
you do not see an immediate plan for a frontal attack, do not be dismayed: the
convex- hull problem is one with no obvious algorithmic solution. Nevertheless,
there is a simple but inefficient algorithm that is based on the following
observation about line segments making up a boundary of the convex hull: a line
segment connecting two points P; and P of a set of n points is a part of its
convex hull's boundary if and only if all the other points of the set lie on the
same side of the straight line through these two points.2 (Verify this property for
the set in Figure 3.6.) Repeating this test for every pair of points yields a list of
line segments that make up the convex hull's boundary.
A few elementary facts from analytical geometry are needed to implement this
algorithm. First, the straight line through two points (x1, y1). (x2, y2) in the
coordinate plane can be defined by the equation
ax + by = c,
where a= y2- y1,b=x1-x2, c=X1y2-y1x2.
Second, such a line divides the plane into two half-planes: for all the points in
one of them, ax + by c, while for all the points in the other, ax + by < c. (For the
points on the line itself, of course, ax + by c.) Thus, to check whether certain
points lie on the same side of the line, we can simply check whether the
expression ax + by - c has the same sign at each of these points. We leave the
implementation details as an exercise.
What is the time efficiency of this algorithm? It is in O(n³): for each of n(n-1)/2
pairs of distinct points, we may need to find the sign of ax + by-c for each of the
other n - 2 points. There are much more efficient algorithms for this important
problem, and we discuss one of them later in the book.
Convex Hull
Definition: The convex hull of a set of n points in the plane is the smallest convex
polygon that encloses all of these points. A convex polygon is defined as a polygon
in which any line segment connecting two points within the polygon lies entirely
within the polygon or on its boundary.
Intuitive Interpretation: To visualize the concept of a convex hull, think of it as a
fence that you need to build to enclose a group of sleeping tigers in the shortest
possible perimeter. The fence must be such that it covers all the tigers. This lively
interpretation was contributed by D. Harel. Another way to understand it is to
imagine the points as nails on a large sheet of plywood representing the plane.
When you stretch a rubber band to encompass all the nails and then let it snap
into place, the convex hull is the area enclosed by the rubber band.
Formal Definition: The formal definition of the convex hull is applicable to
arbitrary sets, including cases where some points may lie on the same line. It
encompasses the concept of finding the smallest convex polygon that contains all
the points, either inside it or on its boundary.
Applications: The concept of the convex hull is essential in various fields, including
computational geometry, image processing, robotics, and geographic information
systems. It helps in defining boundaries, planning paths, and finding the most
efficient ways to enclose a set of points.
Convex Sets: Convex sets are those sets that are entirely contained within their
convex hull. This includes shapes like circles, rectangles, triangles, and the entire
plane. Convex sets are themselves convex polygons.
Non-Convex Sets: Non-convex sets include sets that are not fully contained within
their convex hull, such as finite sets of two or more distinct points and the
boundaries of convex polygons or circumferences.
Efficient Algorithms: While the brute-force approach to finding the convex hull
involves checking all possible combinations of points, more efficient algorithms
like Graham's scan and the Jarvis march are preferred for practical use due to their
reduced time complexity.
Exhaustive Search
Many important problems require finding an element with a special
property in a domain that grows exponentially (or faster) with an instance size.
Typically, such problems arise in situations that involve-explicitly or implicitly-
combinatorial objects such as permutations, combinations, and subsets of a
given set. Many such problems are optimization problems: they ask to find an
element that maximizes or minimizes some desired characteristic such as a
path's length or an assignment's cost.
Exhaustive search is simply a brute-force approach to combinatorial prob-
lems. It suggests generating each and every element of the problem's domain,
selecting those of them that satisfy all the constraints, and then finding a
desired element (e.g., the one that optimizes some objective function). Note
that though the idea of exhaustive search is quite straightforward, its
implementation typically requires an algorithm for generating certain
combinatorial objects. We delay a discussion of such algorithms until Chapter 5
and assume here that they exist. We illustrate exhaustive search by applying it to
three important problems: the traveling salesman problem, the knapsack
problem, and the assignment problem.
Traveling Salesman Problem
The traveling salesman problem (TSP) has been intriguing researchers
for the last 150 years by its seemingly simple formulation, important
applications, and interesting connections to other combinatorial problems. In
layman's terms, the problem asks to find the shortest tour through a given set of
n cities that visits each city exactly once before returning to the city where it
started. The problem can be conveniently modeled by a weighted graph, with
the graph's vertices representing the cities and the edge weights specifying the
distances. Then the problem can be stated as the problem of finding the
shortest Hamiltonian circuit of the graph. (A Hamiltonian circuit is defined as a
cycle that passes through all the vertices of the graph exactly once. It is named
after the Irish mathematician Sir William Rowan Hamilton (1805-1865), who
became interested in such cycles as an application of his algebraic discoveries.)
It is easy to see that a Hamiltonian circuit can be also defined as a
sequence of n+1 adjacent vertices Vi, Vij,..., Vin-1 Vio, where the first vertex of
the sequence is the same as the last one while all the other n - 1 vertices are
distinct. Further, we can assume, with no loss of generality, that all circuits start
and end at one particular vertex (they are cycles after all, are they not?). Thus,
we can get all the tours by generating all the permutations of n-1 intermediate
cities, compute the tour lengths, and find the shortest among them. Figure 3.7
presents a small instance of the problem and its solution by this method.
An inspection of Figure 3.7 reveals three pairs of tours that differ only by
their direction. Hence, we could cut the number of vertex permutations by half.
We could, for example, choose any two intermediate vertices, say, B and C, and
then consider only permutations in which B precedes C. (This trick implicitly
defines a tour's direction.)
This improvement cannot brighten the efficiency picture much, however.
The total number of permutations needed will still be (n - 1)!/2, which makes
the exhaustive-search approach impractical for all but very small values of n. On
the other hand, if you always see your glass as half-full, you can claim that
cutting the work by half is nothing to sneeze at, even if you solve a small
instance of the problem, especially by hand. Also note that had we not limited
our investigation to the circuits starting at the same vertex, the number of
permutations would have been even larger, by a factor of n.
Knapsack Problem
Here is another well-known problem in algorithmics. Given n items
of known weights w1,..., wn, and values v1,..., Vn and a knapsack of capacity W,
find the most valuable subset of the items that fit into the knapsack. If you do
not like the idea of putting yourself in the shoes of a thief who wants to steal the
most valuable loot that fits into his knapsack, think about a transport plane that
has to deliver the most valuable set of items to a remote location without
exceeding the plane's capacity. Figure 3.8a presents a small instance of the
knapsack problem.
The exhaustive-search approach to this problem leads to generating
all the subsets of the set of n items given, computing the total weight of each
subset to identify feasible subsets (i.e., the ones with the total weight not
exceeding the knapsack's capacity), and finding a subset of the largest value
among them. As an example, the solution to the instance of Figure 3.8a is given
in Figure 3.8b. Since the number of subsets of an n-element set is 2", the
exhaustive search leads to a 2(2") algorithm no matter how efficiently individual
subsets are generated
