# Pune University BE CSE Design and Analysis of Algorithms Question Papers

**B.E. (Computer Engineering) DESIGN AND ANALYSIS OF ALGORITHMS**

**(2008 Pattern) (Sem. – I)**

Time: 3 Hours] [Max. Marks :100

Instructions to the candidates:

** 1) **Answer 3 questions from Section -1 and 3 questions from Section – II.

** 2) **Answers to the two sections should be written in separate books.

** 3) **Neat diagrams must be drawn wherever necessary.

** 4) **Figures to the right indicate full marks.

SECTION – I

Q1) a) Define asymptotic notations. Explain their significance in analyzing algorithms. [5]

b) Write the recurrence relation for quick sort. Compare its time complexity with brute force sorts. [3]

c) Explain general strategy of Greedy Method with the help of its control abstraction for the subset paradigm. Write an algorithm which uses this strategy for solving the Knapsack problem. [10]

OR

Q2) a) Write a note on Mathematical Induction and how it can be used to prove that an algorithm is correct. [5]

b) What is divide and conquer strategy? Write an algorithm for Merge Sort. State its time complexity. [6]

c) Explain the Greedy Kruskal’s minimum spanning tree. Compare this with Greedy Prim’s method. [7]

Q3) a) A problem of allocating n units of resources to r projects is given. The net profit N(i, j) is obtained when j, 0 < = j < = n, units of the resource are allocated to project i. For a maximum total net profit the resources must be optimally distributed to the r projects. Formulate this problem as an r + 1 stage graph problem. [6]

b) What is the Optimal Binary Search Tree problem? Explain how principal of optimality holds for this problem. Also explain how it is solved using dynamic programming. [10]

OR

For a directed graph the edge length matrix is given below. Solve the Travelling Salesperson Problem for this 4 city graph using Dynamic Programming method. What will be the time complexity for an n city TSP problem solved using this method? [7]

0 |
9 |
8 |
8 |

12 |
0 |
13 |
6 |

10 |
9 |
0 |
5 |

20 |
15 |
10 |
0 |

What is the Flow Shop Scheduling problem? Explain how principal of optimality holds for this problem. Also explain how it is solved using dynamic programming. [9]

Explain the difference between FIFO and LC Branch and Bound solution to 0/1 Knapsack. [10]

Write a backtracking algorithm for m Graph coloring. [6]

OR

Compare the Backtracking method with a depth first search technique. How is Hamiltonian Cycles problem solved using Backtracking? [8] Write the control abstraction for LC-Search. Explain how Traveling Salesperson problem is solved using LCBB. [8]

SECTION – II

Q7) a) Differentiate between “polynomial” and “nondeterministically polynomial”. [2]

b) What is meant by a problem “reducing to” another problem? Prove that the clique decision problem reduces to node cover decision problem. [8]

c) Show that the sum of subsets problem is NP-Hard, given that Exact cover problem is NP-Hard. [7]

OR

Q8) a) State Cook’s Theorem after explaining what is meant by P, NP and SAT problem. [4]

b) Prove that Satisfiability (with at most three literals per clause) reduces to chromatic number decision problem (CNDP). State what more is required to prove that CNDP is NP-Complete? [8]

c) Show that the Partition problem reduces to minimum finish time nonpreemptive schedule. [5]

Q9) a) Write in brief about a parallel computational model. [4]

b) Explain the prefix computation problem encountered in parallel solutions to problems. [6]

c) Write the Odd-even Merge algorithm and explain it with an example. [7]

OR

Q10)a) Explain how graph problems can be solved on parallel processors. [10]

b) Write and explain the Pointer Doubling algorithm. [7]

Q11)a) What is meant by heuristic algorithms? Discuss any one heuristic search algorithm. [8]

b) Explain how Huffman’s technique is used for data coding. [8]

OR

Construct an optimal binary prefix code for the letters given below using Huffman’s algorithm. [4]

Letter : |
D |
E |
G |
J |
O |
X |
Z |

Frequency : |
10 |
12 |
9 |
7 |
18 |
5 |
2 |

Explain an image edge detection algorithm.

H