MORE IN Design & Analysis of Algorithms
SPPU Computer Engineering (Semester 7)
Design & Analysis of Algorithms
December 2016
Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

Solve any one question.Q7(a,b,c) Q2(a,b)
1(a) Which Algorithm strategy used by quick sort? Write recurrence relation for quick sort & solve it.
6 M
1(b) Compare following Algorithm strategies
i) Divide & Conquer
iii) Dynamic programming
6 M
1(c) Solve following job sequencing problem using G ready apporach.
N=7,
Profit (P1....P7)=(3,
5,
20,
18,
1,
6,
3,
4,
2,
3,
2,
1)
8 M

2(a) Explain the following for dynamic programming.
i) Principle of optionalizing with example
ii) Matrix multiplication problem
12 M
2(b) Given n=G and weight (w1,
w2,
w3,
w4,
w5) = (7,
11,
13,
24,
10). Find all subset whose sum is 41 using sum of subsets Algorithm.
8 M

Solve any one question.Q3(a,b) Q4(a,b)
3(a) Which are different approaches of writing Randomized Algorithm? Write Randomized sort Algorithm.
8 M
3(b) Explain following with relations with each other.
i) Polynominal Algorithms
ii) Non-Polynomial Hard Algorithms
iii) Non-polynomial complete Algorithms
8 M

4(a) What 0-1 Knap sack problem? Explain the Algorithm as deterministic & non-determinstic versions.
10 M
4(b) What NP-complete Algorithm? How do we prove that algorithm is NP complier? (Give example)
6 M

Solve any one question.Q5(a,b) Q6(a,b)
5(a) What is mean by parallel Algorithms? What are way by which we can achieve parallelism is Algorithm?
6 M
5(b) Explain sequential & parallel Algorithm for merge sort for the following arrays. A[8]=[ 11,
4,
30,
11,
20,
5,
8,
2]
10 M

6(a) How parallel Algorithm can be used to solve graph problem?
8 M
6(b) How complete binary tree is useful for parallel algorithms? Give any example you are familiar with.
8 M

Solve any one question.Q7(a,b) Q8(a,b)
7(a) What is clustering ? How clustering is used in data management? Explain with any Algorithm used in clustering.
12 M
7(b) Explain various elements of IOT (Internet of things).
6 M

8(a) State & explain different software engineering algorithms.
9 M
8(b) Write KMP algorithm for string matching Algorithm.
9 M

More question papers from Design & Analysis of Algorithms