R.

B Institute of management studies

Subject Name: Analysis and Design of Algorithms
Subject Code: 2688603
Unit-2

Divide and Conquer is a fundamental algorithmic paradigm used to

solve problems by breaking them down into smaller subproblems,
solving the subproblems independently, and then combining their
solutions to obtain the final solution. The Divide and Conquer approach
typically involves three steps:

1. Divide: Break the problem into smaller, more manageable

subproblems that are similar in structure to the original problem.
This step involves recursively dividing the problem into smaller
instances until the base case is reached.
2. Conquer: Solve the subproblems recursively. This step involves
independently solving each subproblem using the same
algorithm or approach as the original problem. If the
subproblems are small enough, they can be solved directly
without further subdivision.
3. Combine: Merge the solutions of the subproblems to obtain the
solution to the original problem. This step involves aggregating
or combining the results from the subproblems to derive the
final solution.

Here, we will sort an array using the divide and conquer approach (ie.
merge sort).

Let the given array be:

1. Divide the array into two halves.

ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA

 Divide the array into two halves.

Divide the array into two subparts

Again, divide each subpart recursively into two halves until you get
individual elements.

ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA

Divide the array into smaller subparts

3. Now, combine the individual elements in a sorted manner.

Here, conquer and combine steps go side by side.

Combine the subparts

We are interested in to find maximum subarray sum (contiguous) of

given 1-D array. Array may contain negative and positive numbers
ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA
which makes this a difficult problem. Brute force will take O(N^2) time
while a divide and conquer approach will take O(N log N) time.

If all the array entries were positive, then the maximum-subarray

problem would

present no challenge, since the entire array would give the greatest sum.

• Example : input array = [-3,2,3,4,-4,-1].

• here maximum subarray is [2,3,4]. hence maximum subarray sum is

9.

Two approaches:

• Simple approach is brute-force implementation but it will take O(n^2)

time.

• Divide and conquer algorithm will give maximum subarray in

O(nlogn) time.

• The outer loop will take the starting element, the inner loop finds the
maximum

possible sum with first element picked by outer loop and compares this
maximum

with the overall maximum. Finally return the overall maximum.

• So Basically we are checking all possible subarray for given element

and each time

we compare it with overall maximum.

Divide and Conquer algorithm O(N log N)

1. Divide an array in two halves.

2. Find maximum subarray sum in left half.

3. Find maximum subarray sum in right half.

ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA

4. Find maximum subarray sum which crosses the midpoint.

5. Maximum of step 2,3 and 4 is our answer.

• Divide and Conquer technique suggest that divide the subarray into
two subarrays

of as equal size as possible. for that we find mid point of an array.

• consider subarray A[low,mid] and A[mid+1,high] as shown in figure

1.

• any contigues maximum subarray lie between three following places

:

1. entirely in the leftside subarray (A[low,mid])

2. entirely in the rightside subarray(A[mid+1,high]).

3. crossing the midpoint (A[i,j]).(figure 2)

Applications of Divide and Conquer

The Divide and Conquer paradigm finds applications across various

domains due to its versatility and efficiency in solving complex
problems. Some of the common applications include:

 Sorting Algorithms: Algorithms like Merge Sort and Quick Sort

utilize Divide and Conquer to efficiently sort large datasets by
recursively dividing them into smaller subarrays, sorting the
subarrays, and then merging or combining them.
 Searching Algorithms: Binary Search, a Divide and Conquer
algorithm, efficiently searches sorted arrays by repeatedly
dividing the search space in half until the target element is found
or the search space is exhausted.

ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA

  Matrix Operations: Algorithms for matrix multiplication,
exponentiation, and inversion often use Divide and Conquer to
break down the problem into smaller subproblems, compute
solutions for the subproblems, and combine them to obtain the
final result.
 Optimization Problems: Divide and Conquer is used to solve
optimization problems such as finding the closest pair of points,
computing the convex hull of a set of points, and optimizing
resource allocation in scheduling and routing problems.
 Computational Geometry: Algorithms for geometric problems
like finding intersections, calculating distances, and determining
visibility regions make use of Divide and Conquer to efficiently
decompose the problem space, solve subproblems, and combine
results.
 Numerical Computations: Divide and Conquer algorithms are
employed in numerical methods like the Fast Fourier Transform
(FFT), which decomposes the problem of transforming a
sequence of values into smaller subproblems that can be
efficiently solved.
 Dynamic Programming: Dynamic programming problems
often exhibit overlapping subproblems and optimal substructure,
making them amenable to a Divide and Conquer approach. Many
dynamic programming algorithms utilize Divide and Conquer to
break down the problem into smaller subproblems and combine
their solutions.

Maximum Subarray Problem

You have an array X[] with n elements, write a program to find the
maximum sum of subarray among all possible subarrays.
Two approaches:
• Simple approach is brute-force implementation but it will take O(n^2)
time.

ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA

• Divide and conquer algorithm will give maximum subarray in
O(nlogn) time.
• The outer loop will take the starting element, the inner loop finds the
maximum possible sum with first element picked by outer loop and
compares this maximum with the overall maximum. Finally return the
overall maximum.
• So Basically we are checking all possible subarray for given element
and each time
Divide an array in two halves.
2. Find maximum subarray sum in left half.
3. Find maximum subarray sum in right half.
4. Find maximum subarray sum which crosses the midpoint.
5. Maximum of step 2,3 and 4 is our answer.
• Divide and Conquer technique suggest that divide the subarray into
two subarrays
of as equal size as possible. for that we find mid point of an array.
• consider subarray A[low,mid] and A[mid+1,high] as shown in figure
1.
• any contigues maximum subarray lie between three following places
1. entirely in the leftside subarray (A[low,mid])
2. entirely in the rightside subarray(A[mid+1,high])
crossing the midpoint (A[i,j]).(figure 2)

ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA

find the location of maximum subarray in this three places.
• Divide and Conquer technique will return maximum subarray of the
left and right
subarray.
• But We need maximum subarray of an given array. so we need to
check an
subarray which crosses the midpoint. this subarray contain elements
from both left
and right.
• to find this subarray we could simply start from midpoint then traverse
toward the

ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA

left side of an midpoint till sum is increasing. do the same process on
left side of an
midpoint.(start from mid+1 index) .
• Example : input array {-3,2,5,6,7,1,-3,-2}
• Divide and Conquer technique will return 13 (A[1,3]) for left
subarray. and 8
(A[4,5]) for right subarray.
• if we find subarray (A[1,5]) which cross the midpoint then answer
should be 21.
Input array =[-6,-2,8,3,4,-2].
• here maximum contiguous subarray sum from left-side is 8 .
• maximum contiguous subarray sum from right-side is 7.
Strassen's Algorithm
The traditional matrix multiplication algorithm has a time complexity
of O(n^3) for multiplying two n x n matrices. However, Strassen's
algorithm improves this to O(n^log2(7)), which is approximately
O(n^2.81). The algorithm achieves this improvement by recursively
breaking down the matrix multiplication into smaller subproblems and
combining the results.

Algorithm working As below:

Given two matrices A and B, of size n x n, we divide each matrix into
four equal-sized submatrices, each of size n/2 x n/2.
A = | A11 A12 | B = | B11 B12 |
| A21 A22 | | B21 B22 |

We then define seven intermediate matrices:

P1 = A11 * (B12 - B22)
ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA
P2 = (A11 + A12) * B22

P3 = (A21 + A22) * B11

P4 = A22 * (B21 - B11)

P5 = (A11 + A22) * (B11 + B22)

P6 = (A12 - A22) * (B21 + B22)

P7 = (A11 - A21) * (B11 + B12)

Finally, we combine the results to obtain the four submatrices of the

resulting matrix C of size n x n:
C11 = P5 + P4 - P2 + P6

C12 = P1 + P2

C21 = P3 + P4

C22 = P5 + P1 - P3 - P7

The efficiency of Strassen's algorithm comes from the fact that it

reduces the number of recursive calls, which means fewer
multiplication operations are needed overall. However, due to its higher
constant factors and increased overhead, Strassen's algorithm is
sometimes slower than the naive algorithm for small matrices or
practical implementations. For huge matrices, it can provide a
significant speedup.

begin
If n = threshold then compute
C = a * b is a conventional matrix.
Else
Partition a into four sub matrices a11, a12, a21, a22.
Partition b into four sub matrices b11, b12, b21, b22.

ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA

 Strassen ( n/2, a11 + a22, b11 + b22, d1)
Strassen ( n/2, a21 + a22, b11, d2)
Strassen ( n/2, a11, b12 – b22, d3)
Strassen ( n/2, a22, b21 – b11, d4)
Strassen ( n/2, a11 + a12, b22, d5)
Strassen (n/2, a21 – a11, b11 + b22, d6)
Strassen (n/2, a12 – a22, b21 + b22, d7)
C = d1+d4-d5+d7 d3+d5
d2+d4 d1+d3-d2-d6
end if
return (C)
end
Example: Strassen’s Matrix Multiplication
Let's consider two 2×2 matrices for simplicity:

A = 1 2 B = 5 6

3 4 7 8

Step 1: Compute the 7 Products (Strassen’s Formula)

Define the following intermediate values:

M1=(A11+A22)(B11+B22)=(1+4)(5+8)=5×13=65

M2=(A21+A22)B11=(3+4)×5=7×5=35

M3=A11(B12−B22)=1×(6−8)=1×(−2)=−2

M4=A22(B21−B11)=4×(7−5)=4×2=8

M5=(A11+A12)B22=(1+2)×8=3×8=24
ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA
 M6=(A21−A11)(B11+B12)=(3−1)×(5+6)=2×11=22

M7=(A12−A22)(B21+B22)=(2−4)×(7+8)=(−2)×15=−30

Step 2: Compute the Result Matrix

Using the 7 computed values:

C11=M1+M4−M5+M7=65+8−24−30=19

C12=M3+M5=−2+24=22

C21=M2+M4=35+8=43

C22=M1−M2+M3+M6=65−35−2+22=50

So, the final result is:

C = 19 22

43 50

Substitution Method
We make a guess for the solution and then we use mathematical
induction to prove the guess is correct or incorrect.
Example
onsider the recurrence T(n) = 2T(n/2) + n
We guess the solution as T(n) = O(nLogn). Now we use induction
to prove our guess.

ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA

We need to prove that T(n) <= cnLogn.
We can assume that it is true
for values smaller than n.
T(n) = 2T(n/2) + n
<= 2cn/2Log(n/2) + n
= cnLogn - cnLog2 + n
= cnLogn - cn + n
<= cnLogn
Recursion tree method for Recurrence
A recursion tree is a tree where each node represents the cost of a
certain recursive subproblem. Then you can sum up the numbers in
each node to get the cost of the entire algorithm.
We would usually use a recursion tree to generate possible guesses for
the runtime, and then use the substitution method to prove them.
However, if you are very careful when drawing out a recursion tree and
summing the costs, you can actually use a recursion tree as a direct
proof of a solution to a recurrence.
If we are only using recursion trees to generate guesses and not prove
anything, we can tolerate a certain amount of sloppiness in our analysis.
For example, we can ignore floors and ceilings when solving our
recurrences, as they usually do not affect the final guess.
Steps to Solve Recurrence Relations Using Recursion
Tree Method
Step-01:
Draw a recursion tree based on the given recurrence relation.
Step-02:
Determine-

ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA

• Cost of each level
• Total number of levels in the recursion tree
• Number of nodes in the last level
• Cost of the last level

Step-03:
Add cost of all the levels of the recursion tree and simplify the
expression so
obtained in terms of asymptotic notation.
Following problems clearly illustrates how to apply these steps.

Problem-01:
Solve the following recurrence relation using recursion tree method-
T(n) = 2T(n/2) + n

Solution-
Step-01:
Draw a recursion tree based on the given recurrence relation.
The given recurrence relation shows-
• A problem of size n will get divided into 2 sub-problems of size n/2.
• Then, each sub-problem of size n/2 will get divided into 2 sub-
problems of size
n/4 and so on.
• At the bottom most layer, the size of sub-problems will reduce to 1.

ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA

The given recurrence relation shows-
• The cost of dividing a problem of size n into its 2 sub-problems and
then
combining its solution is n.
• The cost of dividing a problem of size n/2 into its 2 sub-problems and
then
combining its solution is n/2 and so on.
This is illustrated through following recursion tree where each node
represents the
cost of the corresponding sub-problem-

ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA

Step-02:
Determine cost of each level-
• Cost of level-0 = n
• Cost of level-1 = n/2 + n/2 = n
• Cost of level-2 = n/4 + n/4 + n/4 + n/4 = n and so on.

Step-03:
Determine total number of levels in the recursion tree-
• Size of sub-problem at level-0 = n/20
• Size of sub-problem at level-1 = n/21
• Size of sub-problem at level-2 = n/22
Continuing in similar manner, we have-
Size of sub-problem at level-

i = n/2i

ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA

Suppose at level-x (last level), size of sub-problem becomes 1. Then-
n / 2x = 1
2x = n
Taking log on both sides, we get-
xlog2 = logn
x = log2n
∴ Total number of levels in the recursion tree = log2n + 1

Step-04:
Determine number of nodes in the last level-
• Level-0 has 20 nodes i.e. 1 node
• Level-1 has 21 nodes i.e. 2 nodes
• Level-2 has 22 nodes i.e. 4 nodes
Continuing in similar manner, we have-
Level-
log2n has 2log2n nodes i.e. n nodes

Step-05:
Determine cost of last level-
Cost of last level = n x T(1) = θ(n)

Step-06:
Add costs of all the levels of the recursion tree and simplify the
expression so
obtained in terms of asymptotic notation-

ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA

= n x log2n + θ (n)
= nlog2n + θ (n)
= θ (nlog2n)

The master method for solving Recurrences

The Master Method is a popular technique used to solve recurrence
relations of the form:

T(n)=aT(n/b)+f(n)
here are the following three cases:
 If f(n) = O(nc) where c < Logba then T(n) = Θ(n Log a)
b

 If f(n) = Θ(nc) where c = Logba then T(n) = Θ(ncLog n)

 If f(n) = Ω(nc) where c > Logba then T(n) = Θ(f(n))

How does this work?

he master method is mainly derived from the recurrence tree method. If
we draw the recurrence tree of T(n) = aT(n/b) + f(n), we can see that the
work done at the root is f(n), and work done at all leaves is Θ(n c) where c
is Logba. And the height of the recurrence tree is Log bn

ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA

In the recurrence tree method, we calculate the total work done. If the
work done at leaves is polynomially more, then leaves are the
dominant part, and our result becomes the work done at leaves (Case
1). If work done at leaves and root is asymptotically the same, then
our result becomes height multiplied by work done at any level (Case
2). If work done at the root is asymptotically more, then our result
becomes work done at the root (Case 3).

Example:-1

Solve the following recurrence relation using Master’s theorem-

T(n) = 3T(n/2) + n2

Solution-

We compare the given recurrence relation with T(n) = aT(n/b) + θ

(nklogpn).

Then, we have-

a=3

b=2
ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA
k=2

p=0

Now, a = 3 and bk = 22 = 4

Clearly, a < bk.

So, we follow case-03.

Since p = 0, so we have-

T(n) = θ (nklogpn)

T(n) = θ (n2log0n)

Thus,
T(n) = θ (n2)

Example:-2

T(n)=8T(n/2)+n2

The recurrence is of the form:

T(n)=aT(n/b)+f(n)

From the given equation:

 a=8 (number of subproblems)

 b=2 (factor by which the problem size is reduced)
 f(n)= n2 (extra work done outside recursion)

logba=log28=3
Compare f(n)with nlogba
f(n)=n2
nlogba=n3

ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA

 Since f(n)=O(n2) and n2<n3 this falls under Case 1 of the Master
Theorem:
T(n)=O(nlogba)=O(n3)
Final Answer:
T(n)=O(n3)

The Hiring Problem

For example, you are using an employment agency to hire a new
assistant for your company. The agency works in such a way that it
sends you one candidate per day. You then interview the candidate after
which you must immediately decide whether or not to hire that person.
Also, if you hire that person, you must fire your current office assistant.
Even if it is someone you have hired recently you must fire them before
you hire a new assistant.

For this, let us consider the cost to interview as ci per candidate and the
cost to hire the candidate is ch.
Also, there are a few requirements to be fulfilled which are:
 At all times, you want to have the best candidate you have seen so far.
 Whenever you interview a candidate and feel that the candidate is better
than your current assistant, you have to fire the current assistant and
then hire the candidate.
 You should also always hire the first candidate that you interview.

Best-Case Analysis for Hiring Problem

 We get the best case when the agency sends us the best applicant on the
first day.
 The cost would be nci+ch

ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA

 Worst-case Analysis for Hiring problem

 The worst case is when we hire all the n candidates.

 This happens only if each candidate that comes later is better than all
those who came before. That is when candidates come in increasing
order of quality.
 The cost would be nci+nch
 Whenever this happens, we will fire the agency.

Average-case Analysis for Hiring problem

 For the average case, an input to the hiring problem is an ordering of

the n applicants, there are n! different inputs.
 To use probabilistic analysis, we assume that the candidates arrive in
random order.
 Then we analyze our algorithm by computing an expected running
time.
 This expectation is taken over the distribution of all the possible inputs.
 Thus, we are averaging the running time over all possible inputs.

Now, we want to know the expected cost of our hiring algorithm in

terms of the number of times we hired an applicant.

 For this, Random variable X(s) is the number of applicants who are
hired for a given input sequence s.
 Indicator random variable Xi for applicant i will be 1 if applicant i is
hired, 0 otherwise.

What is Indicator Random Variable?

It is a powerful technique that is used for computing the expected

value of a random variable. Also, it is a convenient method for

ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA

 converting between probabilities and also expectations. Indicator
Random Variable takes only 2 values, which are 1 and 0.
Indicator Random Variable XA=I{A} for an event A of a sample
space is defined as:

I{A} = 1 if A occurs
0 if A does not occur

The expected value of an indicator Random Variable is associated

with an event A is equal to the probability that A occurs.

Indicator RV – Example

Problem: Determine the expected number of heads in one toss.

 Sample space is s{H, T}
 Indicator random variable

XA= I{ coin coming up with heads}=1/2

 The expected number of heads obtained in one flip of the coin is equal
to the expected value of the indicator random variable.

Therefore, E[XA] = 1/2

This is all about probabilistic analysis, Hiring problem, and the

Indicator random variable.

RANDOMIZED ALGORITHMS:

Deterministic algorithm is an algorithm in which for given particular

input it will always produce the same output, with the underlying
machine always passing through the same sequence of states as shown
in figure.

ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA

 1. To overcome the computation problem of exploitation of running
time of a deterministic algorithm, randomized algorithm is used.
2. Randomized algorithm uses uniform random bits also called as
pseudo random number as an input to guides its behavior
(Output).
3. Randomized algorithms rely on the statistical properties of
random numbers. One example of a randomized algorithm is
quicksort.
4. It tries to achieve good performance in the average case.
5. Randomized algorithm is also called as probabilistic algorithm.
6. Randomized algorithm flow steps is shown figure 2.

Example:
The problem of finding ‘a’ in an array of n elements:
In a given array of n elements let half elements are ‘a’ and that of half
are ‘b’. One approach of the approach is to look at each element of the
array and this is an expensive one and will take n/2 operations, if the
array were ordered as ‘b’s first followed by ‘a’s. With this approach we
cannot guarantee that the algorithm will complete quickly.
Using randomized algorithm, if we look randomly then we can find ‘a’
quickly with high probability.
ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA
Advantage of Randomized Algorithm:

1. The algorithm is usually simple and easy to implement.

2. The algorithm is fast with very high probability, and/or it
produces optimum output with very high probability.

Uses:
Randomized algorithms are particularly useful when faced with a
malicious attacker or “adversary”

ANALYSIS AND DESIGN ALGORITHMS POOJA BHDAURIYA