18IS6C2

USN
RV COLLEGE OF ENGINEERING®
(An Autonomous Institution affiliated to VTU)
VI Semester B. E. Examinations August 2022
Common to ISE/CSE
ADVANCED ALGORITHMS (Elective)
Time: 03 Hours Maximum Marks: 100
Instructions to candidates:
1. Answer all questions from Part A. Part A questions should be answered
in first three pages of the answer book only.
2. Answer FIVE full questions from Part B. In Part B question number 2, 7
and 8 are compulsory. Answer any one full question from 3 and 4 & one
full question from 5 and 6.

PART-A

1 1.1 The worst case time complexity of bucket sort (k=number of buckets)
is ______. 01
1.2 The time complexity of constructing the prefix table used in Knuth
Morris Pratt algorithm where the length of text is and length of
pattern as will be ______. 01
1.3 The method used to solve Bellman-Ford algorithm is ______. 01
1.4 In case of finite automata based string matcher for the pattern
on the text , how many times the system
encounters second state while searching the pattern until second
occurrence? 01
1.5 The time complexity of the algorithm computing shortest path of a
Direct Acyclic Graph is ______. 01
1.6 For the recurrence ( ) ( ) , using substitution method
( ) ______. 02
1.7 Calculate the time complexity for the code below.

( )
*
( )
*

+
+ 02
1.8 Consider the two matrices P and Q which are and
matrices respectively. What is the number of multiplications required
to multiply the two matrices? 01
1.9 For the direct acyclic graph in Fig 1.9, identify the shortest path from
source S with sequence .

Fig 1.9 02
 1.10 For the strings “ABCDEABCD” and “ACPEAQCBCAD”, write the
length of the longest common subsequence. 01
1.11 The time complexity of Active Selection Problem using greedy
technique is ______, if the activities are sorted according to their finish
time. 01
1.12 Write any two applications of modular arithmetic. 01
1.13 The time complexity of Fibonacci heaps can be given as ______. 01
1.14 Arrange the elements of the array A= {11, 23, 78, 123, 90, 45} after
second iteration of radix sort accordingly. 02
1.15 For which sorting algorithm, time complexity remains to be the same
in its best, average and worst case? 01
1.16 When Ford-Fulkerson is implemented using BFS to construct
augmented path, the worst case time complexity can be ______. 01

PART-B

2 a For the function ( ) ( ( )), prove ( ) ( ( )) and

( ) ( ( )). 06
b Consider the stack operations push, pop and multipop. Discuss the
accounting method to determine the amortized cost of these
operations. 06
c Consider the function ( ) , check whether ( ) ( ). 04

3 a Given a set of activities with their start and finish time, compute the
maximum number of non-overlapping activities using Activity
Selection algorithm.
( )
( )
( ) 06
b Write an algorithm to solve matrix chain multiplication using
dynamic programming. Give the analysis of the algorithm. 04
c Perform radix sort on the below input.
06

OR

4 a Write an algorithm to perform counting sort and discuss its efficiency.

Explain with an example. 08
b Write an algorithm to perform bucket sort and discuss its efficiency.
Apply the same on the below input.
9.6, 0.5, 11.1, 1.8, 2.07, 2.04, 4.0, 7.0, 3.8, 6.68 08

5 a Apply Bellman Ford algorithm for the graph shown in Fig 5a and
analyze the time complexity. Show the execution stepwise.

Fig 5a 08
 b Write the Ford-Fulkerson algorithm for maximum flow problem with
an example. Analyze its complexity. 08

OR

6 a Write Johnson’s algorithm and discuss its complexity. Apply the

algorithm to find all pair shortest path for the graph shown in Fig 6a.

Fig 6a 08
b Write an algorithm for maximum bipartite matching and analyze its
complexity. 08

7 a Discuss the addition and multiplication properties of modular

arithmetic. 05
b Briefly discuss Chinese Remainder theorem. 06
c Write a note on elementary number theory. 05

8 a Write the functions required in implementation of Binomial heap. 08

b Discuss the operations of splay trees in detail. 08