PART A1) 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
