Design & Analysis of Algorithms UOS — University of Sargodha

University of Sargodha

Paper: Analysis of Algorithms

Total Marks: 50

Time Allowed: 120 min

Roll #

Note: Attempt all questions.

Problem

1.

Answer the following questions briefly. Give examples where necessary.

i. Differentiate between min heap and max heap. [2]

ii. Prim's algorithm for computing MST and Dijikstra's algorithm for computing

shortest paths are similar in design. T/F [1]

iii. Differentiate between D.P approach and greedy approach. [4]

iv. Write down the recursive solution for assembly line scheduling. [2]

v. All pair shortest path can be calculated using greedy approach. T/F [1]

Problem

2.

i. Run Prim's MST algorithm on the graph given below. Also find how many MSTs

are there in this graph. [5+2]

ii. Write down the procedure that finds out the optimal solution in knapsack

problem. [3]

Problem

3.

i. Write down the recursive solution for knapsack problem. [1.5]

ii. Write down the recursive solution for all pair shortest path problem [1.5]

iii. Write down the procedure of Min-Heapify. [3]

iv. Suppose that all characters in the pattern P are different. Show how to

accelerate Naïve String Matcher? [4]