Scribd
Upload
10 views2 pages

Question Paper Code:: Reg. No.

The document is a question paper for a M.Sc. degree examination in Software Systems. It contains 15 multiple choice and long answer questions about algorithms and data structures. Topics covered include time vs space complexity, asymptotic efficiency classes, greedy algorithms, graph traversal techniques, articulation points in graphs, backtracking algorithms, graph coloring problems, NP-hard vs NP-complete problems, and algorithms for shortest paths, minimum spanning trees, knapsack problems, and graph coloring. Students are required to answer all 20 short questions and choose one of two long answer questions for each of the 5 problems in Part B.

Uploaded by

surendraninfotech
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views2 pages

Question Paper Code:: Reg. No.

The document is a question paper for a M.Sc. degree examination in Software Systems. It contains 15 multiple choice and long answer questions about algorithms and data structures. Topics covered include time vs space complexity, asymptotic efficiency classes, greedy algorithms, graph traversal techniques, articulation points in graphs, backtracking algorithms, graph coloring problems, NP-hard vs NP-complete problems, and algorithms for shortest paths, minimum spanning trees, knapsack problems, and graph coloring. Students are required to answer all 20 short questions and choose one of two long answer questions for each of the 5 problems in Part B.

Uploaded by

surendraninfotech
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

*46122* Reg. No.

Question Paper Code : 46122

[Link]. (5 Years) DEGREE EXAMINATION, NOVEMBER/DECEMBER 2017


Elective
Software Systems
ESE 053 : DESIGN AND ANALYSIS OF ALGORITHMS
(Common to : [Link].-Software Engineering)
(Regulations 2010)

Time : Three Hours Maximum : 100 Marks

Answer ALL questions

PART A (102=20 Marks)


1. Differentiate time complexity from space complexity.
2. What are the basic Asymptotic Efficiency Classes ?
3. Give the characteristics of Greedy Algorithm.
4. Specify the conditions for Flow Shop Scheduling.
5. What are the various graph traversal techniques ?
6. Define articulation point.
7. Specify the factors influencing the efficiency of Backtracking Algorithm.
8. State the Graph Coloring problem.
9. Can a NP Hard problem be solved in determinist polynomial time ? How ?
10. Show the class hierarchy of P, NP and NP complete problems.

PART B (516=80 Marks)

11. a) i) Can selection be on O(n) worst case, if the size of the input is n. If so, how does
it be done ? Analyze your algorithm to guarantee the linear worst cost time. (11)
ii) Using iterative method, find the asymptotic value T(n) for (5)
(1) for n = 1
T(n) =
3T(n/4) + n for n > 1
(OR)
b) What is divide and conquer ? Explain with an example the merge sort algorithm. (16)
46122 *46122*

12. a) Describe with an example the Single Source Shortest Path Algorithm.
(OR)
b) Explain Multistage Graph and its traversal with example.

13. a) Write the Prims algorithm, find the minimum cost spanning tree for weighted
graph shown in Fig. 13(a). (16)

Fig. 13(a)
(OR)
b) i) For the graph, show in Fig. 13 b(i) draw the DFS and BFS. (10)

Fig. 13(b) (i)


ii) Find all articulation points for the graph shown in Fig. 13 b(i). (6)

14. a) i) Explain the algorithm for graph coloring problem with suitable example. (8)
ii) What do you mean by 0/1 Knapsack problem ? Explain. (8)
(OR)
b) i) Explain how backtracking works on a eight queen problem with a suitable
example. (8)
ii) Briefly discuss about branch and bound technique for problem solving. (8)

15. a) State and prove Cookes Theorem. (16)


(OR)
b) Describe the following in detail :
i) NP-Hard problem. (8)
ii) NP-Complete problem. (8)

You might also like