DAYANANDA SAGAR ACADEMY OF TECHNOLOGY AND MANAGEMENT

(Affiliated to Visvesvaraya Technological University, Belagavi & Approved by AICTE, New Delhi)
22 Mile, B.M Kaval, Opp. to Art of Living, Udayapura, Kanakapura Road, Bangalore-560082.
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
(Accredited by NBA, New Delhi for 3 Years Validity: 26-7-18 to 30-6-2021)

Even Semester February-2020 to May-2020 Session( 2019-2020)

CLASS- 4th A & B Faculty: Manasa Sandeep & Chethana V

SUBJECT: Design and Analysis of Algorithms (18CS42)

Course Outcomes:

CO 1: Describe computational solution to well known problems like searching, sorting etc.
CO 2: Estimate the computational complexity of different algorithms.
CO 3: Design and develop an algorithm for problems using appropriate design strategies.
CO 4: Apply and implement learned algorithm design techniques and data structures to solve
real- world problems.
Assignment II
1. Write a recursive algorithm for binary search and also bring out its efficiency
(10 Marks, June 2017) CO2

Recursive Binary Search Algorithm

Analysis
 Input size: Array size, n
Basic operation: key comparison
Depend on
Best – key matched with mid element. Key is present in the middle of the array.
Worst – key not found or key sometimes at last in the list.

Let C(n) denotes the number of times basic operation is executed. Then
Best Case: number of comparison = 1 Ω(1)

Worst Case:
T(n) = Worst case efficiency. Since after each comparison the algorithm divides the
problem into half the size, we have to search either the upper part or the lower part of the
array. Time complexity is given by the following recurrence relation

T(n) = 1 + T(n/2) Replace n by n/2

T[n/2] = 1 + T[n/4]
= 1 + [1 + T(n/4)]
= 2 + T[n/22]
……
= i + T [n/2i]
To get the initial condition T(1) n=2i or i=log2n
= i + T(1) T(1) =1
T(n) = 1 + log2n
= Θ(log n)

2. a. List out the advantages and disadvantages of divide and conquer method and illustrate
the topological sorting for the following graph using DFS method. (06 Marks, Dec
2017(CO1))

Advantages and disadvantages of divide and conquer

Advantages:

1. Complex problems are broken into smaller sub problems and each subproblem is
solved independently. Smaller subproblems are easier to solve than complex large
problems.
2. It yields efficient algorithms like quick sort, merge sort, Strassen’s matrix
multiplication etc.
3. The subproblems can be executed on parallel processes.
Disadvantages:

1. Large number of sublists are created and need to be processed.

2. Divide and conquer algorithm makes use of recursive methods. Recursion is slow and
complex.
Topological Sorting by DFS method

Steps:

1. Perform DFS traversal by pushing the elements into the stack

2. Pop the elements from the stack.
3. Reverse the popped elements
4. The resulting order gives the topological sorting of the elements.
Problem 1:

b. Apply source elimination based algorithm to represent vertices in topological ordering

for the digraph given in the following figure (CO4) (04 Marks, Dec 2012)

3. a.Discuss Strassens matrix’s multiplication and Explain with example

(05 Marks, Dec 2017) (CO3)

Let A and B be two matrices. The product AB can be computed by using divide and conquer
approach is as follows:
Here A11, A12, …..B22 are the submatrices of size n/2.
This approach requires eight multiplications of n/2 X n/2 matrices and four additions of n/2 X
n/2 matrices. Since two n/2 X n/2 matrices can be added in time cn2 for some constant c, the
overall computing time T(n) is given by the following recurrence relation.

By solving the above recurrence we get T(n) = O(n3).

Strassen’s Matrix multiplication: Volker Strassen showed that 2 X 2 matrix multiplication can
be accomplished in 7 multiplication and 18 additions or subtractions. Since matrix
multiplications (order of growth: n3) are more expensive than matrix addition/subtraction (order
of growth n2), even with reduction in one multiplication will improve the algorithm.
This method involves first computing the seven n/2 X n/2 matrices P, Q, R, S, T, U, and V. Then
C is computed. The formula’s are as follows:

From the above formulas, we can see that to compute P, Q, R, S, T, U, V, it requires 7 matrix
multiplications and 10 matrix additions or subtractions. Computing C requires additional 8
additions/subtractions.

b. Give the time complexity for Strassens matrix’s multiplication

(05Marks, Dec 2017) (CO2)

The resulting recurrence relation for T(n) is

Where a and b are constants.

Sole the recurrence relation by backward substitution
T(n) = 7T(n/2) + an2. Replace n by n/2.
= 7 [7 T(n/22) + a(n/2)2] + an2.
= 72 T(n/22) + (7/4) an2 + an2. Replace n by n/4
= 72 [7 T(n/23) + a(n/4)2] + (7/4) an2 + an2.
= 73 T(n/23) +(7/4)2 an2 + (7/4) an2 + an2. Rearranging the terms, we get
= an2 [1+ 7/4 + (7/4)2] + 73 T(n/23)
……………………………………….
= an2 [1+ 7/4 + (7/4)2…….(7/4)i-1] + 7i T(n/2i) Note: 1+ 7/4 + (7/4)2…….(7/4)i-1 ≈
(7/4)i
= an2 (7/4)i + 7i T(n/2i). Substitute 2i= n, then i=log n.
= an2 (7/4)log n + 7log n T(1).
= an2 (7/4)log n + 7log n because T(1) = b= constant
2 log(7/4) log 7
= an n +n
= an2 nlog 7-log 4 + nlog 7
= a nlog 4 nlog 7-log 4 + nlog 7
= a nlog 4+log 7-log 4 + nlog 7
= a nlog 7+ nlog 7
= O(nlog27)
≈ O(n 2.81)

4. Write an recursive algorithm to find the maximum and minimum elements in a given
array of n elements by applying the divide and conquer technique and write recursive tree
for list of numbers 22,13,-5,-8,15,60,17,31,47 and give its time complexity.
(06 Marks, Dec 2017) (CO3)
Recursive algorithm to find the maximum and minimum elements in a given array of n
elements by applying the divide and conquer technique is given by:

Recursive call tree made by MaxMin(low, high, Max, Min) on the following set of data:
 22, 13, -5, -8, 15, 60, 17, 31, 47

Position 1 2 3 4 5 6 7 8 9
data 22 13 -5 -8 15 60 17 31 47

Fig: Tree of recursive calls of MaxMin

(Note: The circled numbers in the upper left corner of each node represent the orders in
which max and min are assigned).

Analysis
Input size: n- the number of elements.
Basic operation: Comparison statement.

Recurrence relation

Solving the recurrence relation by backward substitution method:

T(n) = 2 T(n/2) + 2
= 2[2 T(n/22) + 2] +2
= 22 T(n/22) + 22 + 2
= 23 T(n/23) + 23+ 22 + 2
……..
= 2i T(n/2i) + 2i+…. + 23+ 22 + 2 2i+…. + 23+ 22 + 2 = 2. (2i-1)/2-1
i
= n. T(1) + 2. (2 -1)/2-1
= 0+ 2. (n-1) = Θ(n)

5. a. If n € [2k-1, 2k], prove that binary search algorithm makes at most K element
comparisons for a successful search and either K - 1 or K. comparisons for an
unsuccessful search. (07 Marks, June 2012)(CO2)
Proof: Consider the Binary decision tree describing the action of Binary Search of n
elements. All successful searches end at a circular node whereas all unsuccessful searches
end at a square node.
 If 2k-1 ≤ n ≤ 2k [because n is in range [2k-1, 2k]]

Then all circular node are at the levels 1, 2, 3…….k

Whereas all square node are at levels k and k+1

The number of element comparisons needed to terminate at a circular node on level i is

“i”, whereas the number of element comparison needed to terminate at a square node at
level i is only “i-1”

To determine the average behavior

The distance of a node from the root is one less than its level.

The internal path ‘I’ is the sum of the distance of all internal nodes from the root.

The external path length ‘E’ is the sum of the distance of all external nodes from
the root.

For any binary tree with n internal nodes E and I are related by the formula E=I + 2n

There is a simple relationship between E, I and the average number of comparison in

binary search.

Let As(n) → The average number of comparison in successful search.

Au(n) → The average number of comparison in unsuccessful search.

The number of comparison needed to find an element represented by an internal node is

one more than the distance of this node from the root, hence

As(n) = (1+I/n)

The number of comparison on any path from the root to an external node is equal to the
distance between the root and the external node.

Since every binary tree with n internal node has n+1 external nodes

Au(n) = E / (n+1)

Using these 3- formula E, As(n) and Au(n)

 As(n) = (1 + 1/n) Au(n) -1

From this formula we see that As(n) and Au(n) is directly related.

E is proportional to nlogn. Using this in the preceding formula we conclude that As(n)
and Au(n) are both proportional to log n.

b. Consider the following set of 14 elements in an array list, -15, -6, 0, 7, 9, 23, 54, 82,
101, 112, 125, 131, 142, 151 when binary search is applied on these elements, find the
elements which required maximum number of comparisons. Also determine average
number of key comparisons for successful search and unsuccessful search.
(03 Marks, Dec 2012)(CO4)

The elements that require maximum number of comparisons are -6, 7, 23, 82, 112, 131,
151.
Binary decision tree for binary search n=14
 So, no element requires more than 4 comparisons.
The average comparison is obtained by summing the comparisons needed to find all 14
items and dividing by 14.
i.e, (3 + 4 + 2 + 4 + 3 + 4 + 1 + 4 + 3 + 4 + 2 + 4 + 3 + 4) /14 = 45/14 = 3.21

There are 15 possible ways in which unsuccessful search may terminate.

If x<a[1], the algorithm requires 3 element comparisons to determine x is not present.
For all remaining possibilities, it requires 4 element comparisons.
So average number of element comparisons for an unsuccessful search is
(3 + 14 * 4) /15 = 59/15 = 3.93

6. Write a greedy algorithm(Dijkstra’s algorithm) to find single source shortest path, Trace
the following graph to get shortest path from vertex 'a' to all other vertices.

(10 Marks, Dec 2017) (CO1, CO3)

Dijkstra’s algorithm finds the shortest paths to a graph’s vertices in order of their distance
from a given source. First, it finds the shortest path from the source to a vertex nearest to
it, then to a second nearest, and so on. In general, before its ith iteration commences, the
algorithm has already identified the shortest paths to i − 1 other vertices nearest to the
source
Using greedy method, trace the following graph to get shortest path from vertex 'a' to all other
vertices.

7. a. Obtain the optimal solution for the job sequencing problem with deadline, wheren=5,
[P,,P2,P3,P4,P5 ] = [20, 15, 10, 5, l]and[d1 ; d2 , d3 , d4, d5] = [2, 2, 1, 3, 3]
(05 Marks, June/July, 2016) (CO3)
The solution generated by the function job scheduling (JS) when n=5
i 1 2 3 4 5

Pi 20 15 10 5 1

di 2 2 1 3 3
The jobs are already arranged in the descending order of their profits.

b. What is greedy method and Write greedy method control abstraction for subset
paradigm. (05 Marks, Dec 2014)(CO3)

The greedy approach suggests constructing a solution through a sequence of steps.

• Each step expands a partially constructed solution obtained so far, until a
complete solution to the problem is obtained.
• If the inclusion of next input into the partially constructed optimal solution will
result in an in feasible solution, then this input is not added to the partial solution,
otherwise it is added.
• So, the choice made in the each step should be
feasible, i.e., it has to satisfy the problem’s constraints
locally optimal, i.e., it has to be the best local choice among all feasible choices
available on that step
irrevocable, i.e., once made, it cannot be changed on subsequent steps of the
algorithm
• Greedy is applicable to optimization problems only.
 Greedy algorithm suggests a “greedy” grab of the best alternative available in the hope
that a sequence of locally optimal choices will yield a (globally) optimal solution to the
entire problem.

8. a.Define minimum cost spanning tree,Write Prim’s algorithm to construct minimum cost
spanning tree. (05Marks,Jan 2018)(CO3)

Minimum cost Spanning Tree

Let G= (V, E) be an undirected connected graph. A subgraph t=(V, E’) of G is a spanning

tree of G iff t is a tree. Spanning tree is a tree in which all nodes are connected without
forming a closed path or circuit. A spanning tree whose cost is minimum is called
minimum cost spanning tree(MST).

Fig: A graph and its possible three spanning trees

Prim’s Algorithm

Prim’s algorithm is a greedy method to obtain a minimum –cost spanning tree. It builds
tree edge by edge. The next edge to include is chosen with a minimum increase in the
sum of the costs of the edges so far included. ‘A’ is a tree formed by the set of edges
selected so far. The next edge (u,v) to be included in ‘A’ is a minimum –cost edge not in
A with the property that A U {(u,v)} is also a tree
 The initial subtree in such a sequence consists of a single vertex selected
arbitrarily from the set V of the graph’s vertices. On each iteration, the algorithm expands
the current tree in the greedy manner by simply attaching to it the nearest vertex not in
that tree. The algorithm stops after all the graph’s vertices have been included in the tree
being constructed. Since the algorithm expands a tree by exactly one vertex on each of its
iterations, the total number of such iterations is n − 1, where n is the number of vertices in
the graph. The tree generated by the algorithm is obtained as the set of edges used for the
tree expansions.

b.obtain minimum cost spanning tree using Prim’s algorithm for the graph whose weight
matrix is given below: (05 Marks, June, 2016) (CO1)

0 3 ∞ 7 ∞
3 0 4 2 ∞
∞ 4 0 5 6
7 2 5 0 4
∞ ∞ 6 4 0

9. Write a Kruskal algorithm to find minimum cost spanning tree and obtain spanning tree
of the graph shown below:

(10 Marks, June/July, 2016) (CO1, CO3)

Kruskal’s algorithm looks at a minimum spanning tree of a weighted connected graph
G = V, E as an acyclic subgraph with |V| − 1 edges for which the sum of the edge weights
is the smallest.
The algorithm begins by sorting the graph’s edges in non decreasing order of their
weights.
Then, starting with the empty subgraph, it scans this sorted list, adding the next edge on
the list to the current subgraph if such an inclusion does not create a cycle and simply
skipping the edge otherwise.

On applying kruskul algorithm,

10. a.Construct a Huffman tree and resulting code word for the following:
Character A B C D -

Probability 0.35 0.1 02 0.2 0.15

Encode the words DAD and ADD. (05 Marks, June 2017) (CO3)
Arrange the given data in the increasing order of the given probability

Symbol B _ C D A
Probability 0.1 0.15 0.2 0.2 0.35

Now start construct the tree by merging two nodes at a time.

The Huffman code is as follows

Symbol A B C D _
Probability 0.35 0.1 0.2 0.2 0.15
Codeword 11 100 00 01 101
DAD is encoded as follows: 011101
10011011011101 = BAD_AD
2 * 0.35 + 3 * 0.1 + 2 * 0.2 + 2 * 0.2 + 3 * 0.15 = 2.25

b.Sort the given list of numbers using heap sort: 2, 9, 7, 6, 5, 8. (05 Marks, Dec 2017) (CO3)

11. a. Apply greedy method to obtain an optimal solution to the knapsack problem given
M=60, (W1, W2, W3, W4,W5)=(5,10,20,30,40) (P1, P2, P3, P4,P5) = (30,20,100,90,160)
Find the total profit earned, (05 Marks,June 2018)(CO2)

b. Explain the bottom–up heap construction algorithm with example. Give the Worst case
efficiency of this algorithm (05 Marks, June 2018) (CO1)

Bottom- up heap construction (Max Heap) : It initializes the essentially complete

binary tree with n nodes by placing keys in the order given and then “heapifies” the tree
as follows. Starting with the last parental node, the algorithm checks whether the parental
dominance holds for the key in this node. If it does not, the algorithm exchanges the
node’s key K with the larger key of its children and checks whether the parental
dominance holds for K in its new position. This process continues until the parental
dominance for K is satisfied. After completing the “heapification” of the subtree rooted
at the current parental node, the algorithm proceeds to do the same for the node’s
immediate predecessor. The algorithm stops after this is done for the root of the tree.
 This method is more efficient compared to top-down heap construction.

Problem: Construct bottom-up heap for the given data

2, 9, 7, 6, 5, 8

12. a.Explain the concept of Dynamic Programming with examples. (05 Marks, June 2017)
(CO1)

Dynamic programming is a technique for solving problems with overlapping

subproblems.These subproblems arise from a recurrence relating a given problem’s
solution to solutions of its smaller subproblems. Rather than solving overlapping
subproblems again and again, solve each of the smaller subproblems only once and
record the results in a table from which a solution to the original problem can then be
obtained.

Example, Knapsack Problem solving by dynamic approach

Given n items of known weights w1, . . . , wn and values v1, . . . , vn and a knapsack of
capacity W, find the most valuable subset of the items that fit into the knapsack. Here all
the weights and the knapsack capacity are positive integers; the item values do not have
to be integers.
Solution to knapsack problem using dynamic approach
We can divide all the subsets of the first i items that fit the knapsack of capacity j into
two categories: those that do not include the ith item and those that do.
1. Among the subsets that do not include the ith item, the value of an optimal subset is,
by definition,
F(i − 1, j).
2. Among the subsets that do include the ith item (hence, j – wi ≥ 0), an optimal subset is
made up of this item and an optimal subset of the first i − 1 items that fits into the
knapsack of capacity j − wi . The value of such an optimal subset is vi + F(i − 1, j − wi).
It can be expressed by using the following recurrence relation

The initial conditions are defined as follows: F(0, j) = 0 for j ≥ 0 and F(i, 0) = 0 for i ≥ 0.
Our goal is to find F(n, W), the maximal value of a subset of the n given items that fit into
the knapsack of capacity W, and an optimal subset itself. The following figure illustrates
the values involved in equations the above equations. For i, j > 0, to compute the entry in
the ith row and the jth column, F(i, j), we compute the maximum of the entry in the
previous row and the same column and the sum of vi and the entry in the previous row
and wi columns to the left.

The time efficiency and space efficiency of this algorithm are both in Θ(nW).

b.Explain multistage graphs with example.Write multistage graph algorithm to forward

approach (05 Marks.June 2017)(CO1,CO3)
Multistage Graph: A multistage graph G=(V, E) is a directed graph in which the
vertices are partitioned into k disjoint sets, Where k ≥ 2. (V1, V2, ….Vi,…Vk) . If
(u,v) is an edge in E, then u ϵ Vi and v ϵ Vi+1.
The Multistage-graph problem is to find a minimum-cost path from ‘s’ (source-
V1) to ‘t’ (sink-Vk).
Example: The following figure shows a five stage graph. A minimum-cost s to t
path is indicated by the broken edges.
Multistage graph problem can be solved by using two methods
Forward approach

Formula: