Download GTU (Gujarat Technological University Ahmedabad) B.Tech/BE (Bachelor of Technology/ Bachelor of Engineering) 2020 Winter 5th Sem 2150703 Analysis And Design Of Algorithms Previous Question Paper
Enrolment No.___________
GUJARAT TECHNOLOGICAL UNIVERSITY
BE- SEMESTER?V (NEW) EXAMINATION ? WINTER 2020
Subject Code:2150703 Date:22/01/2021
Subject Name:Analysis and Design of Algorithms
Time:10:30 AM TO 12:30 PM Total Marks: 56
Instructions:
1. Attempt any FOUR questions out of EIGHT questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
Q.1 (a) Define O, , notations with example.
03
(b) Sort following functions in increasing order of running time for large values 04
of n: n, log2n, 2n ,n2logn, n3
(c) (i) What are the different parameters to analyze any algorithm?
03
(ii) Solve the following using Master's theorem:
A. T(n) = 2T(n/4) + 1
04
B. T(n) = 3T(n/3) + n
Q.2 (a) Explain Master Theorem for all three cases.
03
(b) (i) What is the smallest value of n such that an algorithm whose running time 04
is 100n2 is runs faster than an algorithm whose running time is 2n on the same
machine?
(ii) What is meaning of T (n) =O(1). Explain with suitable example.
(c) Given the four matrices P5x4, Q4x6, R6x2, T2x7. Find the optimal sequence for 07
the computation of multiplication operation.
Q.3 (a) Mention the parameters for finding suitable algorithm among many candidate 03
algorithms. Justify parameter with suitable example.
(b)
i.
Which version of algorithm is preferred when memory resources are 04
limited, Iterative or recursive? Justify your answer.
ii.
An asymptotically fast algorithm running on Slow computer is better
than asymptotically slow algorithm is running on fast computer for
larger input size. (True/False) Justify your answer with supporting
arguments.
(c) Analyze Selection sort and Insertion Sort algorithms in best case and worst 07
case scenarios.
Q.4 (a) Merge sort algorithm have similar time complexity in best, average and worst 03
case. (True/False). Justify your answer.
(b) Differentiate between greedy approach and Dynamic approach..
04
(c) How the selection of pivot affects the performance of Quick Sort? Discuss all 07
possible scenarios.
Q.5 (a) How to solve knapsack problem using dynamic programming?
03
(b) Given two strings from 26 symbols set, X="BITTER", Y = "BUTTER" obtain 04
the longest common subsequence.
1
(c) Compare and contrast Branch and Bound and Backtracking Methods with 07
suitable example.
Q.6 (a) Generate
Huffman
Code
for
symbols
with
probability
as 03
A1(0.5),A2(0.25),A3(0.125),A4(0.0625),A5(0.0625).
(b) Find the all pair shortest path using Floyd-Warshall Algorithm for directed 04
graph shown below:
(c) How to solve 0-1 knapsack problem using dynamic programming? Consider 07
Items having Value(Rs.)={60,100,120} , Weight(KG)={10,20,30}
respectively, Weight Capacity =50 KG.
Q.7 (a) Define terms: Articulation Point, Isolated , Adjacency
03
(b) Solve the following Task Assignment problem for minimization using 04
following cost matrix.(Cost matrix represents cost of Task T performed by
Person P.
T1 T2 T3
P1 10 20 25
P2 20 23 26
P3 12 16 25
(c) Find minimum spanning tree for the following undirected weighted graph 07
using Kruskal's algorithm.
Q.8 (a) What is the significance of Hashing in Rabin-Karp Pattern matching 03
algorithm?
(b) Draw the Finite automata which accepts String over 26 letter alphabet of 04
{A...Z} : ACACAGA
(c) Explain the concept of P, NP and NP-complete problem
07
*************
2
This post was last modified on 04 March 2021