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

DAA (5th) May2019

This document contains instructions for a 3 hour exam on the design and analysis of algorithms. It has 3 sections with a total of 18 multiple choice and written response questions. Section A contains 10 short 2 mark questions. Section B has 5 longer 5 mark questions and students must answer 4 of them. Section C contains 2 10 mark questions that students must answer. The questions cover topics like algorithm definitions, asymptotic notation, sorting algorithms, graph algorithms and complexity classes.

Uploaded by

NitinPandey
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
105 views2 pages

DAA (5th) May2019

This document contains instructions for a 3 hour exam on the design and analysis of algorithms. It has 3 sections with a total of 18 multiple choice and written response questions. Section A contains 10 short 2 mark questions. Section B has 5 longer 5 mark questions and students must answer 4 of them. Section C contains 2 10 mark questions that students must answer. The questions cover topics like algorithm definitions, asymptotic notation, sorting algorithms, graph algorithms and complexity classes.

Uploaded by

NitinPandey
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

Roll No. Total No.

of Pages : 02
Total No. of Questions : 18
B.Tech.(CSE) (2011 Onwards) (Sem.–5)
DESIGN & ANALYSIS OF ALGORITHMS
Subject Code : BTCS-503
M.Code : 70536
Time : 3 Hrs. Max. Marks : 60

INSTRUCTION TO CANDIDATES :
1. SECTION-A is COMPULSORY consisting of TEN questions carrying T WO marks
each.
2. SECTION-B contains FIVE questions carrying FIVE marks each and students
have to attempt any FOUR questions.
3. SECTION-C contains T HREE questions carrying T EN marks each and students
have to attempt any T WO questions.

SECTION-A

Answer the following questions :


o m
1. What is an algorithm? .r c
p e m
2. If f(n) = n! and g(n) = 2n, indicate whether f = 0(g), or f = (g), or both (f = (g)).

a o
r p
3. What do you mean by dynamic programming?
.r c
b
4. State the time complexity of Bubble sort.

p e
a
5. Explain the applications of depth first search algorithm.

p
6. Describe asymptotic notation.
b r
7. What is order statistics?

8. What do you mean by randomization?

9. What is convex hulls?

10. Explain the time complexity of binary search.

1 | M-70536 (S2)-522
SECTION-B
11. Take the following list of functions and arrange them in ascending order of growth rate.
That is, if function g(n) immediately follows function f(n) in your list, then it should be the
case that f(n) is O(g(n)).
f1(n) = n2.5, f 2(n) = √2n, f3(n) = n + 10, f4(n) = 10n, f5(n) = 100n, and f6(n) = n2 log n
12. Sort the list 415, 213, 700, 515, 712, 715 using Merge sort algorithm. Also explain the time
complexity of merge sort algorithm.
13. Explain breadth first search algorithm with an example.
14. Write a short note on approximation algorithms.
15. Explain the classes of P and NP.

SECTION-C
16. Explain Strassen's algorithm for matrix multiplication with the help of an example.
17. Write a short note for the following :
o m
a. Divide and conquer technique
.r c
b. Greedy algorithm
p e m
18.
a
a. Why do we perform topological sorts only on DAGs? Explain.
o
r p .r c
b. Using Dijkstra’s algorithm find the shortest path from A to D for the following graph.

b B
7

p e C
3

pa
2
2 3

br
A E 2 D
F
6 2 2
1
G H
4

Fig.1

NOTE : Disclosure of Identity by writing Mobile No. or Making of passing request on any
page of Answer Sheet will lead to UMC against the Student.

2 | M-70536 (S2)-522

You might also like