Scribd
Upload
7 views1 page

Algorithm Design and Analysis

This document is an examination paper for the course 'Algorithm Design and Analysis' with a total duration of 3 hours and a maximum score of 80 marks. It consists of two parts: Part A with 10 compulsory questions worth 2 marks each, and Part B with 10 questions where students must attempt 6 out of 10, each worth 10 marks. The paper covers various topics including sorting, data compression, dynamic programming, and NP-hard problems.

Uploaded by

Facebook
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
7 views1 page

Algorithm Design and Analysis

This document is an examination paper for the course 'Algorithm Design and Analysis' with a total duration of 3 hours and a maximum score of 80 marks. It consists of two parts: Part A with 10 compulsory questions worth 2 marks each, and Part B with 10 questions where students must attempt 6 out of 10, each worth 10 marks. The paper covers various topics including sorting, data compression, dynamic programming, and NP-hard problems.

Uploaded by

Facebook
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

Registration No.

:__________________
PNR No:: DEC508087
COURSE CODE : DECAP538
COURSE NAME : ALGORITHM DESIGN AND ANALYSIS
Time Allowed: 03:00 hrs [Link]: 80
1. This question paper is divided into two parts A and B.
2. Answer all the questions in serial order.
3. Part A contains 10 questions of 2 marks each. All questions are compulsory.
4. Part B contains 10 questions (Questions 2 to 11) of 10 marks each, attempt any 06 questions out of 10.
Attempt all parts of the selected question. Only first 06 attempted questions would be evaluated.
5. The student is required to attempt the question paper in English medium only.
6. Simple non programmable calculator is allowed.

PART A

Q1(a) Define sorting .

(b) Define feasible solution.

(c) State the principle of optimality .

(d) What is backtracking ?

(e) Define Lower bound in branch and bound ?

(f) Name two commonly used lossless compression algorithms other than Huffman coding.

(g) What is the lower bound on the worst-case running time of any sorting algorithm?

(h) What is the relationship between lower bounds and algorithm optimality?

(i) What is the difference between preemptive and non-preemptive scheduling?

(j) Explain the significance of Stephen Cook's theorem .

PART B

Q2 Discuss the significance of decision tree models in lower bound theory. How are decision trees
used to establish lower bounds for sorting algorithms?
Q3 Discuss the advantages and disadvantages of lossless and lossy data compression techniques.
Provide real-world examples where each type of compression is more suitable.
Q4 Describe the lower bound for inserting or deleting elements in a dynamically changing data
structure, such as a binary search tree.
Q5 Describe the First-Fit, Best-Fit, and Next-Fit heuristics for bin packing.
Q6 Explain the concept of dynamic programming . How does it differ from other problem-solving
techniques?
Q7 What are the key characteristics of a problem that can be solved using dynamic programming ?
Q8 Distinguish between prim's and Kruskal's algorithm.
Q9 Explain control abstraction of LC-branch and bound?
Q10 Define NP-hard problems and provide an example of a problem that is NP-hard. Explain why it is
considered NP-hard.
Q11 What do you mean by time and space complexity of an algorithm?

-- End of Question Paper --

Page 1 of 1

You might also like