DAA II UNIT IMP QUESTIONS

PART A

1)  Waht is meant by optimal solution?

2)  State knapsack problem

3)  What is meant by divide and conquer strategy?

4)  Write down the recurrence equation for binary search algorithm

5)  Give two examples of real time problems that could be solved using greedy algorithm

6)  Compare feasible and optimal solution

7)  Give the time efficiency and drawback of merge sort algorithm

8)  Write recursive algorithm to perform binary search

9)  List out any two drawbacks of binary search algorithm

10)          Give the recurrence equation for the worst case behaviour of merge sort

11)          What is the time and space   complexity of container loading problem

12)          What is the time and space   complexity of knapsack problem

13)          What is meant by container loading problem

14)          What is the time efficiency class of greedy algorithm for  the knapsack problem? Justify ur answer

15)          Compare the time complexity of straight method with divide and conquer method of finding the maximum and minimum

16)          What are the merits of finding maximum and minimum using DAC?

17)          What are the merits and demerits of binary search algorithm?

18) What are the merits and demerits of merge sort?

19) Write the pseudo code for container loading algorithm

20) Define feasibility

Part B

1)  Write down the binary search algorithm and do the worst case analysis of the algorithm.  Derive any intermediate formula used

2)  Explain merge sort.  How do you analyse it using divide and conquer principle

3)  Explain merge sort with example

4)  Differentiate sequential from binary search technique

5)  Explain the working principle of merge sort with necessary algorithm, and simulate the algorithm with a non-trivial example

6)  Write down the binary search algorithm that searches for an element in a sorted list and analyse it for its worst case behaviour.  Derive all the intermediate results used

7)  Solve the following instance of the knapsack problem by greedy algorithm

               Item                           weight                             values

                    1                                 10                            100

                    2                                   7                              63

                    3                                   8                              56

                    4                                   4                              12

8)  Give an detailed note on divide and conquer techniques

9)  Write an algorithm for searching an element using binary search method.  Give an example

10) Discuss the use of greedy method in solving knapsack problem

11) A) write a pseudo code for divide and conquer algorithm for merging two sorted arrays into a single sorted one.  Explain with an example

b) set up an solve a recurrence relation for the number of key comparisons made by the above pseudo code.

12) How merge sort works for the following data set 100, 300.,150,450,250,350,200,400,500

13) Suppose you have 6 containers whose weights are 50, 10, 30,20,60,5 and ship whose capacity is 100. Find the optimal solution for the problem

14) Find an optimal solution to the knapsack instance n=7,m=15,(p1 ,p2)

    (w1,w2,w3,w4,w5,w6,w7)=(2,3,5,7,1,4,1)

             15) Find the maximum and minimum for the following set of elements using DAC technique.22

13

-5

-8

15

60

17

31

47