Download AKTU B-Tech 5th Sem 2016-2017 Design And Analysis Of Algorithm Ncs 501 Question Paper

Download AKTU (Dr. A.P.J. Abdul Kalam Technical University (AKTU), formerly Uttar Pradesh Technical University (UPTU) B-Tech 5th Semester (Fifth Semester) 2016-2017 Design And Analysis Of Algorithm Ncs 501 Question Paper

Printed Pages - 3 NCS-50l
(Following Paper ID and Roll No. to be ?lled in your
'Answer Books)
Paper ll) : 2012264 Roll No.
B.TECH.
Regular Theory Examination (Odd Sem - V) 2016-17
DESIGNAND ANALYSIS OF ALGORITHM
Time : 3 Hours ' Max. Marks : 100
Section - A
1. Attempt all parts. All parts carry equal marks. Write
answer of each part in?short. (10X2=20)
a) List out the disadvantages of divide and conquer
algorithm.
b) What are the fundamental steps involved in
algorithmic problem solving?
c) Write recursive function to ?nd nth Fibonacci '
number.
d) De?ne Binary heap.
e) Brie?y explain the Prim?s algorithm.
f) De?ne principle of optimality.
501/11/2016/13260 (1) [P.T.O.

, NCS-SOl
g) Write the names of various design techniques of
algorithm.
h) Differences between branch & bound and
backtracking technique.
i) What is the running time complexity of 8 queen?s
problem?
j) De?ne P, NP and NP complete in decision problem.
Section - B
Attempt any ?ve questions from this section.
(5X10=50)
2. Explain the concepts of quick sort method and analyze
its complexity with suitable example.
3. Explain the concept of merge sort with example.
4. Insert the nodes 15, l3, l2, 16, 19,23, 5, 8 in empty Red
Black Tree ahd delete in the reverse order of insertion.
5. Write short note on Dijkstra ?s algorithm shortest paths -
Dijkstra?s algorithm shortest path problems.
6. Write pseudocode for 8 queen problem.
Write non-deterministic algorithm for sorting.
8. What is backtracking? Write general iterativealgorithm
for backtracking. '
9. Differentiate NP complete with NP hard.
501/11/2016/13260 (2)
NCS-501
Section-C
N ote: Attempt any 2 questions from this section.
10.
11.
12.
(2XI5=30) '
i) State Bellman ford algorithm.
ii) Consider following instance for simple knapsack
problem. F ind the solution using greedy method.
N=8
P= {11, 21, 31, 33, 43, 53, 55, 65}
W: {1, 11, 21, 23, 33, 43,45, 55}
M=110
What is travelling salesman problem? F ind the solution
of following travelling salesman problem using branch
and bound method.
Cost matrix =
'
IIIIEI
IIIEIII
Prove that three coloring problem is NP Complete.
501/11/2016/13260 (3)