Unit 5 Brute Force Method
Structure:
5.1 Introduction
Objectives
5.2 Brute Force
Brute force algorithm
5.3 Selection Sort and Bubble Sort
Selection sort
Bubble sort
5.4 Sequential Search and Brute Force String Matching
Sequential search
Brute Force string matching
5.5 Exhaustive Search
Definition
Implementation
Reordering the exhaustive search
Speeding up exhaustive search
Alternatives to the exhaustive search
5.6 Summary
5.7 Glossary
5.8 Terminal Questions
5.9 Answers
5.1 Introduction
In the earlier unit you studied about the mathematical analysis of algorithms.
In this unit you will study about brute force method in detail with algorithms.
Brute force is a problem solving technique wherein we compute a series of
possible answers and test each possible answer for accuracy. It simply tries
all possibilities until a satisfactory solution is found. Once it finds the value
for the best solution it stops. In this unit we will discuss various algorithms
which make use of the brute force method.
Objectives:
After studying this unit, you should be able to:
define brute force method
describe and analyze selection sort and bubble sort
, analyze and compute sequential search and brute force string matching
explain and discuss the exhaustive search
5.2 Brute Force
Let us first define brute force.
Definition - Brute force is defined as a primitive programming technique
where the programmer relies on the processing strength of the computing
system rather than his own intelligence to simplify the problem. Here the
programmer applies appropriate methods to find a series of possible
answers and tests each possible answer for accuracy.
Let us now discuss the brute force algorithm.
5.2.1 Brute force algorithm
Brute force algorithm is a basic algorithm which works through every
possible answer until the correct one is found. We can solve a particular
problem easily using brute force algorithm rather than wasting time on
creating a more elegant solution, especially when the size of the problem is
smal.
A good brute force algorithm should have the following factors in it.
.Smal number of sub solutions
Specific order in the sub solutions
Sub solutions must be evaluated quickly
Let us take an example of counting change.
Consider a cashier who counts some amount of currency with a collection of
notes and coins of different denominations. The cashier must count a
specified sum using the smallest possible number of notes or coins.
Let us now analyze the problem mathematically.
Consider n as number of notes or coins and the set of different
denominations of currency P= ip1. p2,.pn.j.
Let d, denomination of pi
In the Indian system p.= { Rs 1, Rs 2, Rs 5, Rs 10,.) the d = { 1, 2,5, 10.)
If we have to count a given sum of money A we need to find the smallest
subset of P such that d
pie S A.
, Let us represent the subset S withn variables as X =
{*.x2,...
Such that
(1 Pi E S
K n Pi S
For {d1,d2....dn} we have to minimize ass
Xi
i=l
Such that
1
dax = A
i=l
Since each element of X, X={i,x2,..n. is either equal to zero or one,
there will be 2" possible values for any X in an algorithm. The best solution
for brute force algorithm to solve a problem is to compute all the possible
values, given any variable X.
For each possible value of X, we check whether the constraintdai = A
i=l
is satisfied for it or not. A value that satisfies the constraint is called as a
n
feasible solution. An objective function 2 is associated with an
optimization problem determining how good a solution is.
Since there are 2" possible values of X, we assume that the running time of
brute-force solution is Q (2"). The running time needed to determine whether
a possible value of a feasible solution is O(n) and the time required to
compute the objective function is also O(n) is O(n2").
Activity 1
Write a brute force algorithm to compare 25 text characters in an array
and match with one character.
Structure:
5.1 Introduction
Objectives
5.2 Brute Force
Brute force algorithm
5.3 Selection Sort and Bubble Sort
Selection sort
Bubble sort
5.4 Sequential Search and Brute Force String Matching
Sequential search
Brute Force string matching
5.5 Exhaustive Search
Definition
Implementation
Reordering the exhaustive search
Speeding up exhaustive search
Alternatives to the exhaustive search
5.6 Summary
5.7 Glossary
5.8 Terminal Questions
5.9 Answers
5.1 Introduction
In the earlier unit you studied about the mathematical analysis of algorithms.
In this unit you will study about brute force method in detail with algorithms.
Brute force is a problem solving technique wherein we compute a series of
possible answers and test each possible answer for accuracy. It simply tries
all possibilities until a satisfactory solution is found. Once it finds the value
for the best solution it stops. In this unit we will discuss various algorithms
which make use of the brute force method.
Objectives:
After studying this unit, you should be able to:
define brute force method
describe and analyze selection sort and bubble sort
, analyze and compute sequential search and brute force string matching
explain and discuss the exhaustive search
5.2 Brute Force
Let us first define brute force.
Definition - Brute force is defined as a primitive programming technique
where the programmer relies on the processing strength of the computing
system rather than his own intelligence to simplify the problem. Here the
programmer applies appropriate methods to find a series of possible
answers and tests each possible answer for accuracy.
Let us now discuss the brute force algorithm.
5.2.1 Brute force algorithm
Brute force algorithm is a basic algorithm which works through every
possible answer until the correct one is found. We can solve a particular
problem easily using brute force algorithm rather than wasting time on
creating a more elegant solution, especially when the size of the problem is
smal.
A good brute force algorithm should have the following factors in it.
.Smal number of sub solutions
Specific order in the sub solutions
Sub solutions must be evaluated quickly
Let us take an example of counting change.
Consider a cashier who counts some amount of currency with a collection of
notes and coins of different denominations. The cashier must count a
specified sum using the smallest possible number of notes or coins.
Let us now analyze the problem mathematically.
Consider n as number of notes or coins and the set of different
denominations of currency P= ip1. p2,.pn.j.
Let d, denomination of pi
In the Indian system p.= { Rs 1, Rs 2, Rs 5, Rs 10,.) the d = { 1, 2,5, 10.)
If we have to count a given sum of money A we need to find the smallest
subset of P such that d
pie S A.
, Let us represent the subset S withn variables as X =
{*.x2,...
Such that
(1 Pi E S
K n Pi S
For {d1,d2....dn} we have to minimize ass
Xi
i=l
Such that
1
dax = A
i=l
Since each element of X, X={i,x2,..n. is either equal to zero or one,
there will be 2" possible values for any X in an algorithm. The best solution
for brute force algorithm to solve a problem is to compute all the possible
values, given any variable X.
For each possible value of X, we check whether the constraintdai = A
i=l
is satisfied for it or not. A value that satisfies the constraint is called as a
n
feasible solution. An objective function 2 is associated with an
optimization problem determining how good a solution is.
Since there are 2" possible values of X, we assume that the running time of
brute-force solution is Q (2"). The running time needed to determine whether
a possible value of a feasible solution is O(n) and the time required to
compute the objective function is also O(n) is O(n2").
Activity 1
Write a brute force algorithm to compare 25 text characters in an array
and match with one character.
