Hall Ticket No Question Paper Code: AIT001
INSTITUTE OF AERONAUTICAL ENGINEERING
(Autonomous)
Four Year B.Tech III Semester End Examinations (Supplementary) January, 2019
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. Write down Divide and Conquer recursive merge sort algorithm and derive the time complexity
of this algorithm
Explain quicksort algorithm and simulate it for following data sequence: 3 5 9 7 1 4 6 8 2
2. Discuss the general plan for analyzing efficiency of non recursive and recursive algorithms?

When Strassen's method outperforms the traditional matrix multiplication method. How many
number of multiplication operations are required during multiplication of two matrices with size
of 32 x 32 in Stressen's method.
UNIT II
3. Explain the difference between depth first and breadth first searches?
Write an algorithm for searching an element using binary search method. Give an example?[7M]
4. Discuss iterative versions of inorder, preorder and post order traversal algorithms.
Calculate the time complexity for the following graph shown in Figure 1 using all pairs shortest
path algorithm and find the shortest paths between these three nodes.
Figure 1
Page 1 of 2
UNIT III
5. Describe the traveling salesman problem and discuss how to solve it using dynamic programming.

Give the control abstraction for subset paradigm using greedy method. Solve the job sequencing
with deadline problem using greedy method for the given data are
profits and are deadline respectively
6. Write down and explain the algorithm to solve all pair's shortest path problem
Solve the instance of the Knapsack problem by branch and bound algorithm for data given in
Table 1.
Table 1
Item Weight Value
1 10 $100
2 7 $63
3 8 $56
4 4 $12
UNIT IV
7. Explain the basic principle of backtracking and list the applications of backtracking.
Using backtracking enumerate how can you solve the following problems
8-Queen Hamilton circuit problem
8. Identify an example for the best case input for the branch and bound algorithm for the assignment
problem?
Solve the following instance of traveling sales person problem using Least Cost Branch and Bound
technique. 2
6666664
1 12 5 7
11 1 13 6
4 9 1 18
10 3 2 1
3
7777775
UNIT V
9. Prove the following:
CNF-SAT is NP complete ii) 3-SAT is in NP complete
iii) CIRCUIT-SAT is in NP
Give the non-deterministic algorithm for sorting elements in non decreasing order.
10. Explain how to implement an algorithm for Knapsack problem using NP-Hard approach.
Does boolean satisfiability problem satisfy the condition of NP complete? Prove it by
using Cook's theorem.