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

DAA First-Internal Question Paper (2018) 3.4

This document contains an exam on design and analysis of algorithms. It has two sections with 8 marks for short answer questions in Section A and 12 marks for longer answer questions in Section B. Section A asks students to define UNION and FIND operations, feasible solutions for the knapsack problem, and hashing. Section B asks students to explain heap sort, asymptotic notation, merge sort time complexity, and find a feasible solution for a scheduling problem with jobs and deadlines.

Uploaded by

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

DAA First-Internal Question Paper (2018) 3.4

This document contains an exam on design and analysis of algorithms. It has two sections with 8 marks for short answer questions in Section A and 12 marks for longer answer questions in Section B. Section A asks students to define UNION and FIND operations, feasible solutions for the knapsack problem, and hashing. Section B asks students to explain heap sort, asymptotic notation, merge sort time complexity, and find a feasible solution for a scheduling problem with jobs and deadlines.

Uploaded by

deccancollege
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
You are on page 1/ 2

Deccan College of Engineering and Technology Deccan College of Engineering and Technology

Darussalam, Nampally, Hyderabad Darussalam, Nampally, Hyderabad


B.E III/IV (CSE A & B) II Semester B.E III/IV (CSE A & B) II Semester
Internal Examination-I (2018) Internal Examination-I (2018)
Design & Analysis of Algorithm Design & Analysis of Algorithm
Section-A Section-A
Answer all the questions (4*2=8M) Answer all the questions (4*2=8M)
1. State about ‘UNION’ and ‘FIND’ operation. 1. State about ‘UNION’ and ‘FIND’ operation.
2. Define feasible solution w.r.t greedy knapsack problem. 2. Define feasible solution w.r.t greedy knapsack problem.
3. Define Hashing? 3. Define Hashing?
4. Write about Optimal storage on tapes. 4. Write about Optimal storage on tapes.
Section-B Section-B
Answer any two questions (2*6=12M) Answer any two questions (2*6=12M)
5. Explain step by step heap sort with example and write an 5. Explain step by step heap sort with example and write an
algorithm for Heap sort. algorithm for Heap sort.
6a) Explain about different Asymptotic Notation 6a) Explain about different Asymptotic Notation
b) find the time complexity of T(n) b) find the time complexity of T(n)
T(n) = T(n-1)+2 if n>2 T(n) = T(n-1)+2 if n>2
=1 if n = 0 =1 if n = 0
7. Write merge sort algorithm and derive its time complexity for 7. Write merge sort algorithm and derive its time complexity for
best & worst case. best & worst case.
8. find feasible solution for given jobs with deadlines n=7, 8. find feasible solution for given jobs with deadlines n=7,
(p1,p2,p3,p4,p5,p6,p7)=(3,5,20,18,1,6,30) (p1,p2,p3,p4,p5,p6,p7)=(3,5,20,18,1,6,30)
(d1,d2,d3,d4,d5,d6,d7)=(1,3,4,3,2,1,2) (d1,d2,d3,d4,d5,d6,d7)=(1,3,4,3,2,1,2)

***********

You might also like