UNIT- II
BRUTE FORCE AND DIVIDE
AND-CONQUER
BRUTE FORCE AND DIVIDE
AND-CONQUER
• Brute Force -Closest-Pair and Convex-Hull
Problems
• Exhaustive Search - Traveling Salesman
Problem – Knapsack Problem -
Assignment problem
• Divide and conquer methodology – Merge
sort – Quick sort – Binary search
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
• Examples:
• Computing an : a * a * a * … * a ( n times)
• Computing n! : The n! can be computed as n*(n-1)* …
*3*2*1
• Multiplication of two matrices : C=AB
• Searching a key from list of elements (Sequential search)
• Selection Sort, Bubble Sort, Sequential Search,
String Matching, Depth-First Search and
Breadth-First Search, Closest-Pair and Convex-Hull
Problems can be solved by Brute Force.
Advantages
• The brute-force strategy is easiest to apply
• 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.
Application of Brute-Force Algorithm
• 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
numbers, finding the largest element in a list and
so on.
• 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.
Application of Brute-Force Algorithm
• 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 can serve an
important theoretical or educational purpose
as a yardstick with which to judge more
efficient alternatives for solving a problem.
Brute-Force Algorithm in Selection Sort
• First scan 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 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 the second smallest element
in its final position in the sorted list.
Brute-Force Algorithm in Selection Sort
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 it with Ai:
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]
• 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 Selection Sort
Brute-Force Algorithm in Selection Sort
The analysis of selection sort is straightforward.
The input size is given by the number of elements n; the
basic operation is the key comparison A [j ] < A[MIN].
The number of times it is executed depends only on the
array size and is given by the following sum:
Thus, selection sort is a Θ(n2) algorithm on all
inputs.
The number of key swaps is only Θ(n), or, more
precisely n – 1.
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.
Bubble Sort
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 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]
Bubble Sort
Bubble Sort
Sequential Search
• the algorithm 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)
Sequential Search
Analysis
Analysis
Brute-force string matching
• The problem is: given a string of n characters
called the text and a string of m (m≤n) characters
called the pattern, find a substring of the text that
matches the pattern.
• The Bruteforce algorithm is to 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 the m pairs of the
characters match or a mismatching pair is
encountered.
Brute-force string matching
Brute-force string matching
Analysis
• The worst case is to make all m comparisons
before shifting the pattern, occurs for nm+1
tries.
• There in the worst case, the algorithm is in θ
(nm).
• The average case is when there can be most
shift after a very few comparisons and it is to
be a linear, ie., θ (n+m) = θ (n).
Closest Pair algorithm
• The closest-pair problem calls for finding the
two closest points in a set of n points.
• Eg: finding distance between airplanes or post
offices, as well as database records, statistical
samples
• One of the important applications of the
closest-pair problem is cluster analysis in
statistics.
Closest Pair algorithm
Euclidean distance d(Pi, Pj) = √[(xi-xj)2 + (yi-yj)2]
The closest pair of points can be computed in O(n2) time
Closest Pair algorithm
Algorithm BruteForceClosestPoints(P)
// P is list of points
dmin ← ∞
for i ← 1 to n-1 do
for j ← i+1 to n do
d ← sqrt((xi-xj)2 + (yi-yj)2)
if d < dmin then
dmin ← d; index1 ← i; index2 ← j
return index1, index2
Closest Pair algorithm
