# 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.  

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

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.                                                                                                   

OR

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

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

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

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.                           

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.          

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?            

 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.    

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

Write a backtracking algorithm for m Graph coloring.                               

OR

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

SECTION – II

Q7) a) Differentiate between “polynomial” and “nondeterministically polynomial”.        

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

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

OR

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

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?                                                                                          

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

Q9) a) Write in brief about a parallel computational model.                                         

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

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

OR

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

b) Write and explain the Pointer Doubling algorithm.                      

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

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

OR

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

 Letter : D E G J O X Z Frequency : 10 12 9 7 18 5 2

Explain an image edge detection algorithm.

H