Brute-Force Algorithm.
The “Brute-Force” algorithm is actually the most
straight forward approach to solving a problem.
This technique usually involves direct computation
based on the problem’s statement and the
definition of the concepts involved.
‘’Brute force’’ - the simplest of
the design strategies
-Just do it : the brute-force strategy is easiest
to apply.!
-Time Complexity : Results in ‘’Brute Force’’
algorithm that can be improved with a modest
amount of time.!
-Simplicity : Brute force is important due to its
wide applicability and simplicity.
Brute-Force Algorithm
vs Other Algorithm.
-Brute force algorithms : select each number and
compare it with all other numbers.
~Time complexity : O(n^2)
-Better algorithms : use quicksort to sort the
sequence and compare each adjacent two numbers.
~Time complexity : O(nlogn)
-
Brute-Force Algorithm
vs Other Algorithm.
Best algorithms: let sum = 0; foreach (value in
sequence) sum = sum ^ value ;(^ is xor operator).
Finally, sum is equal to the single number.
~Time Complexity : O(n)
Nusrat Jahan
ID:171-15-1405
Section : PC-A
Dept of CSE,DIU
Brute-Force Algorithm & it’s
Application.
First, unlike some of the other strategies, brute
force is applicable to a very wide variety of
problems. Its used for many elementary but
algorithmic tasks such as computing the sum of n n
umbers, finding the largest element in a list and so
on.
Brute-Force Algorithm & it’s
Application.
Second, for some important problems like sorting,
searching, matrix multiplication, string matching—
the brute-force approach with reasonable
algorithms of at least some practical value with no
limitation on instance size.
Brute-Force Algorithm & it’s
Application.
Third, the expense of designing a more efficient
algorithm may be unjustifiable if only a few
instances of a problem need to be solved and a “
’’brute-force’’ algorithm can solve those instances
with acceptable speed.
Brute-Force Algorithm & it’s
Application.
Finally, a “brute-force” algorithm can serve an
important theoretical or educational purpose as a
yardstick with which to judge more efficient
alternatives for solving a problem.
Jahidur Rahman Fahim
ID:171-15-149
Section : PC-A
Dept of CSE,DIU
Brute-Force Algorithm in
Selection Sort
Scan the list repeatedly to find the elements, one
at a time, in an nondecreasing order. –On the I’th
pass through the list, search for the smallest item
among the last n - i elements and swap it with A[i]
. After n - 1 passes, the list is sorted.
Brute-Force Algorithm in
Selection Sort.
Algorithm Selection Sort : (A[0..n-1])
//Sorts a given array
//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]
Brute-Force Algorithm in
Selection Sort.
~Input Size: number of Elements in Array •
~Basic Operation: Comparison of array Elements
A[j] < A[min] •
~Case Complexity: Every Case
Brute-Force Algorithm in String
Matching.
~Align the pattern against the first m characters
of the text and start matching the corresponding p
airs of characters from left to right until all m pai
rs match. But, if a mismatching pair is found, th
en the pattern is shift one position to the right an
d character comparisons are resumed.
~The goal is to find i - the index of the leftmost
character of the first matching substring in the te
xt
– such that ti = p0,….ti+j = pj, …..t i+m-1 = pm-1
Brute-Force Algorithm in String
Matching.
Algorithm BruteForceStringMatching (T[0..n - 1], P[0..m - 1])
//Implements string matching
//Input: An array T[0..n - 1] of n characters representing a text
// an array P[0..m - 1] of m characters representing a pattern
//Output: The position of the first character in the text that star
ts the first
// matching substring if the search is successful and -1 otherwise.
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 return i
return -1
Brute-Force Algorithm in String
Matching Complexity
Rasel Uddin Durjoy
ID:171-15-1414
Section : PC-A
Dept of CSE,DIU
Brute Force Algorithm
Advantage, Disadvantages
~Brute Force Algorithm : The ‘’brute-force’’
algorithm is actually the most straight forward
approach to solving a problem. This technique
usually involves direct computation based on the
problem’s statement and the definition of the
concepts involved.
Brute Force Algorithm
Advantage, Disadvantages
~Example : computing factorial of a numbe
r – the input is assumed to be 'n'. Now
, we know the problem statement clearly
, so we can directly compute the result as
'1*2*3*...*n'
Advantages
~This method is used by default to solve some pro
blems such as sorting, searching, matrix multiplic-
ation, binomial expansion etc.
~used for solving smaller instances or modules of a
larger problem.
Disadvantages
~It is inefficient and hence useless when dealing
with homogeneous problems of higher complexity.!
