[go: up one dir, main page]
Scribd
Upload
17 views3 pages

Design and Analysis of Algorithms

This document outlines the examination details for the Design and Analysis of Algorithms course at Manipal Institute of Technology, including instructions for candidates and a list of questions covering various algorithms and data structures. Students are required to answer any five full questions from the provided topics, which include Dijkstra's algorithm, Prim's algorithm, depth-first search, and dynamic programming. The exam is scheduled for December 9, 2006, with a maximum score of 50 marks.

Uploaded by

vikashkumar.singh.civ16
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
17 views3 pages

Design and Analysis of Algorithms

This document outlines the examination details for the Design and Analysis of Algorithms course at Manipal Institute of Technology, including instructions for candidates and a list of questions covering various algorithms and data structures. Students are required to answer any five full questions from the provided topics, which include Dijkstra's algorithm, Prim's algorithm, depth-first search, and dynamic programming. The exam is scheduled for December 9, 2006, with a maximum score of 50 marks.

Uploaded by

vikashkumar.singh.civ16
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/ 3

Reg.

No

Manipal Institute of Technology


(Constituent Institute of MAHE – Deemed University)
Manipal – 576 104

FIFTH SEMESTER B.E(IT) END SEMESTER EXAMINATIONS – NOV/DEC, 2006


SUBJECT:– DESIGN AND ANALYSIS OF ALGORITHM (ICT-309 )
(REVISED CREDIT SYSTEM)
09/12/2006 (2-5PM)
TIME: 3 HOURS MAX.MARKS: 50

Instructions to Candidates:

•Answer any 5 FULL questions.


•All questions carry equal marks.
•Missing data may be suitably assumed

1A. Write a C++ function for inserting an element into an sorted array and find its
asymptotic space and time complexity.
1B. Give dijkstrass algorithm for finding single source shortest path.
1C. Let G=(V,E) be a directed graph. Let cardinality of V is n and total number of
edges in the graph is e. Prove that
(i) Σ diin = Σdiout = e
(ii) 0 <= e <= n(n-1)
[5+3+2]
2A. Write a C++ function for recursive sequential search and find its asymptotic
time complexity for best, worst and average cases.

Page 1 of 3
2B. Give Prim’s algorithm for finding minimum cost spanning tree and trace the
algorithm for the graph whose cost adjacency matrix is given as follows.
0 20 ∞ ∞ ∞ 10 ∞
20 0 16 ∞ ∞ ∞ 14
∞ 16 0 12 ∞ ∞ ∞
∞ ∞ 12 0 22 ∞ 18
∞ ∞ ∞ 22 0 25 24
10 ∞ ∞ ∞ 25 0 10
∞ 14 ∞ 18 24 10 0

2C. Discuss the different ways used to store the adjacency matrix, for reducing the space
complexity.
[5+3+2]
3A. Write DFS algorithm and trace it for the graph whose adjacency matrix is given
as follows.
0 1 1 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 1 0 0 1 1 0 0 0
0 0 1 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0

3B. Using profit by density method, solve the following 0/1 Knapsack problem
N = 8 w = [ 100 200 50 90 150 50 20 80] C = 400
P = [25 22 30 20 40 50 50 60]
3C. Solve the following recurrence equation
t(n) = 10 t(n / 3) + 11n, n>=3 and a power of 3
[5+3+2]

Page 2 of 3
4A. Solve the following matrix multiplication chain problem using dynamic
programming
q = 5 r = (12, 4, 5, 10, 2, 3)
4B. Calculate time complexity of strassen’s matrix multiplication method.
4C. Write a short note of NP- complete and NP-hard problems.
[5+3+2]
5A. With suitable example explain Branch and bound least cost method for container
loading problem. Take n = 4 and make use of bounding function.
5B. Give an algorithm for quick sort and find its worst case time complexity.
5C. State and prove theta ratio theorem.
[5+3+2]
6A. With suitable example explain Back tracking method for max clique problem.
Take n = 4 and make use of bounding function.
6B. Find all pairs of shortest path using dynamic programming method for the graph
whose cost adjacency matrix is given as follows

0 7 1 3
7 0 ∞ 3
1 ∞ 0 1
3 3 1 0

6C. Write a C++ function for merge sort.


[5+3+2]

Page 3 of 3

You might also like