CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

UNIT II
BRUTE FORCE AND DIVIDE-AND-CONQUER
Brute Force - Closest-Pair and Convex-Hull Problems-Exhaustive Search - Traveling
Salesman Problem - Knapsack Problem - Assignment [Link] and conquer
methodology – Merge sort – Quick sort – Binary search – Multiplication of Large Integers
– Strassen’s Matrix Multiplication-Closest-Pair and Convex-Hull Problems.

PART A
1. Define Brute Force.
Brute Force is a straightforward approach to solve a problem, which is directly
based on the problem statement and definition of the concepts.
Brute Force strategy is one of the easiest approach.

2. What are the types of Brute Force Algorithm?

There are two types of Brute force algorithm. They are
Consecutive integer checking algorithm for computing the greatest common
divisor of two integer[gcd(m,n)]
Definition based algorithm for matrix multiplication.
3. What are the Advantages of Brute Force Approach?
Advantages
It is applicable to a variety of problems.
A brute Force algorithm can be useful for solving small size instances of a
problem.
A brute Force algorithm can serve an important theoretical or educational
purpose.
The brute force approach provides reasonable algorithms of atleast some
practical value with no limitation on instance size for sorting, searching, matrix
multiplication and string matching problem.
4. What is Closest-Pair Problem?
The closest-pair problem calls for finding the two closest points in a set of n points.
It is the simplest of a variety of problems in computational geometry that deals with
proximity of points in the plane or higher-dimensional spaces.
5. What is meant by Convex?
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.
6. What is meant by convex hull?
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

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.)
7. Define exhaustive search.
An exhaustive search, also known as generate and test, is a very general problem-
solving technique that consists of systematically enumerating all possible candidates
for the solution and checking whether each candidate satisfies the problem's
statement.
8. What is Travelling Salesman Problem?
The Travelling Salesman Problem (TSP) is an NP-hard problem in combinatorial
optimization studied in operations research and theoretical computer science.
Given a list of cities and their pairwise distances, the task is to find a shortest possible
tour that visits each city exactly once.

9. What is knapsack?
The knapsack problem, another well-known NP-hard problem.
The Knapsack problem is, given n items of known weights w1, . . . , wn and values
v1, . . . , vn and a knapsack of weight capacity W, find the most valuable subset of the
items that fits into the knapsack.
[Link] is assignment problem?
The assignment problem is one of the fundamental combinatorial optimization
problems in the branch of optimization or operations research in mathematics.
It consists of finding a maximum weight matching in a weighted bipartite graph.
11. Define the divide and conquer method.
Divide & conquer technique is a top-down approach to solve a problem.
The algorithm which follows divide and conquer technique involves 3 steps:
Divide the original problem into a set of sub problems.
Conquer (or Solve) every sub-problem individually, recursive.
Combine the solutions of these sub problems to get the solution of original
problem.
12. What is the binary search?
If ‘q’ is always chosen such that ‘aq’ is the middle element
(that is, q = [(n+1)/2)], then the resulting search algorithm is known as binary
search.
13. What is the time complexity of Binary search? June 2011 & 12
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

Successful searches unsuccessful searches

Θ (1) Θ (log n) Θ (log n) Θ (log n)
Best Average Worst Best ,Average, Worst
14. Define external path length?
The external path length E, is defines analogously as sum of the distance of
all external nodes from the root.
15. Define internal path length.
The internal path length ‘I’ is the sum of the distances of all internal nodes
from the root.
16. Is insertion sort better than the merge sort?
Insertion sort works exceedingly fast on arrays of less then 16 elements,

2
though for large ‘n’ its computing time is O (n ).

17. Give the recurrence relation of divide-and-conquer?

The recurrence relation is
T( n) = g(n) n is small
T(n1) + T(n2) + T(nk) + f(n) otherwise
Where T(n) is the time for DAndC on any input of size n and g(n) is the time to
compute the answer directly for small inputs.
The function f(n) is the time for dividing P and combining the solutions to
subproblems.
18. What are internal nodes?
The circular node is called the internal nodes.
19. Give the recurrence equation for the worst case behavior of merge sort?
Dec 2010
The recurrence equation for the worst case behavior of merge
sort is T(n) = 2T(n/2) + cn for n>1, c is a constant
Total number of comparison required by the merge sort is Θ(n logn)
20. Find the number of comparisons made by the sequential
search in the worst case and best case?
Worst case: The algorithm makes the largest number of key comparisons
among all possible input of size n. Cworst(n)=n
Best Case: The best case inputs will be lists of size n with their first element
equal to search key. Cbest(n)=1
21. What are the objectives of sorting algorithms?
A sorting algorithm is an algorithm that puts elements of a list in a certain order.
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

The most-used orders are numerical order and lexicographical order. Efficient
sorting is important for optimizing the use of other algorithms (such as search
and merge algorithms) that require sorted lists to work correctly;
More formally, the output must satisfy two conditions:
The output is in non-decreasing order (each element is no smaller than the
previous element according to the desired total order)
The output is a permutation (reordering) of the input.
22. What do you meant by Divide and conquer strategy? May 2013
Divide & conquer technique is a top-down approach to solve a problem.
The algorithm which follows divide and conquer technique involves 3
steps:
 Divide the original problem into a set of sub problems.
 Conquer (or Solve) every sub-problem individually, recursive.
 Combine the solutions of these sub problems to get the solution of
original problem.
23. What are the merits of binary search?
A binary search or half-interval search algorithm finds the position of a specified
value (the input "key") within a sorted array.
In each step, the algorithm compares the input key value with the key value of
the middle element of the array.
A binary search halves the number of items to check with each iteration, so
locating an item (or determining its absence) takes logarithmic time
It is faster than the sequential search.
It requires lesser number of key comparisons than the sequential search.
24. Is merge sort stable sorting algorithm?
Yes, merge sort is the stable sorting algorithm.
A sorting algorithm is said to be stable if it preserves the ordering of similar
elements after applying sorting method.
And merge sort is a method which preserves this kind of ordering. Hence merge
sort is a stable sorting algorithm.
25. Give efficiency analysis of divide and conquer?
The efficiency of divide and conquer algorithms is given by recurrences of the
form. T(n) = T(n) n=1
aT(n/b) + f(n) n>1
Where a and b are known constants. We assume that T(1) is known and
n is a power of b ( n=bk).
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

26. What is the idea behind binary search?

A binary search or half-interval search algorithm finds the position of a specified
value (the input "key") within a sorted array.
In each step, the algorithm compares the input key value with the key value of
the middle element of the array.
If the keys match, then a matching element has been found so its index, or
position, is returned.
Otherwise, if the sought key is less than the middle element's key, then the
algorithm repeats its action on the sub-array to the left of the middle element or,
if the input key is greater, on the sub-array to the right.
If the remaining array to be searched is reduced to zero, then the key cannot be
found in the array and a special "Not found" indication is returned.
27. Give the time efficiency and drawback of merge sort
algorithm? Dec 2005

Refer Class Notes

28. What is the difference between quick sort and merge sort? May 2013

Sequential technique binary search technique

This is the simple technique of searching This is the efficient technique of searching
an element an element
This technique require the list to be
This technique does not require the list to
sorted. Then only this method is
be sorted
applicable
The worst case time complexity of this The worst case time complexity of this
technique is O(n) technique is O(log n)

Every element of the list may get Only the mid element of the list is
compared with the key element. compared with key element.

29. What is the difference between sequential and binary search Apr 2013
Sequential technique binary search technique
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

This is the simple technique of searching This is the efficient technique of searching
an element an element

This technique does not require the list to This technique require the list to be
be sorted sorted. Then only this method is applicable

The worst case time complexity of this The worst case time complexity of this
technique is O(n) technique is O(log n)

Every element of the list may get Only the mid element of the list is
compared with the key element. compared with key element.

30. What is the necessary precondition for the binary search ?

For the binary search the list should be sorted either in ascending or descending
order
31. List out two drawbacks of binary search algorithm. Dec 2007
In binary search the elements have to be arranged either in ascending or
descending order
Each time the mid elements has to be computed in order to partition the list in
two sub lists
32. Give the control abstraction for divide and conquer. Dec 2012
divide_and_conquer ( P )
{
if ( small ( P ) ) // P is very small so that a solution is trivial
return solution ( n );
divide the problem P into k instances P1, P2, ..., Pk;
return ( combine ( divide_and_conquer ( P1 ),
divide_and_conquer ( P2 ),
...
divide_and_conquer ( Pk ) ) );
}
The solution to the above problem is described by the recurrence,
assuming size of P denoted by n
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

where f(n) is the time to divide n elements and to combine their solution.
33. What is called substitution method? Jun 2010
A substitution method is one, in which we guess a bound and then use
mathematical induction to prove our guess correct.
It is basically two step process:
Step1: Guess the form of the Solution.
Step2: Prove your guess is correct by using Mathematical Induction.
Example 1.
Solve the following recurrence by using substitution method.

Solution:
Step1: The given recurrence is quite similar with that of MERGESORT, you guess
the solution is

Or

Step2: Now we use mathematical Induction.

Here our guess does not hold for n=1 because

Now for n=2

34. What is called optimal solution? Jun 2010
A feasible solution that maximizes the given objective function is called as
optimal solution.
35. What do you mean by divide and conquer strategy? Jun 2013
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

Refer Part A – Q. No. 11

36. State the principle of substitution method? Jun 2014
Refer Part A – Q. No. 33
37. Define feasible and optimal solution? Jun 2014
Given n inputs form a subset such that it satisfies some given constraints then
such a subset is called feasible solution.
A feasible solution that maximizes the given objective function is called as
optimal solution
38. Trace the operation of binary search algorithm for the input –
15, -6, 0, 7, 9, 23, 54, 82, 101, 112, 125, 131, 142, 151, if you
are searching for the element 9. Dec 2010
Input :

15 -6 0 7 9 23 54 82 101 112 125 131 142 151

0 1 2 3 4 5 6 7 8 9 10 11 12 13

Iteration 0:
Left = 0
Right = 13
Mid = (Left + Right) / 2
= (0 + 13) / 2
Mid = 6
Midelement = 54
Search key = 9
Since 9 < 54, search the element 9 in the left of midelement 54.
Iteration 1:
Left = 0
Right = 5
Mid = (Left + Right) / 2
= (0 + 5) / 2
Mid = 2
Midelement = 0
Search key = 9
Since 9 > 0, search the element 9 in the right of midelement 0.
Iteration 2:
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

Left = 3
Right = 4
Mid = (Left + Right) / 2
= (3 + 4) / 2
Mid = 3
Midelement = 7
Search key = 9
Since 9 > 7, search the element 9 in the right of midelement 7.
Therefore 9 is found in the position 4.
[Link] a brute force algorithm for computing the value of a polynomial
(AU april/may 2015)
Problem: Find the value of polynomial
p(x) = anxn + an-1xn-1 +… + a1x1 + a0 at a point x = x0
Algorithm:
x := x0
p := 0.0
for i := n down to 0 do
power := 1
for j := power * x
p := p + a:= 1 to i do
power [i] * power
return p
Efficiency: Q(n2)
40. Derive complexity of binary search algorithm. (AU april/may 2015)
Worst Case Analysis
The worst case includes all arrays that do not contain a search key.
The recurrence relation for
Cworst(n) = Cworst (n/2) + 1, for n > 1 ----- (1)

Time required to one comparison

compare left sublist made with middle element
or right sub list
Cworst(1) = 1 -------- ( 2 )
The above recurrence relation can be solved further .
assume n=2k the equation ( 1 ) becomes
Cworst(2k) = Cworst(2 k /2)+ 1
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

Cworst(2k) = Cworst(2 k-1

)+ 1 ------ ( 3 )
Using backward substation method , we can substitute
Cworst(2k-1) = Cworst(2k-2)+ 1
Then equation (3) becomes
Cworst(2k) = [Cworst( 2 k-2
)+ 1] + 1
Cworst(2k) = Cworst( 2 k-2
)+ 2
Then
Cworst(2k) = [Cworst( 2 k-3
)+1]+ 2
k k-3
Cworst(2 ) =Cworst( 2 )+3
---
---
Cworst(2k) =Cworst( 2 k-k
)+k
Cworst(2k) =Cworst( 2 0)+k
Cworst(2k) =Cworst( 1 )+k ----- (4)
But as per equation (2 )
as we have assumed n = 2k taking logarithm (base 2 )on both sides
log 2 n = log 2 2k
log 2 n = k. log 2 2
log 2 n = k(1) therefore log 2 2 =1
therefore k = log 2 n
Cworst(1) = 1 the we get equation ( 4 )
Cworst(2k) = 1 + k
Cworst(n) = 1 + log2n ----- (2)
Cworst(n) = log2n for n>1
The worst case time complexity of binary search is Θ(log2n)
As Cworst(n) = log2n + 1
we can verify equation ( 1) with this value.
Cworst(n) = Cworst[(n/2)] + 1
In equation (1) put n = 2i
L.H.S
Cworst(n) = log2n + 1
= log2(2i )+ 1
= log 2 2 + log 2i + 1
= 1+ log 2i + 1
= 2 + log 2i
Cworst(n) =2 + log 2i
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

R.H.S
Cworst(n/2)+1 = log 2(2i/2 )+ 1
= log 2i + 1
= log 2 2i + 1+ 1
= 2 + log 2i
Cworst(n/2) =2 + log 2i
L.H.S = R.H.S
Hence
Cworst(n) = log 2n + 1 and
Cworst(i) = log 2i + 1 are same
Hence
Cworst(n) = Ө(log n )
PART – B
1. Discuss in detail about brute force algorithm.
Brute force
Brute Force is a straightforward approach to solve a problem, which is
directly based on the problem statement and definition of the concepts.
Brute Force strategy is one of the easiest approaches.
For example
Computing an : for a given number a and a non negative integer n , find
the exponentiation as follows
an = a * a* a* ….a* for n times
Computing n! : The n! can be computed as 1 *2 * 3….*n
Performing multiplication of two matrices.
Searching a key value from given list of elements.
Brute Force Algorithm
Two types of Brute force algorithm
1. Consecutive integer checking algorithm for computing
the greatest common divisor of two integer[gcd (m,n)]
2. Definition based algorithm for matrix multiplication.
Advantages of Brute Force Approach
1. It is applicable to a variety of problems.
2. A brute Force algorithm cab be useful for solving small size
instances of a problem.
3. A brute Force algorithm cab be serve an important
theoretical or educational purpose.
4. The brute force approach provides reasonable algorithms of
atleast some practical value with no limitation on instance
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

size for sorting, searching, matrix multiplication and string

matching problem.

2. Explain the Closest-pair and convex-Hull problems by brute

force in detail.
Closest-Pair Problem
The closest pair problem is – finding the two closest points from the set of n
points.
For simplicity the closet pair problem can be considered to be in two dimensional
case.
The point is specified by a pair (x,y).hence .hence P=(x,y) is a point on a two
dimensional plan.
The distance between two points is denoted by Euclidean distance.
It is denoted as

where pi and pj are two points for which i<j

The basic operation in above algorithm is computing Euclidian distance between

two points.
Then the basic operation of the algorithm will be squaring a number.
The number of times it will be executed can be computed as follows:
C(n) =

=2

= (n − 1)n ∈ θ(n2).
= 2[(n − 1) + (n − 2) + . . . + 1]

Of course, speeding up the innermost loop of the algorithm could only decrease
the algorithm’s running time by a constant factor, but it cannot improve its
asymptotic efficiency class.
Convex-Hull Problem
Definition:
Given a set S { p1, p2 ,p3, …pn} of points in the plan , the convex hull H(S) is the
smallest convex polygon in the plane that contains all of the points of S. the set S is
called as coves set .
A polygon is convex if and only if any two points from the set forming a line segment
with end points entirely within the polygon
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

For example

(a) Convex sets. (b) Sets that are not convex.

Definition of Convex Hull:
The convex hull of a set S of points is the smallest convex set containing S.
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 then its convex hull is the triangle
Convex hull problem is the problem of constructing the convex hull for a given set S of
n points
Example 1
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

The points { 1, 2, 3, 4 , 5, 6 } are called extreme points

P6
P1 1
Example 2: 1

P2
P8 1
1

P5
1
P3 P4
1 1

The convex hull for this set of eight points

P1 is the convex polygon with vertices at {p1,
1
p5, p6, p7, and p3.}

Definition of extreme points

An extreme point of a convex set is a point which is not a middle point of any
line segment with end points in the set
Extreme points have several special properties other points of a convex set do
not have. One of them is exploited by the simplex method.
This algorithm solves linear programming problems, which are problems of
finding a minimum or a maximum of a linear function of n variables subject to
linear constraints.
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 sets 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 counter clockwise order.
A few elementary facts from analytical geometry are needed to implement this
algorithm.
1. 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.
2. Such a line divides the plane into two half-planes:
for all the points in one of them, ax + by > c,
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

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 for each of these points.
Time efficiency of this algorithm is in O(n3): 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
3. Explain the concept of Exhaustive search with the help of an example.
Exhaustive search is simply a brute-force approach to combinatorial problems.
It suggests generating each and every element of the problem domain, selecting those
of them that satisfy all the constraints, and then finding a desired element.
Three exhaustive search problems:
 The travelling salesman problem,
 The knapsack problem, and
 The assignment problem.
1. Travelling Salesman Problem
The Travelling 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.
The travelling salesman problem (TSP) is a famous problem in the graph theory.
It can be stated as follows - consider that there are n cities and travelling salesman
has to visit each city exactly once and has to return to the city from where he has
started.
To model this problem weighted graph can be used. The vertices of such graph
represent cities and the edge weight specifies the distances between the cities
This problem can also be started as finding shortest Hamiltonian circuit of the
graph. The shortest Hamiltonian circuit is a cycle in the given graph such that all the
vertices of the graph can be visited only [Link] the tour obtained in such a way has
shortest distance.
Example
Consider the graph as given [Link] is a weighted graph in which weight along the
edges represent the distances among the cities.
We have to find shortest Hamiltonian circuit i.e. the path in which each city is visited
once and returning to the city from which it has started initially.

2
a b

5 8 7 3

c d
1
Tour Length
a -> b -> c -> d -> a I = 2+8+1+7 = 18
a -> b -> d -> c-> a I = 2+3+1+5 = 11
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

optimal
a-> c -> b -> d -> a I = 5+8+3+7 = 23
a-> c -> d -> b -> a I = 5+1+3+2 = 11
optimal
a-> d ->b -> c -> a I = 7+3+8+5 = 23
a-> d -> c -> b -> a I = 7+1+8+2 = 18

Fig: Solution to a small instance of the travelling salesman

problem by exhaustive search
Thus we have to try each possible path and find the shortest distance which
gives optimal tour.
It is easy to see that a Hamiltonian circuit can also be defined as a sequence of n
+ 1 adjacent vertices vi0, vi1, . . . , vin−1, vi0, where the first vertex of the sequence is the
same as the last one and all the other n − 1 vertices are distinct
2. Knapsack Problem
This is another popular problem which can be solved using exhaustive search.
It can be stated as follow : suppose that there are n objects from I = 1,2 , 3, …n.
each object I has some weight wi and values associated with each object is v i .
And capacity of knapsack is W. a person has to pickup the most valuable objects
to fill the knapsack to its capacity.
Example:Consider a knapsack instance as follows
The Knapsack capacity W=8

I Wi Vi
1 7 $42
2 3 $12
3 4 $40
4 5 $25
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

Subset Total Weight Total Value

Nil 0 $0
{1} 7 $42
{2} 3 $12
{3} 4 $40
{4} 5 $25
{1,2} 7+3=10 $42+$12=$54
7+4=11
{1,3} Not feasible
(11>10)
7+5=12
{1,4} Not feasible
(12>10)
{2,3} 3+4=7 $12+$40=$52
{2,4} 3+5=8 $12+$25=$37
Since the
$40+$25=$65
{3,4} 4+5=9 subset
(Feasible)
{3, 4} gives
7+3+4=14
the {1,2,3} Not feasible
(14>10)`
7+3+5=15
{1,2,4} Not feasible
(15>10)
7+4+5=16
{1,3,4} Not feasible
(16>10)
3+4+5=12
{2,3,4} Not feasible
(12>10)
7+3+4+5=19
{1,2,3,4} Not feasible
(19>10)
maximum value $65, it is the feasible solution, so item 3 and item 4 can be put in the
Knapsack bag.
Because in this method, each element of the problem’s domain has to be
searched for obtaining solution. Hence these problems are also called as NP-hard
problems
3. Assignment Problem
Consider that there are n people who need to be assigned to execute n jobs i.e
only one person is assigned to execute one job at a time.
Then problem is to find such assignment that gives smallest total cost.
The cost can be computed as cost C[i, j, k, l]
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

C[i, j, k, l] = Job i is assigned to Person 1, Job j is assigned to Person 2, Job k is

assigned to Person 3, Job 4 is assigned to Person 4.
Example 1
Person Job 1 Job 2 Job 3 Job 4
Person 1 9 2 7 8

Person 2 6 4 3 7

Person 3 5 8 1 8

Person 4 7 6 9 4
<1, 2, 3, 4> Cost = 9 + 4 + 1 + 4 = 18
<1, 2, 4, 3> Cost = 9 + 4 + 8 + 9 = 30
<1, 3, 2, 4> Cost = 9 + 3 + 8 + 4 = 24
<1, 3, 4, 2> Cost = 9 + 3 + 8 + 6 = 26
<1, 4, 2, 3> Cost = 9 + 7 + 8 + 9 = 33
<1, 4, 3, 2> Cost = 9 + 7 + 1 + 6 = 23
... ... etc
The no. of permutation for assignment problem is n!.
Example 2

Person Job 1 Job 2 Job 3 Job 4

Person 1 10 3 8 9

Person 2 7 5 4 8

Person 3 6 9 2 9

Person 4 8 7 10 5

The cost can be obtained by assigning the jobs in various combinations as

< 1, 2, 3, 4> Cost = 10 + 5 + 2 + 5 = 22
< 1, 2, 4, 3> Cost = 10 + 5 + 9 + 10 = 34
< 1, 3, 4, 2> Cost = 10 + 4 + 9 + 7 = 30
< 1, 3, 2, 4> Cost = 10 + 4 + 9 + 5 = 28
< 1, 2, 4, 3> Cost = 10 + 5 + 9 + 10 = 34
< 1, 4, 2, 3> Cost = 10 + 8 + 9 + 10 = 37
< 1, 4, 3, 2> Cost = 10 + 8 + 2 + 7 = 27
.... etc.
Thus by trying 24 permutations (n! = 4! = 24), we can obtain feasible solution.
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

The feasible solution < 2, 1, 3, 4 > i.e . Cost = 3 + 7 + 2 + 5 = 17

Thus we have to generate n! instances to find solution using exhaustive search
method is for solving such problems.
For solving these type of problems , many efficient algorithms are available .
4. Explain Divide and Conquer technique. Dec 2009
Divide & conquer technique is a top-down approach to solve a problem.
The algorithm which follows divide and conquer technique involves 3 steps:
Divide the original problem into a set of sub problems.
Conquer (or Solve) every sub-problem individually, recursive.
Combine the solutions of these sub problems to get the solution of original
problem.
Divide and Conquer is one of the best algorithm design technique
Algorithm DC(p)
{
If P is too small then
Return solution of P.
Else
{
Divide (p) and obtain p1, p2, …..pn where n ≥ 1
Apply DC to each sub problem
Return combine (DC(p 1),
DC( p2)….Dc(pn));
}
}
The diagrammatic representation of the divide and conquer technique is shown
in figure which divides the problem into two smaller sub problems.

Example:To compute sum of n numbers then by divide and conquer

we can solve the problem as
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

(a0 + ….an-1)

(a0 + ….a[n/2]-1) (a[n/2] + ….an-1)

Solution 1 Solution 2

(a0 + ….an-1)

If we want to divide a problem of size n in to a size of n /b taking f(n) time to divide

and combine , then we can set up recurrence relation for obtaining time for size n is
T (n) = a T (n/b) + f (n),
T(n/b) = Time for size n/b time required for dividing the
problem in to sub problem.
T(n) = Time for size n
n = number of sub instances
The above equation is called general divide and conquer recurrence. The order
of growth of T(n) depends upon the constants a, b and order of growth function
f(n).
Divide and Conquer technique
Examples for divide and conquer method are,
 Binary search
 Quick sort
 Merge sort
Example 1 :
Consider the problem of computing the sum of number a 0 …… [Link] n > 1, the
problem is divided into two instances of the same problem.
They are
To compute the sum of the first [n/2] numbers.
To compute the sum of the remaining [n/2] numbers.
Once the two instances are computed, add their values to get the sum of original
problem.
a0 + a1 +……+ an-1 = (a0 + a1 +……+ a[n/2]-1) + (a[n/2] +……+ an-1)
An instance of size n can be divided into several instances of size
n/b, Where
a and b are constants
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

a ≥ 1 and b > 1
The recurrence for the running time T(n) is
T(n) = aT(n/b) + f(n) ,
which is called as general divide and conquer recurrence where,
f(n) is a function that accounts for the time spent on dividing the problem into
smaller ones and on combining their solutions.
The order of growth of T(n) depends on the values of the constants ‘a’ and ‘b’
and the order of growth of the function f(n).
For example, the recurrence equation for the number of additions is
a(n) = 2a(n/2) + 1
Advantages of divide and conquer
The time spent on executing the problem using divide and conquer is smaller
than other methods.
The divide and conquer approach provides an efficient algorithm in computer
science.
The divide and conquer technique is ideally suited for parallel computation in
which each sum problem can be solved simultaneously by its own processor.
5. Explain the Merge Sort algorithm with the help of illustrative
Example. Dec 2011/12/13 & May 2008/14
The merge sort is a sorting algorithm that uses the divide and conquer strategy.
Division is dynamically carried out.
Merging is the process of combining two or more files into a new sorted file.
Merge sort on an input array with n elements consists of three steps:
Divide: partition array into two sub lists s1 and s2 with n/2 elements each
Conquer: then sort sub list s1 and sub list s2.
Combine: merge s1 and s2 into a unique sorted group.
Merge sort is a perfect example of a successful application of the divide and
conquer technique.
It sorts a given array A[0…..n − 1] by dividing it into two halves A[0…..[n/2]−1]
and A[[n/2]…..n − 1].
It sorts each half separately by using recursive procedure, and
Then, merging the two smaller sorted arrays into a single sorted one.
Steps to be followed
The first step of the merge sort is to chop the list into two.
If the list has even length, split the list into two equal sub lists.
If the list has odd length, divide the list in two by making the first sub list one
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

entry greater than the second sub list.

Then split both the sub lists into two and go on until each of the sub lists are of
size one.
 Finally, start merging the individual sub lists to obtain a sorted list.
Example:
The operation of the algorithm for the array of element (8,3,2,9,7,1,5,4) is explained in
the figure given below 8 3 2 9 7 1 5
4

8 3 2 7 1 5
9 4

8 2 9 7 1 5 4
3
8 3 2 9 7 1 5 4

3 8 2 9 1 7 4 5

2 3 8 1 4 5
9 7

1 2 3 4 5 7 8
9
An example of Merge Sort operation
ALGORITHM
Algorithm Mergesort(A[0..n − 1])
//Sorts array A[0..n − 1] by recursive mergesort
//Input: An array A[0..n − 1] of orderable elements
//Output: Array A[0..n − 1] sorted in nondecreasing order
If n > 1
copy A[0..n/2] − 1] to B[0..n/2] − 1]
copy A[[n/2]..n − 1] to C[0..[n/2]] − 1]
Merge sort(B[0..[n/2] − 1])
Mergesort(C[0..[n/2] − 1])
Merge (B, C, A) //see below

The merging of two sorted arrays can be performed as follows.

Two pointers are initialized to point to the first elements of the arrays being
merged.
Then the elements are compared and the smaller of both is added to a new
array or list being constructed.
Then the index of that smaller element is incremented to point to its immediate
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

successor in the array.

The above steps are continued until one of the two given array is exhausted.
Then the remaining elements of the other array are copied to the end of the next
array.
Algorithm Descriptive and Implementation
ALGORITHM Merge(B[0..p − 1], C[0..q − 1], A[0..p + q − 1])
//Merges two sorted arrays into one sorted array
//Input: Arrays B[0..p − 1] and C[0..q − 1] both sorted
//Output: Sorted array A[0..p + q − 1] of the elements of B //and C
i ← 0; j ← 0; k ← 0
while i<p and j<q do
if B[i] ≤ C[j ]
A[k]← B[i];
i←i+1
else
A[k]← C[j ];
j←j+1
k←k+1
if i = p
copy C[j..q − 1] to A[k..p + q − 1]
else
copy B[i..p − 1] to A[k..p + q − 1]

Efficiency of Merge Sort

In merge sort algorithm the two recursive calls are made. Each recursive call
focuses on n/2 elements of the list .
After two recursive calls one call is made to combine two sublist i.e to merge all
n elements.
Hence we can write recurrence relation as
T(n) = T(n/2) + T(n/2) + cn
T(n/2) = Time taken by left sublist
T(n/2) = time taken by right sublist
T(n) = time taken for combining two sublists
where n> 1 T (1) = 0
The time complexity of merge sort can be calculated using two methods
Master theorem
Substitution method
Master theorem
Let , the recurrence relation for merge sort is
T(n) = T(n/2) + T(n/2) + cn
let
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

T(n) = aT(n/b) + f(n) be a recurrence relation

i.e. T(n) = 2T(n/2) + cn ------- ( 1 )

T(1) = 0 ----------- (2 )

As per master theorem

d
T(n) = Θ (n long n ) if a = b
As equation ( 1),
a =2 , b = 2 and f(n) = cn and a = b d
i.e 2 = 2`
This case gives us ,
T (n) =Θ (n log2 n)
Hence the average and worst case time complexity of merge sort is
C worst (n) = (n log2 n)
Substitution method
Let, the recurrence relation for merge sort be
T(n) = T(n/2) + T(n/2) + cn for n>1
i.e. T(n) = 2T(n/2) + cn for n>1 ------- (3)
T(1) = 0 -------(4)
Let us apply substitution on equation ( 3) .
Assume n=2k
T(n) = 2T(n/2) + cn
T(n) = 2T(2k/2 ) + c.2k
T(2k) = 2T(2k-1) + c.2k
If k = k-1 then,
T(2k) = 2T(2k-1) + c.2k
T(2k) = 2[2T(2k-2) + c.2k -1] + c.2k
T(2k) = 22 T(2k-2) + 2.c.2k -1 + c .2k
T(2k) = 22 T(2k-2) + 2.c.2k /2 + c.2k
T(2k) = 22 T(2k-2) + c.2k + c.2k
T(2k) = 22 T(2k-2) + 2c .2k
Similarly we can write,
T(2k) = 23 T(2k-3) + 3c .2k
T(2k) = 24 T(2k-4) + 4c .2k
…..….
T(2k) = 2k T(2k-k) + k.c.2k
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

T(2k) = 2k T(20) + k.c.2k

T(2k) = 2k T(1) + k.c.2k -------- (5)
But as per equation (4), T(1) =0
There equation (5) becomes ,
T(2k) = 2k .0 +. k. c . 2k
T(2k) = k. c . 2k
But we assumed n=2k , taking logarithm on both sides.
i.e. log 2 n = k
Therefore T(n) = log 2 n. cn
Therefore T (n) =Θ (n log2 n)
Hence the average and worst case time complexity of merge sort is
C worst (n) = (n log2 n)
Time complexity of merge sort
Best case Average case Worst case
Θ (n log2 n) Θ (n log2 n) Θ (n log2 n)
Application of Merge Sort
 Sorting
 Tape Sorting
 Data Processing
Demerit
The algorithm requires linear amount of extra storage.
6. Explain the Quick Sort algorithm with the help of illustrative example
Or
Explain the time complexity of quick sort method in detail
Quick sort is a sorting algorithm that uses the divide and conquers strategy.
The three steps of quick sort are as follows:
Divide:
Split the array into two sub arrays that each element in the left sub array is less
than or equal the middle element and each element in the right sub array is
greater than the middle element .
The splitting of the array into two sub array is based on pivot element.
All the elements that are less than pivot should be in left sub array and all the
elements that are more than pivot should be in right sub array
Conquer: Recursively sort the two sub arrays.
Combine: Combine all the sorted elements in a group to form a list of sorted
elements
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

Quick sort is also referred as Partition Exchange sort.

The problem of sorting a set is reduced to the problem of sorting two smaller
subsets.
Quick sort divides input elements according to their position in the array.
It also divides the input elements according to the value of element.
To achieve the partition, quick sort rearrange the given array element a[0,..n-1]
It is a situation where all the elements before the position ‘S’ are smaller than or
equal to a[s] and all the elements after position ‘s’ are greater than or equal to
a[s].
The partition is shown as
a[0]….a[s-1] a[s] a[s+1]……a[n-1]

all are ≤a[s] all are ≥a[s]

These elements are mid These elements are
Less than A[m] Greater than A[m]
After partitioning, a[s] will be in its final position in the sorted array.
Then sorting of element of two sum arrays preceding and following a[s] can be
done independently.
After both scans stop, three situations may arise, depending on whether or not
the scanning indices have crossed.
1. If scanning indices i and j have not crossed, i.e., i < j, we simply
exchange A[i] and A[j ] and resume the scans by incrementing i
and decrementing j, respectively:
i j
P All elements ≤P ≥P ……. ≤P All elements ≥P
P- pivot element
2. If the scanning indices have crossed over, i.e., i > j, we will have
partitioned the Sub array after exchanging the pivot with A[j].
j i
P All elements ≤P ≥P ≤ P All elements ≥P
3. Finally, if the scanning indices stop while pointing to the same element, i.e.,
i = j, the value they are pointing to must be equal to p.
Thus, we have the sub array partitioned, with the split position s= i=j:
i=j
P All elements ≤P =P All elements ≥P
Combine the last case with the case of crossed-over indices (i > j ) by exchanging the
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

pivot with A[j] whenever i ≥ j .

Example
The array elements are
5 3 1 9 8 2 4 7
The first element of array is chosen as pivot element.
Two indices i and j are used for scanning.
P i j
5 3 1 9 8 2 4 7
P i j
5 3 1 9 8 2 4 7
P i j
5 3 1 9 8 2 4 7
Now exchange the elements 9 and 4 now array becomes,
P i j
5 3 1 4 8 2 9 7
Now also exchange a[i] and a[j], the resultant array becomes,
P i j
5 3 1 4 2 8 9 7
Now the scanning indices i and j have not crossed (ie) i < j, simply exchange i and j.
The array becomes
P j i
5 3 1 4 2 8 9 7
Since a[j] < pivot, (2<5) exchange them.
The result is
P
2 3 1 4 5 8 9 7
Now, the array has been sub divided into sub array with pivot element as middle.
Sub array 1
2 3 1 4
P i j
2 3 1 4
P i j
2 3 1 4
Exchange a[i] and [j]
P i j
2 1 3 4
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

Since i < j, exchange a and j

P j i
2 1 3 4
Since a[j] < pivot, (1 < 2) exchange i and j
P i j
1 2 3 4
Sub array 3
3 4
P ij
3 4
Here i=j, ie both points to the same element.
j j
3 4
Sub array 2
8 9 7
P i j
8 9 7
Exchange a[i] and a[j]
The sub array 2 becomes
P i j
8 7 9
Here i < j simply exchange i and j
It becomes
P j i
8 7 9
Since a[j] < pivot, exchange them
7 8 9
Hence, the array elements are sorted. The sorted array is
1 2 3 4 5 7 8 9
Recursive Calls Tree
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

Tree of recursive calls to Quicksort with input values l and r of subarray bounds and
split position s of a partition obtained.
ALGORITHM FOR QUICK SORT
ALGORITHM Quicksort(A[l..r])
//Sorts a subarray by quicksort
//Input: Subarray of array A[0..n − 1], defined by its left and
//right indices l and r
//Output: Subarray A[l..r] sorted in nondecreasing order
if l<r
s ←Partition(A[l..r]) //s is a split position
Quicksort(A[l..s − 1])
Quicksort(A[s + 1..r])

ALGORITHM Hoare Partition(A[l..r])

//Partitions a subarray by Hoare’s algorithm, using the first //element as a pivot
//Input: Subarray of array A[0..n − 1], defined by its left and //right indices l and r (l <
r)
//Output: Partition of A[l..r], with the split position returned //as this function’s value
p ← A[l]
i ← l; j ← r + 1
repeat
repeat i ← i + 1 until A[i] ≥ p
repeat j ← j − 1 until A[j ] ≤ p
swap(A[i], A[j ])
until i ≥ j
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

swap(A[i], A[j ]) //undo last swap when i ≥ j

swap(A[l], A[j ])
return j
Efficiency of Quick Sort
The number of key comparisons made before a partition is achieved is n + 1 if
the scanning indices i and j cross over.
The number of key comparisons is n, if the scanning indices i and j coincides.
Best Case Analysis( split in the middle)
If the array is always partitioned at the mid , then it brings the best case
efficiency of an algorithm
The number of key comparisons in the best case satisfies the recurrence
Cbest(n) = 2 Cbest(n/2) + n for n > 1,
Or
C(n) = C (n/2) + C (n/2) + n ----------( 1 )

Time required to Time required to Time required for

sort left sub array sort right sub array partitioning the sub array
and Cbest(1) = 0.
Using Master Theorem
Solve equation (1) using Master Theorem
If f(n) ∈ Θ (n d ) then
T(n) = Θ (n d) if a < bd
T(n) = Θ (n d log n ) if a = bd
T(n) = Θ (n log b a ) if a> b bd

C(n) = 2 C(n/2) +n
Here f(n) ∈ n1 therefore d = 1
Now , a = 2 and b = 2
As from case 2 we get a = bd i.e. 2 = 21
We get ,
T(n) i.e C(n) = Θ (nd log n )
Cbest(n) = Θ (n log n)
Best case time complexity of quick sort is Θ (n log n)
Using substitution method
C(n) = C (n/2) + C (n/2) + n ----------( 1 )
C(n) = 2C (n/2) +n
Assume n = 2K since each time the list is divide into two equal halves . then equation
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

becomes,
C(2K) = 2C(2k /2) + 2k
C(2K) = 2C(2k -1) + 2k
Now substitute C(2k -1
) = 2C(2k-2) + 2k-1
C(2K) = 2[2C(2k-2) + 2k-1] + 2k
C(2K) = 22C(2k-2) + 2.2k-1 + 2k
C(2K) = 22C( 2k-2) + 2k + 2k
C(2K) = 22C( 2k-2) +2.2k
If we substitute C(2k -2) then ,
C(2K) = 22C( 2k -2) +2. 2k
C(2K) = 22[2 C(2k -3) + 2k –2
] + 2.2k
C(2K) = 23C(2k -3) +22. 2k –2
+ 2.2k
C(2K) = 23C(2k -3) + 2k + 2.2k
C(2K) = 23C(2k -3) + 3.2k
Similarly we can write
C(2K) = 24C(2k -4) + 4.2 k
----
C(2K) = 2kC(2k-k) + k.2 k

C(2K) = 2kC( 20) + k.2 k

C(2K) = 2kC( 1) + k.2 k

C(1) = 0
hence the above equation becomes
C (2K) = 2k.0 + k.2 k

now as we assumed n = 2k we can also say

n = log 2 n [by taking logarithm on both side]
C( n) = n.0 + log 2 n.n
Thus it is proved that best case time complexity of quick sort
is Θ (n log n)
Worst Case Analysis (sorted array)
The worst case for quick sort occurs when the pivot is a minimum or maximum
of all the elements in the list .
For example,
if A[0..n − 1] is a strictly increasing array and we use A[0] as the pivot,
The left-to-right scan will stop on A[1]
The right-to-left scan continues upto A[0]
The total number of key comparisons made will be equal to
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

Cworst(n) = (n -1) + n
Cworst(n) = (n - 1) +( n-2) + ... + 2 + 1
But as we know
1 + 2+ 3 +---- + n = n (n + 1)/2 = ½ n 2
Cworst(n) ∈ θ(n2)
The time complexity of worst case of quick sort is θ (n2)
Average Case Analysis (random array)
Let Cavg(n) be the average number of key comparison made by Quick Sort.
The partition split can be happen in each position S (0≤S≤n-1) with the
probability 1/n.
The recurrence relation is

Cavg (n) ≈ 2n ln n ≈ 1.39 n log2 n.

Thus, on the average case, Quick Sort makes 38% more comparison the best
case.
Hence average case time complexity of quick sort is Θ ( n log n)
Time complexity of quick sort
Best case Average case Worst case
Θ(n log n) Θ(n log n) θ (n2)

Application
Internal sorting of large data sets.
To improve the efficiency of the Quick sort various methods are used to choose
the pivot element.
One such method is called, median of three partitioning that uses the pivot
element as the median of left most, right most and the middle element of the
array.
7. Write an algorithm to perform binary search on a sorted list of elements.
Analyse the algorithm for the best case , worst case and average case.
May 2011 / Dec 2008
Or
What is divide and conquer strategy and explain the binary
search with suitable example problem. Dec 2011
Or
Differentiate sequential search from binary search [Link] 2009
The binary search algorithm is one of the most efficient searching techniques which
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

require the list to be sorted in ascending order.

To search for an element in the list, the binary search algorithms split the list and
locate the middle element of the list.
The middle of the list is calculated as middle := (l + r) div n-numberof element in list
The algorithm works by comparing a search key element ‘k’ with the array
middle element a[m] After comparison, any one of the following three conditions
occurs.
If the search key element ‘k’ is greater than a[m], then the search element is
only in the upper or second half and eliminate the element present in the lower half.
Now the value of l is middle m+1.
If the search key element ‘k’ is less than a[m], then the search element is only in
the lower or first half. No need to check in the upper half. Now the value of r is middle
m-1.
If the search key element ‘k’ is equal to a[m] , then the search key element k is
found in the position m, Hence search operation is complete.
The above steps are repeated until the search element is found, which is equal
to the middle element or the list consists of only one element that is not equal to the
search key element.
a[0]….a[m-1] a[m] a[m+1]……a[n-1]

search have if k<a[m] k search have if k>a[m]

Example:
The list of element are 3,14,27,31,39,42,55,70,81,85,93,98 and searching for k=70 in
the list.
0 1 2 3 4 5 6 7 8 9 10 11 12
3 14 27 31 39 42 55 70 74 81 85 93 98
m- middle element
m = n div 2
= 13 div 2
m=6
0 1 2 3 4 5 6 7 8 9 10 11 12
3 14 27 31 39 42 55 70 74 81 85 93 98
m
0 1 2 3 4 5 6 7 8 9 10 11 12
3 14 27 31 39 42 55 70 74 81 85 93 98
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

l m
Since k> a[m] , then , l=7.
So, the search element is present in second half.
Now the array becomes
7 8 9 10 11 12
70 74 81 85 93 98
l r
m = (l + r) div 2
= 19 div 2
m=9
7 8 9 10 11 12
70 74 81 85 93 98
l m r
Since k< a[m] and 70 < 81
So, the element is present in the first half
Now, the array becomes
7 8
70 74
l r
m = (l + r) div 2
= (7+8) div 2
m=7
7 8
70 74
l, m r
Now k = a[m] and 70 =70
Hence, the search key element 70 is found in the position 7 and the search operation is
completed.
Algorithm Description and Implementation
Establish the array a[0….n-1] and the value to be found k.
Assign the l and r variables to the array limits.
While l<r do
Compute the middle position of the remaining array segment to be searched.
If the value found is greater than current middle then
Adjust l value according
else
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

Adjust r value according

If the array element at ‘l’ position is equal to the value to be found then
Return found and position
else
Return not found and -1.
Algorithm
// Non recursive binary search
Algorithm BinSearch (var a, n elements, n, x: integer)
Var l,r,m:integer;
//Input: Given an array a[0….n-1] sorted in ascending order //and search key k.
//Output: An index of the array’s element that is equal to k or //-1 if there is no such
element.
begin
l:=0; r := n-1;
while (l≤ r) do
begin
mid := [(l + r) div 2];
if k = a[mid] then
return m;
else if k <a[m] then
r:=m-1;
else
l:=m+1;
end:
return -1
end
Efficiency of Binary Search
The standard way to analyze the efficiency is to count number of times search
key is compared with an element of the array.
Worst Case Analysis
The worst case includes all arrays that do not contain a search key.
The recurrence relation for
Cworst(n) = Cworst (n/2) + 1, for n > 1 ----- (1)

Time required to one comparison

compare left sublist made with middle element
or right sub list
Cworst(1) = 1 -------- ( 2 )
The above recurrence relation can be solved further .
assume n=2k the equation ( 1 ) becomes
Cworst(2k) = Cworst(2 k /2)+ 1
Cworst(2k) = Cworst(2 k-1
)+ 1 ------ ( 3 )
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

Using backward substation method , we can substitute

Cworst(2k-1) = Cworst(2k-2)+ 1
Then equation (3) becomes
Cworst(2k) = [Cworst( 2 k-2
)+ 1] + 1
Cworst(2k) = Cworst( 2 k-2
)+ 2
Then
Cworst(2k) = [Cworst( 2 k-3
)+1]+ 2
Cworst(2k) =Cworst( 2 k-3
)+3
---
---
Cworst(2k) =Cworst( 2 k-k
)+k
Cworst(2k) =Cworst( 2 0)+k
Cworst(2k) =Cworst( 1 )+k ----- (4)
But as per equation (2 )
as we have assumed n = 2k taking logarithm (base 2 )on both sides
log 2 n = log 2 2k
log 2 n = k. log 2 2
log 2 n = k(1) therefore log 2 2 =1
therefore k = log 2 n
Cworst(1) = 1 the we get equation ( 4 )
Cworst(2k) = 1 + k
Cworst(n) = 1 + log2n ----- (2)
Cworst(n) = log2n for n>1
The worst case time complexity of binary search is Θ(log2n)
As Cworst(n) = log2n + 1
we can verify equation ( 1) with this value.
Cworst(n) = Cworst[(n/2)] + 1
In equation (1) put n = 2i
L.H.S
Cworst(n) = log2n + 1
= log2(2i )+ 1
= log 2 2 + log 2i + 1
= 1+ log 2i + 1
= 2 + log 2i
Cworst(n) =2 + log 2i
R.H.S
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

Cworst(n/2)+1 = log 2(2i/2 )+ 1

= log 2i + 1
= log 2 2i + 1+ 1
= 2 + log 2i
Cworst(n/2) =2 + log 2i
L.H.S = R.H.S
Hence
Cworst(n) = log 2n + 1 and
Cworst(i) = log 2i + 1 are same
Hence
Cworst(n) = Ө(log n )
Average Case Analysis
To obtain average case efficiency of binary search we will consider some sample input
n. if n = 1
i.e. only element 11 is there only one search is required to search some KEY.
If n = 2 and search key = 22
11 22
0 1
Two comparisons are made to search 22
Similarly n= 4, 8, 16 and search key = 44, 88
11 22 33 44
0 1 2 3
N Total comparison ( c)
1 1
2 2
4 3
8 4

16 5
. .

Observing the above given table we can write

log2 n + 1 = c
for instance
if n= 2 then
log2 2 = 1
then c= log 2 2 + 1
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

c=1+1
c =2
if n = 8 , then
c = log2 n + 1
= log2 8 + 1
=3+1
C=4
Average number of comparison made by the binary search is slightly smaller than
worst case.

Cavg(n) log2 n
The average number of comparison in the successful search is Θ(log 2n)
Advantages
 In this method elements are eliminated by half each time. So it is very faster
than the sequential search.
 It requires less number of comparisons than sequential search to locate the
search key element.
Disadvantages
 An insertion and deletion of a record requires many records in the existing table
be physically moved in order to maintain the records in sequential order.
 The ratio between insertion/deletion and search time is very high.
Applications of binary search
 The binary search is an efficient searching method and is used to search desired
record from database
 For solving nonlinear equations with one unknown this method is used.
Time complexity of binary search
Best case Average case Worst case
Θ(1) Θ(log2n) Θ(log2n)

Difference between sequential and binary search :

Sequential technique binary search technique

This is the simple technique of searching This is the efficient technique of searching
an element an element

This technique does not require the list to This technique require the list to be
be sorted sorted. Then only this method is applicable
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

The worst case time complexity of this The worst case time complexity of this
technique is O(n) technique is O(log n)

Every element of the list may get Only the mid element of the list is
compared with the key element. compared with key element.

8. Explain the method of multiplication of large numbers with the help of

illustrate example Multiplication of Large Integer
In this method of multiplying two numbers multiplies the multiplicand by each
digit of multiplier and then adds up all the properly shifted results.
This method is also called grade – school multiplication
For example
42
×34
= 168
But this method is not convenient for performing multiplication of large
integers . hence let us discuss an interesting algorithm of multiplying large integer .
For example
To demonstrate the basic idea of the algorithm, let us start with a case of two-
digit integers, say, 23 and 14.
These numbers can be represented as follows:
23 2. 101 + 3 .100 and 14 = 1 . 101 + 4 . 100
24 Now let us multiply both the numbers
23 ∗ 14 = (2 . 101 + 3 . 100) * (1 . 101 + 4 . 100 )
= (2 ∗ 1) 102 + (2 ∗ 4 + 3 ∗ 1) 101 + (3 ∗ 4) 100
=2*100+ (8 +3)10 +(12) 1
=200+110+12
= 322
Let us formulate this method Let
c=a∗b
c = c2102 + c1101 + c0 ------(1)
Where,
c2 = a1 ∗ b1 -->is the product of their first digits,
c0= a0 ∗ b0 -->is the product of their second digits,
c1 = (a1 + a0) ∗ (b1 + b0) − (c2 + c0) --> is the product of the sum of
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

the a’s digits and the sum of the b’s digits minus the sum of c2 and c0
The 2 digit numbers are
a = a1 a0
b = b1 b0
Let perform multiplication operation with the help of formula given in equation (1)
c=a∗b
c= 23 * 14
Where a1 = 2, a0 = 3 , b1 = 1, b0 = 4
Let us obtain c0, c1, c2 values
c2 = a1 ∗ b1
=2*1
c2 = 2
c0= a0 ∗ b0
=3*4
c0 = 12
c1 = (a1 + a0) ∗ (b1 + b0) − (c2 + c0)
= (2 + 3) *( 1 + 4) – (2 +12)
= 5 * 5 – 14
c1 =25-14
c1 = 11
Therefore
a * b = c2 102 + c1 101 + c0
= 2 * 100 +11 * 10 +12
= 200 +110 +12
a * b = 322
We can generalize this formula as
c=a∗b
c = c2102 + c1101 + c0
where , n is total number of digits in the integer
c2 = a1 ∗ b1
c0= a0 ∗ b0
c1 = (a1 + a0) ∗ (b1 + b0) − (c2 + c0)
Analysis
In this method there are 3 multiplication operations 1 digit numbers
i.e c2 = a1 ∗ b1 --> multiplication 1
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

c0 = a0 ∗ b0 --> multiplication 2
c1 = (a1 + a0) ∗ (b1 + b0) − (c2 + c0)->multiplication 3
The multiplication of n digit numbers requires three multiplications of n/2 digit
numbers, the recurrence equation for the number of multiplication M(n) will be,
M(n)=3M(n/2), for n>1
And M(1)=1 where n = 1
k
Now put n=2 Solving it by backward substitutions for
M(2k)=3 M(2k /2)
M(2k)=3 M(2k-1)
=3[3 M(2k-2)]
=32 M(2k-3)
……….
=3k M(2k-k)
=3k M(20) Since 20 = 1
=3k
Using equation (3) , M(n) = 1
Therefore M(2k) = 3k ------ (4)
as n= 2k we get k = log2n ,equation (4)
M(n)= 3 log 2n
=n log 2 3 therefore a log b c = c log2 a
≈ n 1.585
M(n) ≈ n1.585
9. Write an algorithm for performing matrix multiplication using
Strassen’s Matrix Multiplication
The Strassen’s matrix multiplication algorithm finds the product C of two 2 by 2
matrices A and B with just seven multiplication as opposed to eight required by the
brute force algorithm.
It is accomplished by using the following formula.
C=A×B

 The multiplication gives

C00 = a00 ×b00 +a01 ×b10
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

C01 = a00 ×b01 +a01 ×b11

C10 = a10 ×b01 +a11 ×b10
C11 = a10 ×b00 +a01 ×b11
Thus to accomplish 2 ×2 matrix multiplication there are total 8 multiplication
and 4 additions
The divide and conquer approach can be used for implementing Strassen’s
matrix multiplication
Divide: divide matrices into sub – matrices : A0 , A1, A2 etc
Conquer: use a group of matrix multiply equations
Combine: recursively multiply sub – matrices and get the final result of
multiplication after performing required additions or subtractions.

Where
m1 = (a00 + a11) * (b00 + b11)
m2 = (a10 + a11) * b00
m3 = a00 * (b01 - b11)
m4 = a11 * (b10 - b00)
m5 = (a00 + a01) * b11
m6 = (a10 + a00) * (b00 + b01)
m7 = (a01 + a11) * (b10 + b11)
Thus, to multiply two 2 by 2 matrices, strassen’s algorithm makes seven
multiplication and 18 additions/subtractions where as the brute force algorithm
requires eight multiplication and for additions.
These numbers should not lead us to multiplying 2 by 2 matrices by strassen’s
algorithm.
Its importance stems from its asymptotic superiority as matrix order n goes to
[Link] A and B be two n-by-n matrices where n is a power of two.
If n is not a power of two, matrices can be added with rows and column of
[Link] matrix A,B and their product is divided into 4,n/2 by n/2 submatrices each as
follows

The value C00 can be computed as either a00 * b00 or a01 * b10 or as M1 + M4
– M5 + M7 , where M1 , M4 , M5 and M7 are found by strassen’s formula with the
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

numbers replaced by the corresponding submatrices.

The seven products of n/2 and n/2 matrices are computed recursively by the
strassen’s matrix multiplication algorithm.
Efficiency of strassen’s matrix multiplication
If M(n) is the number of multiplication made by strassen’s algorithm in
multiplying two n by n matrices where n is a power of 2, then the recurrence
relation is
M(1) = 1
M(n)=7 M(n/2)
Since n=2k yields
M(2k)=7k M(n/2k)
=7[7 M(2k-2)]
=72 M(2k-2)
=7i M(2k-i)
=7k M(2k-k)
=7k
Since k=log2n
M(n)= 7 log2n
=n log27
≈ n2.807
Which is smaller than n3 required by the brute force algorithm.
Numbers of multiplications are reduced by making extra additions.
To multiply two matrices of order n>1 , the algorithm needs to multiply seven
matrices of order n/2 and make 18 additions of matrices of size n/2.
When n = 1 , no additions are made since two numbers are simply multiplied.
The number of additions A(n) made by the Strassen’s algorithm given by
recurrence
A(n) = 7A(n/2) + 18(n/2) , for n > 1
A(1) = 0
According to the Master Theorem.
A(n) ∈ ϴ( n log2n)
In other words, the number of additions has the same order of growth as the
number of multiplications.
As a result, Strassen’s algorithm in ϴ( n log2n), which is a better efficiency class
than ϴ(n2) or the brute force method.
10. Write an algorithm for performing The Closest-Pair and Convex-Hull
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

Problems by Divide-and-Conquer. Dec 2005/2007/2010/2012/2013

Definition
There exits a set of points on a plane which is said to be convex if for any two
points A and B in the set , the entire line segment with the end points at A and B
belongs to the set
Example

Is a convex hull Is not a convex hull

The convex – hull problem of finding the smallest convex polygon that contains
given n points in a plane can be solved using divide and conquer method.
This version of solving convex hull problem is called quick hull because this method
is based on quick sort technique.
Algorithm
Step 1 : Sort the points ( p1 ,p2 ,p3,…pn) by their x – coordinates
Step 2 : Repeatedly find the convex hull through p1 to p n/2
Step 3 : Repeatedly find the convex hull through p n/2+1 to p n
Step 4 : Merge the two convex hulls
The Closest-Pair Problem
Let P be a set of n > 1 points in the Cartesian plane.
For the sake of simplicity, we assume that the points are distinct.
If 2 ≤ n ≤ 3, the problem can be solved by the obvious brute-force algorithm.
If n > 3, we can divide the points into two subsets Pl and Pr of n/2 and n/2 points,
respectively, by drawing a vertical line through the median m of their x coordinates so
that n/2 points lie to the left of or on the line itself, and n/2 points lie to the right of or
on the line.
Then we can solve the closest-pair problem recursively for subsets Pl and Pr .
Let dl and dr be the smallest distances between pairs of points in Pl and Pr,
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

respectively, and let d = min{ dl , dr }.

Note that d is not necessarily the smallest distance between all the point pairs
because points of a closer pair can lie on the opposite sides of the separating line.

 Let S be the list of points inside the strip of width 2d around the separating line,
obtained from Q and hence ordered in non decreasing order of their y coordinate.
 We will scan this list, updating the information about dmin, the minimum
distance seen so far, if we encounter a closer pair of points.
 Initially, dmin = d, and subsequently dmin ≤ d. Let p(x, y) be a point on this list.
 For a point p(x, y) to have a chance to be closer to p than dmin, the point must
follow p on list S and the difference between their y coordinates must be less than
dmin.
ALGORITHM EfficientClosestPair(P, Q)
//Solves the closest-pair problem by divide-and-conquer
//Input: An array P of n ≥ 2 points in the Cartesian plane //sorted in non
decreasing order of their x coordinates and an //array Q of the same points
sorted in non decreasing order of //the y coordinates
//Output: Euclidean distance between the closest pair of //points
if n ≤ 3
return the minimal distance found by the brute-force algorithm
else
copy the first _n/2_ points of P to array Pl
copy the same _n/2_ points from Q to array Ql
copy the remaining _n/2_ points of P to array Pr
copy the same _n/2_ points from Q to array Qr
dl←EfficientClosestPair(Pl, Ql)
dr←EfficientClosestPair(Pr, Qr)
d ←min{dl, dr}
m←P[_n/2_ − 1].x
copy all the points of Q for which |x − m| < d into array S[0..num − 1]
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

dminsq ←d2
for i ←0 to num − 2 do
k←i + 1
while k ≤ num − 1 and (S[k].y − S[i].y)2 < dminsq
dminsq ←min((S[k].x − S[i].x)2+ (S[k].y − S[i].y)2, dminsq)
k←k + 1
return sqrt(dminsq)
The algorithm spends linear time both for dividing the problem into two
problems half the size and combining the obtained solutions. Therefore, assuming as
usual that n is a power of 2, we have the following recurrence for the running time of
the algorithm:T (n) = 2T (n/2) + f (n),where f (n) ∈ Ө(n). Applying the Master
Theorem (with a = 2, b = 2, and d = 1), we get T (n) ∈ Ө(n log n).
The necessity to presort input points does not change the overall efficiency class
if sorting is done by a O(n log n) algorithm such as merge sort.
Convex-Hull Problem
Let S be a set of n>1 points p1(x1, y1), . . . , pn (xn, yn) in the Cartesian plane.
We assume that the points are sorted in non decreasing order of their x
coordinates, with ties resolved by increasing order of the y coordinates of the points
involved.
It is not difficult to prove the geometrically obvious fact that the leftmost point
p1 and the rightmost point pn are two distinct extreme points of the set’s convex hull
(Figure 5.8).
Let p1 pn be the straight line through point’s p1 and pn directed from p1to pn.
This line separates the points of S into two sets:
S1 is the set of points to the left of this line, and S2 is the set of points to the
right of this line. We say that point q3 is to the left of the line q1q2 directed from point
q1 to point q2 if q1 q2 q3 forms a counterclockwise cycle. Later, we cite an analytical
way to check this condition, based on checking the sign of a determinant formed by
the coordinates of the three points.
The points of S on the line p1 pn, other than p1 and pn, cannot be extreme
points of the convex hull and hence are excluded from further consideration.
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

Fig Upper and lower hulls of a set of points

The boundary of the convex hull of S is made up of two polygonal chains: an
“upper” boundary and a “lower” boundary.
The “upper” boundary, called the upper hull, is a sequence of line segments with
vertices at p1, some of the points in S1 (if S1 is not empty) and pn.
The “lower” boundary, called the lower hull, is a sequence of line segments with
vertices at p1, some of the points in S2 (if S2 is not empty) and pn.
The fact that the convex hull of the entire set S is composed of the upper and
lower hulls, which can be constructed independently.
Construction of upper hull:
If S1 is empty, the upper hull is simply the line segment with the endpoints at p1
and pn.
If S1 is not empty, the algorithm identifies point pmax in S1, which is the farthest
from the line p1 pn .

If there is a tie, the point that maximizes the angle pmax p pn can be selected.
(Note that point pmax maximizes the area of the triangle with two vertices at p1and pn
and the third one at some other point of S1.)

Pmax
1

Pn
P1 1
1

Then the algorithm identifies all the points of set S1 that are to the left of the
line p1 pmax; these are the points that will make up the set S1,
The points of S1 to the left of the line pmax pn will make up the set S1
It is not difficult to prove the following:
pmax is a vertex of the upper hull.
The points inside p1 pmax pn cannot be vertices of the upper hull (and hence
can be eliminated from further consideration).
There are no points to the left of both lines p1 pmax and pmax pn.
Therefore, the algorithm can continue constructing the upper hulls of p1 U S1,1
Upmax and pmax U S1,2 U pn recursively and then simply concatenate them to get the
upper hull of the entire set p1 U S1 U pn.
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

If q1(x1, y1), q2(x2, y2), and q3(x3, y3) are three arbitrary points in the
Cartesian plane, then the area of the triangle q1q2q3 is equal to one-half of the
magnitude of the determinant
x1 y1 1
x2 y2 1 = x1 y2 + x3 y1 + x2 y3− x3 y2 − x2 y1− x1 y3
x3 y3 1
while the sign of this expression is positive if and only if the point q3 = (x3, y3)
is to the left of the line q1 q2.
Using this formula, we can check in constant time whether a point lies to the left
of the line determined by two other points as well as find the distance from the point to
the line.
Example 2:
The merge procedure requires finding a bridge between two hulls that are adjacent to
each other . concatenate left part of left hull and right part of right hull
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

Quick hull has the same Ө(n log n) worst-case efficiency as quick sort.
In the average case Ө(n2), however, we should expect a much better
performance.
The average-case efficiency of quick hull turns out to be linear. ‘n’ its computing
time is O(n2).
11. Trace the steps of merge sort algorithm for the elements 122, 25, 70,
175, 89, 90, 95, 102, 123 and also compute its time complexity. Dec 2012
Refer Part B – Q. No. 5
12. Explain the binary search algorithm with an example. And find
the best, average and worst case complexity. Dec 2012
Refer Part B – Q. No. 7
13. Explain merge sort problem using divide and conquer technique. Give an
example. Apr 2010
Refer Part B – Q. No. 5
14. Write a pseudo code using divide and conquer technique for finding the
position of the largest element in the array of N numbers. Jun 2014
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

Refer Part B – Q. No. 4

15. Sort the following set of elements using merge sort : 12, 2, 8,
71, 4, 23, 6, 89, 56 Jun 2014
12 2 8 71 4 23 6 89 56

12 2 8 71 4 23 6 89 56

12 2 8 71 4 23 6 89 56

12 2 8 71 4 23 6 89 56

12 2 8 71 4 23 6 89 56
Swapping
2 12 8 4 71 6 23 56 89

2 12 8 4 71 6 23 56 89

2 8 12 4 71 6 23 56 89

2 4 8 12 71 6 23 56 89

2 4 6 8 12 56 71 89
16. Distinguish between quick sort and merge sort and arrange the
following numbers in increasing order using merge sort (18, 29, 68, 32, 43,
37, 87, 24, 47, 50). Jun 2013
Quicksort
Quicksort is another divide and conquer sorting algorithm, proposed by C. A. R.
Hoare. Here, the workhorse is the partition operation. Given an array of n elements,
partition takes one element (known as the pivot) and places it in the correct position.
That is, the array will not be sorted, but all the elements less than the pivot will
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

be to the left of the pivot, and all the elements greater than the pivot will be to the
right. The partition operation can be performed in linear time.
Quicksort then works as follows. First, it performs the partition operation on the
input array. Assume the pivot is placed in position p.
Now, quicksort sorts the sub-arrays A[0 : p - 1] and A[p + 1 : n - 1], using
quicksort itself. Here again, the base case is an array of size 1.
Various ways of selecting the pivot:
The simplest is to just take the left-most element every time as the pivot. But,
this leads to a fatal weakness.
In this case, if the array is already sorted, the pivot will get placed in the left
most position always, and quicksort will be sorting sub-lists of size 0 and n - 1.
This leads to a time complexity of O(n^2), which is no better than bubble sort.
This can be mitigated by choosing a random element as the pivot, or using the
median of three elements. In this case, the worst case time of O(n^2) is extremely
unlikely.
In the best case, when the pivot is always placed in the middle, the time
complexity will be O(n log n).
Also, if the pivot always gets placed somewhere in the middle 50% (25% - 75%)
part of the array, quick sort will take time proportional to O(n log n), even as in the
best case.
Advantage of quick sort:
Even though the asymptotic complexities are O(n log n), the constant muliplier
(hidden by the Big Oh notation) is much smaller for quicksort, which subsequently is
appreciably faster than mergesort in almost all cases.
Regarding space complexity, the space complexity of quicksort is O(log n),
taking into account the stack space used for recursion.
Mergesort
The real work of mergesort is done by the merge operation. Given two sorted
sub-arrays, together having a total of n elements,the merge operation uses an
auxiliary array of size n to mergethem together into a single sorted array in linear time
i.e. O(n) in Big Oh notation.
Having this merge operation, mergesort works as follows.
Given an array of elements A, it sorts the left and right sub-arrays using
mergesort itself, and then merges them together into one single sorted array.
The base case is a sub-array of size 1, which is implicitly sorted by definition.
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

If we analyze the time complexity of mergesort, it is O(n log n) in all cases. That
is, the time taken to sort n elements grows proportionally to n log n.
Merge sort also needs an extra array of size n for the merge operation. So its
space complexity is O(n).
Also, quicksort cannot be implemented iteratively, unlike mergesort, where an
iterative implementation, sometimes called bottom-up mergesort, is possible.

18 29 68 32 43 37 87 24 47 50

18 29 68 32 43 37 87 24 47 50

18 29 68 32 43 37 87 24 47 50

18 29 68 32 43 37 87 24 47 50

18 29 68 32 43 37 87 24 47 50

18 29 68 32 43 37 87 24 47 50

18 29 68 32 43 37 87 24 47 50

18 29 68 32 43 24 37 87 47 50
24

18 29 32 43 68 24 37 47 50 87

18 24 29 32 37 43 47 50 68 87

17. Briefly explain the procedure for strassen’s matrix multiplication. Mar 14
Refer Part B – Q. No. 9
18. Write a pseudo code for divide & conquer algorithm for merging two
sorted arrays in to a single sorted one. Explain with [Link] Part B – Q. No. 5
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

19. Explain about binary search with example.

Refer Part B – Q. No. 7
20. Explain how analysis of Merge Sort is done with a suitable illustration.
Refer Part B – Q. No. 5
21.A pair contains two numbers and second number is on right side of the
first one in an [Link] difference of a pair is the minus result while
subtracting the second number from the first [Link] a function which
gets the maximal difference of all pairs in array (using divide and conquer
method) (AU april/may 2015)
We divide an array into two sub-arrays with same size.
The maximal difference of all pairs occurs in one of the three following situations:
(1) two numbers of a pair are both in the first sub-array;
(2) two numbers of a pair are both in the second sub-array;
(3) the minuend is in the greatest number in the first sub-array, and the
subtrahend is the least number in the second sub-array.

It is not a difficult to get the maximal number in the first sub-array and the minimal
number in the second sub-array. How about to get the maximal difference of all pairs in
two sub-arrays?
They are actually sub-problems of the original problem, and we can solve them via
recursion. The following are the sample code of this solution:
int MaxDiff_Solution1(int numbers[], unsigned length)
{
if(numbers == NULL || length < 2)
return 0;

int max, min;

return MaxDiffCore(numbers, numbers + length - 1, &max, &min);
}

int MaxDiffCore(int* start, int* end, int* max, int* min)

{
if(end == start)
{
*max = *min = *start;
return 0x80000000;
}

int* middle = start + (end - start) / 2;

int maxLeft, minLeft;

int leftDiff = MaxDiffCore(start, middle, &maxLeft, &minLeft);
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

int maxRight, minRight;

int rightDiff = MaxDiffCore(middle + 1, end, &maxRight, &minRight);

int crossDiff = maxLeft - minRight;

*max = (maxLeft > maxRight) ? maxLeft : maxRight;

*min = (minLeft < minRight) ? minLeft : minRight;

int maxDiff = (leftDiff > rightDiff) ? leftDiff : rightDiff;

maxDiff = (maxDiff > crossDiff) ? maxDiff : crossDiff;
return maxDiff;
}

In the function MaxDiffCore, we get the maximal difference of pairs in the first sub-
array (leftDiff), and then get the maximal difference of pairs in the second sub-array
(rightDiff).
We continue to calculate the difference between the maximum in the first sub-array
and the minimal number in the second sub-array (crossDiff). The greatest value of the
three differences is the maximal difference of the whole array.
We can get the minimal and maximal numbers, as well as their difference in O(1) time,
based on the result of two sub-arrays, so the time complexity of the recursive solution
is T(n)=2(n/2)+O(1). We can demonstrate its time complexity is O(n).

IMPORTANT QUESTIONS
Part A
1. What is the time complexity of Binary search? June 2011 & 12
Part A – Refer Q. No. 13
2. Give the recurrence equation for the worst case behavior of
merge sort? Part A – Refer Q. No. 19 Dec 2010
3. What do you meant by Divide and conquer strategy? May 2013
Part A – Refer Q. No. 22
4. Give the time efficiency and drawback of merge sort algorithm?
Dec 2005
Part A – Refer Q. No. 27
5. What is the difference between quick sort and merge sort? May 2013
Part A – Refer Q. No. 28
6. What is the difference between sequential and binary search
Apr 2013
Part A – Refer Q. No. 29
7. List out two drawbacks of binary search algorithm. Dec 2007
Part A – Refer Q. No. 31
8. Give the control abstraction for divide and conquer. Dec 2012
Part A – Refer Q. No. 32
9. What is called substitution method? Jun 2010
Part A – Refer Q. No. 33
10. What is called optimal solution? Jun 2010
Part A – Refer Q. No. 34
11. What do you mean by divide and conquer strategy? Jun 2013
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

Part A – Refer Q. No. 35

12. State the principle of substitution method? Jun 2014
Part A – Refer Q. No. 36
13. Define feasible and optimal solution? Jun 2014
Part A – Refer Q. No. 37
14. Trace the operation of binary search algorithm for the input –
15, -6, 0, 7, 9, 23, 54, 82, 101, 112, 125, 131, 142, 151, if you
are searching for the element 9. Dec 2010
Part A – Refer Q. No. 38
15. Define Brute Force method
16. State the concept of Closest-Pair and Convex-Hull Problems
17. What is mean by Exhaustive Search and give the types
18. What is Travelling Salesman Problem?
19. What is knapsack?
20. What is assignment problem?
21. Is merge sort stable sorting algorithm?
22. What is the difference between quick sort and merge sort?
23. Define Stassen’s Matrix Multiplication

Part B
1. Write an algorithm for performing The Closest-Pair and
Convex-Hull Problems by Divide-and-Conquer 2005/2007/2010/2012/2013
Refer Part B – Q. No. 10
2. Write an algorithm to perform binary search on a sorted list of
elements. Analyse the algorithm for the best case , worst case
and average case. May 2011 / Dec 2008
Or
What is divide and conquer strategy and explain the binary
search with suitable example problem. Dec 2011
Or
Differentiate sequential search from binary search technique.
May 2009
Refer Part B – Q. No. 7
3. Briefly explain the procedure for strassen’s matrix
multiplication. Mar 2014
Refer Part B – Q. No. 9
4. Trace the steps of merge sort algorithm for the elements 122,
25, 70, 175, 89, 90, 95, 102, 123 and also compute its time
complexity. Dec 2012
Refer Part B – Q. No. 5
5. Explain the binary search algorithm with an example. And find
the best, average and worst case complexity. Dec 2012
Refer Part B – Q. No. 7
6. Explain merge sort problem using divide and conquer
technique. Give an example. Apr 2010
Refer Part B – Q. No. 5
7. Write a pseudo code using divide and conquer technique for
finding the position of the largest element in the array of N
numbers. Jun 2014
Refer Part B – Q. No. 4

8. Sort the following set of elements using merge sort : 12, 2, 8,

71, 4, 23, 6, 89, 56 Jun 2014
 CS 6402 DESIGN AND ANALYSIS OF ALGORITHMS UNIT 2

Refer Part B – Q. No. 15

9. Distinguish between quick sort and merge sort and arrange the
following numbers in increasing order using merge sort (18, 29,
68, 32, 43, 37, 87, 24, 47, 50). Jun 2013
Refer Part B – Q. No. 16
[Link] the method of multiplication of large numbers with the
help of illustrate example
[Link] an algorithm for performing matrix multiplication using
Strassen’s Matrix Multiplication
[Link] an algorithm for performing The Closest-Pair and
Convex-Hull Problems by Divide-and-Conquer. May 2011/2012/2013

ANNA UNIVERSITY APRIL/MAY 2015

[Link]
1. Design a brute force algorithm for computing the value of a polynomial
(AU april/may 2015)
Part A – Refer Q. No. 39
2. Derive complexity of binary search algorithm. (AU april/may 2015)
Part A – Refer Q. No. 40
Part B
1.A pair contains two numbers and second number is on right side of the first
one in an [Link] difference of a pair is the minus result while subtracting
the second number from the first [Link] a function which gets the
maximal difference of all pairs in array (using divide and conquer method)
(AU april/may 2015)
Refer Part B – Q. No. 21
2. Explain convex hull problem and the solution involved behind it. (AU
april/may 2015)
Refer Part B – Q. No. 2