[Nov-23]
GITAM (Deemed to be University)
[CSEN3001]
GST/GSS/GSB/GSHS Degree Examination
V SEMESTER
DESIGN AND ANALYSIS OF ALGORITHMS
(Effective for the admitted batch 2021-22)
Time: 2 Hours Max. Marks: 30
-----------------------------------------------------------------------------------------------------
Instructions: All parts of the unit must be answered in one place only.
--------------------------------------------------------------------------------------- -------------
Section-A
1. Answer all Questions: (51=5)
a) Define the Control Abstraction of Divide and Conquer.
b) State the Job – Sequencing Deadline Problem.
c) Define and explain the Principles of optimality.
d) What is Chromatic number? Draw the state space tree for
4 – coloring problem.
e) Describe the Least Cost – Search.
Section-B
Answer the following: (55=25)
UNIT-I
2. Illustrate the Quick sort algorithm with Divide and conquer strategy
for the following example. 35,26,12,04,05,16,28,54,24,16,9,65,72.
OR
3. Explain in detail about asymptotic notations with relevant diagrams
and examples.
UNIT-II
4. Apply the Dijkstra’s algorithm on the graph given below to find
single source shortest paths. [source: vertex 1]
OR
5. Solve the following graph using Kruskal’s algorithm to find the
Minimum cost spanning tree.
UNIT-III
6. Design a reliable three stage system with device types D1, D2 and
D3. The costs are $30, $15 and $10 respectively. The maximum cost
of the system is not to exceed $150. The reliability of each device
D1, D2 and D3 are 0.8, 0.9 and 0.7 respectively.
OR
7. Discuss the All-pairs shortest path problem for the given adjacent
matrix using Dynamic Programming.
UNIT-IV
8. Define the sum –of subsets problem. Find all sum of subsets for n=4,
(w1, w2, w3, w4) = (11, 13, 24, 7) and M=[Link] the portion of
the state space tree.
OR
9. Analyze whether the given graph is bi-connected or not using the
relevant procedure.
UNIT-V
10. Outline the procedure for solving the Travelling Salesperson
problem using Branch and bound technique.
OR
11. Illustrate the Branch and Bound solution for the 0/1 knapsack
problem instance, n=4; capacity, m=15;
Profit(p1,p2,p3,p4)=(10,10,12,18);
weight(w1,w2,w3,w4) =(2, 4, 6, 9).
Draw the portion of the state space tree and find optimal solution.
[IIIS/123]