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. Algorithm is defined as a collection of
__________ instructions.
(A) ambiguous (B) unambiguous
(C) Both (A) & (B) (D) none of the above
b.
Space complexity is defined as amount of ______ required by an algorithm to
run.
(A) computer time (B) memory
(C) input size (D) performance
c. _______ method is used for representing upper
bound of algorithm’s running time.
(A) theta notation (B) big
oh notation
(C) omega notation (D) brute force
d. In _____ search method solution is obtained by
searching each element of given problem.
(A) sequential search (B) brute force string matching technique
(C) exhaustive search (D) none of the above
e. _________ method is asset of feasible
solutions & pick up the optimum solution.
(A) greedy (B) dynamic programming
(C) brute force method (D) none of the above
f. Knapsack problem can be solved by using
_________ programming approach.
(A) dynamic programming (B) greedy technique
(C) both (A) & (B) (D) none of
the above
g. The best case complexity of insertion sort is
(A) O(n) (B) O(n2)
(C) O(1) (D) O(n log2 n)
h. Hashing is a
technique based on the idea of __________
(A) prestructuring (B) poststructuring
(C) sorting (D) greedy method
i. In ______ technique search is redefined at
each stage by eliminating the possibility of a non generating solution.
(A) backtracking (B) greedy
(C) brute force (D) none of the above
j. Computational
time efficiency can be achieved by _________ technique.
(A) input enhancement (B) greedy
(C) sorting (D) divide & conquer
Answer any FIVE Questions out
of EIGHT Questions.
Each question carries 16
marks.
Q.2 a. What is an algorithm? Explain different
properties of an algorithm. (8)
b. Explain various issues in study of algorithm.
Write an algorithm to find GCD of two numbers. (8)
Q.3 a. Explain the concept of asymptotic notations,
indicating normally used notations. (8)
b. Discuss whether the Travelling Sales Person problem can be
solved by exhaustive search method. (8)
Q.4 a. Describe a binary search algorithm and also
find the worst case time complexity. (8)
b. Write pseudocode for partition
algorithm. Apply this algorithms to
following set of data showing clearly each stage
5 3 1
9 8 2 4 7 (8)
Q.5 a. Differentiate between DFS & BFS. (8)
b. Write down algorithm for insertion sort. Compare its complexity with Bubble sort. (8)
Q.6 a. Explain how dynamic programming is used to
compute all pair shortest paths for a weighted digraph. (8)
b. With
the help of pseudocode, explain Warshall’s algorithm to find the transitive closure
of a directed graph. Apply it to the following adjacency matrix of the graph. (8)
a b c d
a 0 1 0 0
b 0 0 0 1
c 0 0 0 0
d
1 0 1 0
Q.7
a. What is a heap? Outline an algorithm to construct a heap. Derive
the efficiency class of this algorithm. (8)
b. Solve the
system by Gaussian elimination (8)
Q.8 a. Distinguish
between P, NP, and NP-complete problems. Give examples for each category. (8)
b. Explain the
concept of decision trees for sorting algorithms. (8)
Q.9 a. What is backtracking? Explain with the help
of an algorithm. (8)
b. With the help of state space tree, solve the
following instance of the knapsack problem by branch and bound algorithm. (8)
