Hall Ticket No Question Paper Code: AIT001
INSTITUTE OF AERONAUTICAL ENGINEERING
(Autonomous)
Four Year B.Tech III Semester End Examinations (Regular) November, 2018
Regulation: IARE R16
DESIGN AND ANALYSIS OF ALGORITHMS
Time: 3 Hours (Common to CSE IT) Max Marks: 70
Answer ONE Question from each Unit
All Questions Carry Equal Marks
All parts of the question must be answered in one place only
UNIT I
1. Formulate the order of growth? Compare the order of growth and 2n.
Write an algorithm to find mean and variance of an array perform best, worst and average case
complexity, defining the notations used for each type of analysis.
2. Describe briefly the notations of complexity of an algorithm.
Discuss how much the function value will change if the sequential search function's argument is
increased.
UNIT II
3. Describe non recursive binary tree traversal algorithm with suitable example.
What approach would you use for Depth first Search? Find the solution for the following graph
given.
Figure 1
4. Explain the algorithm for maximum and minimum numbers in an array.
Give a suitable example and explain the breadth first search and depth first search algorithm.

Page 1 of 3
UNIT III
5. Consider that there are three items. Weight and Profit value of each item is as given below in
Table 1. Also W=20 obtain the solution for the above given knapsack problem using Greedy
Method.
Table 1
I Wi Pi
1 18 30
2 15 21
3 10 18
Elucidate the minimum spanning tree with the help of prim's algorithm and show the result for
the given graph shown in Figure 2
Figure 2
6. Compare between Prim's and Kruskal's algorithm and identify the time complexity of those
algorithms.
Develop an algorithm for memory function knapsack problem.
UNIT IV
7. Generate all permutations of 4 and d=9 by backtracking.
Explain subset-sum problem and discuss the possible solution strategies using backtracking.

Page 2 of 3
8. Write and explain the techniques in branch and bound method.
Assume 4 cities which are represented by a fully connected graph. The following
Table 2 represent the pheromone levels on each edge of the graph and the distances between
each city (assume the pheromone levels and distances are symmetric). Assume an ant started its
journey at city A and has travelled to city C. Calculate the following
What is the probability that the ant will travel to city
ii) What is the probability that the ant will travel to city
iii) What is the probability that the ant will travel to city
Assume alpha and beta are set to 1.
Table 2
Pheromone Levels Distances
A B C D A B C D
A A
B 0.25 B 12
C 0.11 0.98 C 10 6
D 0.34 0.54 0.67 D 8 15 3
UNIT V
9. Explain how to implement an algorithm for Cook's theorem.
Using an example, design and prove that satisfiability of Boolean formula in 3-conjunctive normal
form I NP- complete?
10. Show that the Hamiltonian path problem reduces to the Hamiltonian circuit problem and vice
versa.
Elaborate the Non Deterministic Algorithm with example.