AMIETE
– CS/IT (NEW SCHEME) – Code: AC64/AT64
Subject: DESIGN & ANALYSIS OF ALGORITHMS
Time: 3 Hours
Max. Marks: 100
NOTE: There are 9 Questions in all.
· Question 1 is compulsory and
carries 20 marks. Answer to Q.1 must be written in the space provided for it in
the answer book supplied and nowhere else.
· Out of the remaining EIGHT
Questions, answer any FIVE Questions. Each question carries 16 marks.
· Any required data not
explicitly given, may be suitably assumed and stated.
Q.1 Choose
the correct or the best alternative in the following: (2
10)
a. Which of the
following order of growth is correct?
(A) 
(B) 
(C) 
(D) 
b. An increasing sequence of keys results in creation of
a binary search tree that of _________ in nature.
(A) Complete tree (B) Skewed tree
(C) State space tree (D) Balanced tree
c. Solution to
Josephus problem is obtained by using the design strategy
(A) Divide and conquer (B) Decrease by a constant
(C) Decrease by a
constant factor (D) Variable size
decrease
d. Assume
that the adjacency list of a graph follow the alphabetical order of the vertex
labels. Starting with node ‘a’, DFS of the following graph is _________.
(A) a, b, d, f, c, g, e (B)
a,
b, d, f, c, e, g
(C) a, c, e, g, b, d, f (D)
a,
d, e, b, c, f, g
e. A polynomial,
2x4 - x3 + 3x2 + x - 5 can be represented by
Horner’s rule as:
(A) 2*x*x*x*x – x*x*x +3*x*x
+ x -5
(B) x3(2x -
x) + x(3x + 1) - 5
(C) x( x (x( 2x – 1)+3)
+ 1)-5
(D) None of the above.
f. Heapsort uses
___________
(A) Ordinary queue (B) Circular queue
(C) FIFO queue (D)
Priority queue
g. The time complexity of sorting by distribution
counting compared to merge sort is ______________.
(A) n log n Vs. n log n (B)
n
Vs. n log n
(C) n Vs. n2 (D) n log n Vs. n2
h. Back-Tracking
and Branch-and-bound based solutions use ___________.
(A) Spanning Tree (B) Decision Tree
(C) Binary tree (D) State-space tree
i. NP is the
class of all decision problems whose randomly guessed solutions can be verified
in __________.
(A) Polynomial time (B) Exponential time
(C) NP Hard time (D)
NP complete time
j. All operations
in AVL trees are in
(A) O(n) (B) O(log n)
(C) O(n log n) (D) O(n2)
Answer any FIVE Questions out
of EIGHT Questions.
Each question carries 16
marks.
Q.2 a. Consider the following algorithm for finding
the distance between the two closest elements in an array of numbers.
Min-Distance(A[0…n-1])
dmin
¬ Ą
for i
¬ 0 to n-1 do
for
j ¬ 0 to n-1 do
if i ą j and |A[i]- A[j]| < dmin
dmin ¬ |A[i]- A[j]|
return dmin
Make as many improvements as you can in this
algorithm solution to the problem. Illustrate the efficiency of the proposed
algorithm with the existing one by taking an example. (8)
b. Consider the
following undirected graphs in figure (a) and (b). Provide the adjacency matrix
for each of them and explain what property of the matrix indicates that
(i) The
graph is complete
(ii) The
graph has a loop; ie an edge connecting a vertex to itself
(iii) The
graph has an isolated vertex; ie a vertex has no edge incident to it. (8)
Q.3 a. Define
worst-case efficiency, best-case efficiency and average-case efficiency of an
algorithm. (6)
b. Write the pseudo-code of the sequential search algorithm to
search for a key K in a list of n items. (4)
c. Find out
worst-case efficiency, best-case efficiency and average-case efficiency of the
sequential search algorithm. Express them using asymptotic notations. (6)
Q.4 a. Write
the pseudo-code of selection sorting algorithm. Analyze its time complexity.
Sort the list E, X, A, M, P, L, E in alphabetical order by using this
algorithm.
(10)
b. Let the array
given to binary search be 3, 14, 27, 31, 39, 42, 55, 70, 74, 81, 85, 93, 98.
(i) What
is the largest number of key comparisons made and when?
(ii) What
is the number of key comparisons made when key = 14, key = 27, key = 93 and key
= 99. (6)
Q.5 a. What is the design strategy used for finding
topological sorting? (2)
b. For what type
of graphs, topological sorting is impossible?
(2)
c. Consider the directed graph given below, find
the topological sorting using (a) DFS based algorithm (b)
source-removal algorithm. Assume that the adjacency list of a graph
follow the alphabetical order of the vertex labels. If there is a tie in
deletion, one with lower alphabetical order is considered. (12)
Q.6 a. Explain
briefly the concept of transform-and-conquer strategy, indicating the three
major variations of the same. Give an example problem for each case which can
be solved by using the method. (8)
b. What are AVL trees?
For the list “3, 6, 5, 1, 2, 4”, construct an AVL tree by inserting the
elements successively, starting with an empty tree. (8)
Q.7 a. What
is the deficiency of Dijkstra’s algorithm? What is its time complexity if
priority queue is used to represent the input graph? Solve the following
instance of the single-source shortest-path problem with ‘i ‘as source node. (8)
b. Apply bottom-up dynamic programming algorithm to the
following instance of Knapsack problem with capacity W = 6. What is the optimal
solution? (8)
|
Item |
Weight |
Value |
|
1 |
3 |
Rs. 25 |
|
2 |
2 |
Rs. 20 |
|
3 |
1 |
Rs. 15 |
|
4 |
4 |
Rs. 40 |
|
5 |
5 |
Rs. 50 |
Q.8 a. For
the input 30, 20, 56, 75, 31, 19 and hash function h(K) = K mod 11
(i) Construct
the hash table
(ii) Find
the largest number of key comparisons in a successful search in this table
(iii) Find the average number of key comparisons
in a successful search in this table (10)
b. Define the
following and give two examples for each. (6)
(i)
Polynomial class problems (ii) NP complete problems
Q.9 a. Explain the commonalities and differences
between back-tracking and branch-and-bound design techniques. (6)
b. Define
n-queens problem. Explain how n-queen’s problem can be solved by using
back-tracking by taking an example of n = 4. Show the generated state-space
tree. (10)
|
|
List A |
List B |
|
1 |
110 |
110110 |
|
2 |
0011 |
00 |
|
3 |
0110 |
110 |