Gujarat Technological University 2010 M.E Computer Algorithm - Question Paper

GUJARAT TECHNOLOGICAL UNIVERSITy
M.E Sem-I exam January 2010
Subject code: 710201 Subject ame: Computer Algorithm
Total Marks: 60
Instructions:
1. Attempt all ques..
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
Q.1 (a) obtain out complexity of
T (n) = 3T (n/2) + n2,
T (n) = 16T (n/4) + n, using master method in terms of O (Big Oh)
06
(b) discuss worst case and Best case complexity of INSERTION sort. 06
Q.2 (a) Difference ranging from red-black tree and AVL tree. (In terms of application)
with example.
06
(b) If 48 bit word is provided for RADIX sort with r=24, How many maximum
passes would be needed for Radix sort to sort approximately 3000 nos.
Prove your ans. How many passes would be needed for Merge sort in
above case?
06
OR
(b) Create AVL tree for subsequent sequence of insertion
Jan, Feb, … Dec
06
Q.3 (a) discuss the utilization of augmented data structure with info and
Rank in beneath provided example.
06
(b) Generate formula for chain Matrix multiplication using Dynamic
programming and obtain out minimum no of multiplication needed for
multiplying: A [50 × 10], B [10 × 89] and C [89 ×
15].
06
OR
Q.3 (a) For a graph G = (V, E) with V no of Vertices and E no of Edges. Where V=12
and E=23. What type of storage would be used to store info of Adjacent
Nodes? What would be storage requirement/complexity for maintaining
info for adjacent List and adjacent Matrix?
06
(b) discuss various kinds of Edges in DFS with suitable example. 06
Q.4 (a) discuss Prim's algorithm with time and space complexity. 06
(b) define a naive algorithm for solving the Hamiltonian-cycle issue with
running time complexity?
06
OR
Q.4 (a) discuss how Parallel algorithms differ to Sequential algorithms. Write Parallel
algorithms and Sequential algorithms algorithm to sum n no's.
06
2
(b) 1) Parallel radix sort algorithm
A) Extend the parallel radix sort algorithm where the number n of
elements to be sorted is larger than the number p of processors.
06
Q.5 (a) Compare and contrast Binomial Heap and Fibonacci Heap. discuss procedure of
merging 2 Binomial Heaps.
06
(b) discuss data structure of a Fibonacci Heap using suitable example. 06
OR
Q.5 (a) How Disjoint Set Forest can be implemented? give related algorithm. 06
(b) Write an algorithm to delete a key from B-tree. Trace your algorithm on suitable
example.
06
*************

Earning:   Approval pending.