and 5 others joined a min ago.
0
577views
Design and Analysis of Algorithms Question Paper - Dec 15 - Computer Science (Semester 5) - Jawaharlal Nehru Technological University (JNTUH)
1 Answer
0
8views
written 6.9 years ago by
teamques10
★ 70k
|
Design and Analysis of Algorithms - Dec 15
Computer Science (Semester 5)
Total marks: 80
Total time: 3 Hours
INSTRUCTIONS
(1) Answer any FIVE questions.
(2) All questions carry equal marks.
1.a.
Explain pseudo code conventions for writing an algorithm.
(7 marks)
00
1.b.
Write short notes on space complexity.
(7 marks)
00
2.a.
Explain in detail about spanning trees and related algorithms.
(7 marks)
00
2.b.
Explain the following fundamental operations on sets:
(7 marks)
00
- FIND.
- DELETE.
- MIN.
- INSERT.
3.a.
Write an algorithm to sort N numbers in ascending order using merge sort.
(7 marks)
00
3.b.
Compute the time complexity for Merge sort.
(7 marks)
00
4.a.
Prove that the Kruskal algorithm generates a minimum cost spanning tree for every connected undirected graph G.
(7 marks)
00
4.b.
Write an algorithm to find minimum cost spanning tree by using prim’s technique
(7 marks)
00
5.a.
Explain the traveling sales person problem and also analyze its time complexity.
(7 marks)
00
5.b.
Explain the 0/1 knapsack problem.
(57 marks)
00
6.a.
Derive the Bounding functions of sum of subsets problem and write the algorithm for the same.
(7 marks)
00
6.b.
Define the following terms: live node, E
-node, dead node.
(7 marks)
00
7.a.
Solve the traveling sales man problem for the following graph by using branch and bound.
(14 marks)
00
8.a.
What is meant by Halting problem? Explain with an example.
(7 marks)
00
8.b.
Prove that CNF satisfiability $\alpha$ AND/OR graph decision problem.
(7 marks)
00
ADD COMMENT
EDIT
Please log in to add an answer.