USN 1 S I 4RCS03
Siddaganga Institute of Technology, Tumakuru-572 103
(An Autonomous Institution affiliated to VTU, Belagavi, Approved by AICTE, New Delhi)
Supplementary Semester B.E. Computer Sc. and Engg. Examinations Sept. 2023
Analysis and Design of Algorithms
Time: 3 Hours Max. Marks: 100
Note : 1. Revealing of Identity in any form in the answer book/graph sheet will be treated as malpractice.
2. Answer any five questions choosing one full question from each unit.
Unit - I M BL CO PO PSO
01 a) With the help of a flow chart, explain the various stages of algorithm design and
analysis process. 6 1 1 1
b) Develop a brute force algorithm to check whether all the elements in a given array
are distinct. If c(n) denotes the number of times of algorithm’s basic operation is
executed, derive an expression for c(n) for the above algorithm. 6 2 2 1
c)Write a recursive algorithm to find biggest element in an array and analyze its
efficiency by writing its recurrence relation. 8 2 2,4 1
OR
02 a) Given a positive decimal integer n, write a recursive algorithm which computes
the factorial of n. Set up the corresponding recurrence relation, solve the same and
identify the asymptotic efficiency class it belongs to. 7 2 2,4 1
b) Define space complexity and time complexity. Explain the two approaches of
estimating run time of an algorithm. 6 2 1 1
c) With a suitable algorithm explain the best, worst and average case efficiencies for
sequential search technique. 7 2 1 1
Unit - II
03 a) Design an algorithm to sort the elements using quick sort using divide and conquer
technique and apply the same to sort the list S, O, R, T, I, N, G. 10 2 3 3
b) Write the pseudocode for merge sort algorithm. Estimate the worst case
complexity of the merge sort using Master theorem. 10 3 2,4 1
OR
04 a) Design an algorithm for Brute-force string matching and obtain the time efficiency
of the algorithm in the worst-case and average case. Find the number of character
comparisons that will be made by string matching algorithm for the pattern
ABABC in text BAABABABCCA. 8 3 3 3
b) Discuss advantages and disadvantages of divide and conquer technique. 4 1 2 1
c) Describe a Brute force algorithm to find two numbers in an array whose sum
equals a given value and analyze its efficiency. 8 2 3 3
Unit - III
05 a) What is meant by AVL tree? Construct an AVL tree for the list (15, 16, 18, 13, 12,
14, 17} by inserting the elements of list successively, starting with the empty tree. 8 3 2 1
b) Write an algorithm to construct a heap by bottom up method. Trace the same for
the list {11, 18, 16, 15, 13, 17, 14} to construct a heap. 7 3 2 1
c)What are the major variations involved in transform and conquer method. Give
examples of each variation. 5 2 2 1
OR
06 a) Design an algorithm for DFS. With an example, explain how this algorithm can be
used to solve topological sorting problem. 10 3 3 3
-1- Please Turn Over
-2- 4RCS03
b) What are the AVL trees? Explain different rotations with respect to AVL trees. 5 2 2 1
c) Construct heap and trace the list 2, 9, 7, 6, 5, 8 using heap sort algorithm using
bottom-up method. 5 3 2 1
Unit - IV
07 a) Apply dynamic programming algorithms to the following instance of Knapsack
problem and find the optimal subset.
Item i Value Vi Weight Wi
1 8 2
2 6 1
3 16 3
4 11 2
Given Knapsack capacity M = 5. 6 3 2,3 1,3
b) Design Warshall’s algorithm to compute the transitive closure of a graph. Apply
the algorithm to determine transitive closure for the following adjacency matrix.
a b c d e
a 0 1 0 0 0
b 0 1 1 0 0
c 0 0 0 0 1
d 0 0 1 0 0
e 0 0 0 1 0 8 3 2,3 1,3
c) Write an algorithm for computing binomial co-efficient and discuss its
complexity. Compute binomial co-efficient for n=8, r=4. 6 4 2,3 1,3
OR
08 a) Write Floyd’s algorithm for computing the all-pairs
shortest-paths of a given weighted connected directed
graph, analyse its efficiency and trace the algorithm for
the graph given in Fig. 8(a).
Fig. 8(a) 10 4 3,4 2,3
b) Write Dijikstra’s algorithm and apply the same for
the following graph. Analyze the efficiency of the
algorithm.
10 4 3,4 2,3
Unit - V
09 a) State n-queens problem. Discuss how do you solve n-queens problem using back
tracking method and write state space tree of solving the four n-queens problem by
back tracking. 10 3 2,3 1,3
b) Write Horspool’s algorithm. Apply the same to search for the pattern LEADER in
the text:
JIMY_RAN_HAILED_THE_LEADER_TO_STOP. 10 3 2,3 1,3
OR
10 a) What is back tracking? Write state space tree for solving the 4-queens problem by
back tracking. 7 2 2,3 1,3
b) Write the state-space tree to solve the following instance of the subset-sum
problem: S = {1, 2, 3, 4, 5} and d = 6. 6 3 2,3 1,3
c) Differentiate between P, NP and NP complete problems. Give examples for each. 7 2 1 1
________
