[go: up one dir, main page]
Scribd
Upload
13 views2 pages

Design and Analysis of Algorithms - R2013

This document outlines the examination structure for the B.Tech. IV-Semester Supplementary Examinations in Design and Analysis of Algorithms at Gayatri Vidya Parishad College of Engineering. It includes instructions for answering questions, a breakdown of topics covered in various units, and specific questions related to algorithm analysis, dynamic programming, and complexity classes. The exam is scheduled for April 24, 2019, with a maximum score of 70 marks.

Uploaded by

My Self
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
13 views2 pages

Design and Analysis of Algorithms - R2013

This document outlines the examination structure for the B.Tech. IV-Semester Supplementary Examinations in Design and Analysis of Algorithms at Gayatri Vidya Parishad College of Engineering. It includes instructions for answering questions, a breakdown of topics covered in various units, and specific questions related to algorithm analysis, dynamic programming, and complexity classes. The exam is scheduled for April 24, 2019, with a maximum score of 70 marks.

Uploaded by

My Self
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
You are on page 1/ 2

Course Code :13CT1108/ 2013 R-2013 Reg.

No :

GAYATRI VIDYA PARISHAD COLLEGE OF ENGINEERING (AUTONOMOUS)


Madhurawada, Visakhapatnam
Affiliated to JNT University – K, Kakinada
B.Tech. IV-Semester Supplementary Examinations, April– 2019
Design and Analysis of Algorithms
(Common to CSE & IT)

Date : 24-04-2019 Time : 3 Hours Max. Marks : 70


1. Answer ONE Question from each UNIT
2. All parts of a Question must be answered in one place to get valued.
3. All questions carry equal marks.

UNIT-I

1. a) In what way amortized analysis is used for performance analysis of algorithms? Explain. 7 Marks
b) Define Big O notation, Big omega and Theta notation. Depict the same graphically and 7 Marks
explain.
2. a) State the general plan for analyzing the time complexity of non-recursive algorithms and 7 Marks
explain with suitable example.
b) Explain the method of determining the complexity of a procedure by the step count approach. 7 Marks
Illustrate with an example.
UNIT-II
3. a) Derive the worst case analysis of merge sort using suitable illustrations. 7 Marks
b) Write a recursive algorithm for binary search and also bring out its efficiency. 7 Marks

4. Define Minimum cost spanning tree. Find the minimum cost spanning tree for the following graph by
14 Marks
using Prim’s and Krushkal’s algorithms.

Page 1 of 2
Course Code :13CT1108/ 2013 R-2013 Reg. No :

UNIT-III
5. a) Construct an optimal travelling sales person tour for the given adjacency matrix using Dynamic 7 Marks

0 10 9 3
Programming:

5 0 6 2

9 6 0 7
7 3 5 0
b) Solve the following instance of 0/1 Knapsack problem using Dynamic programming: 7 Marks
n = 3; (W1, W2, W3) = (3, 5, 7); (P1, P2, P3) = (3, 7, 12); M = 14.
6. a) Compute lengths of shortest paths between all pairs of nodes for the given adjacency matrix 7 Marks

0 6 13
using Dynamic programming:

8 0 4
5 4 0
7 Marks
b) Let the dimensions of matrices A,B,C,D respectively be 10X5, 5X15, 15X8, 8X20. Generate
matrix product chains that produces minimum number of scalar multiplications using dynamic
programming.
UNIT-IV
7. a) Relate Hamiltonian cycle with travelling sales person problem and also give the backtracking 7 Marks
solution that finds all Hamiltonian cycles for any directed or undirected graph.
b) Draw the portion of state space tree generated by recursive backtracking algorithm for sum of 7 Marks
subsets problem with an example.
8. a) Consider the travelling salesperson instance defined by the following cost matrix. Obtain the 7 Marks

∞ 7 3 12 8
reduced cost matrix and the portion of the state space tree that will be generated by LCBB.
 3 ∞ 6 14 9 
 
5 8 ∞ 6 18
9 3 5 ∞ 11
18 14 9 8 ∞ 
b) Explain the Graph – coloring problem. And draw the state space tree for m= 3 colors and n=4 7 Marks
vertices complete graph.
UNIT-V
9. Explain the following:
a. The Clique decision problem 5 Marks
b. Node Cover decision problem 5 Marks
c. The Chromatic number decision problem 4 Marks

10. Define P, NP, NP- Hard and NP- Complete classes of problems. 14 Marks

Page 2 of 2

You might also like