# 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