DAA Important Questions(For Semester Exam)

Below is the link to download the important questions(UQ) - DAA for each unit,

(for Office 2007 or higher - docx)

Click here

(for Office 97-2003 - doc - compatible mode)

Click here

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

 

DAA Solutions

1. Algorithm for nth number in Fibonacci series

Read n

f1 <- -1

f2 <-1

i <- 0

while i<=n

f3 <- f1+f2

f1 <- f2

f2 <- f3

i <-i + 1

End while

Display f3

3. Recursive function to find the factorial

FUNCTION FACTORIAL (N: INTEGER): INTEGER

BEGIN

(* TEST FOR STOPPING STATE *)

IF N <= 0 THEN

FACTORIAL := 1

ELSE

FACTORIAL := N * FACTORIAL(N - 1)

END

4. If lim f(n)/ g(n) = 0 then f(n) = O(g(n))

n->∞ = ∞ then f(n) = ω(g(n))

= constant then f(n) = θ(g(n))

Here

Lim n+n logn/ n.n^(1/2) if we apply L hoptial’s rule we get 0, therefore

n->∞

n+n log n = O (n.n^(1/2))

In this way computing the limit helps us in comparing the order of growth of 2 specific function.

5. Algorithm to find the number of binary digits

Recursive procedure:

Function F(X: integer)

{

If X= =0 or X= = 1 Then

Return 1;

Else

Return 1+ F(X/2);

}

End Function

Analysis:

T(n) = 1 + T(n/2)

Solving this recurrence equation by substitution method I get the roots as 1 and 1 and the efficiency class as O(log n)

If it is solved by Master method again we get it as O(log n)..

6. Linear search – In class notes

7. Algortihm for multiplication of two matrices

MATRIX-MULTIPLY(A, B)

1 n ← rows[A]

2 let C be an n × n matrix

3 for i ← 1 to n

4 do for j ← 1 to n

5 do ci j ← 0

6 for k ← 1 to n

7 do ci j ← ci j + aik · bkj

8 return C

8. substituting n = 2^k we get the roots as 2,2,1 and the time complexity as O(n log n)

9. There are two possible solutions, ω(n² ) or O(n³).

10. 1. Algorithm computes sum of squares of 1 to n numbers.

2. Basic operation(inside for loop)
3. basic operation executed 'n' times.
4. Efficiency class – O(n)

Disclaimer - The solutions here need not be right.

Download the Solution

DAA Important Questions

(1) (1)Write an algorithm for a given number n to generate the n’th number of the Fibonacci sequence.

-----May/June 2007

(2) (2) (A) what is pseudo code? Explain with an example [ 8 marks ]

(B) Find the complexity C(n) of the algorithm for the worst, best and average case

{ evaluate average case complexity for n=3, where n is the number of inputs } [ 8 marks ]

(3) Write a recursive function to find the factorial of a number n ---> 2 mark
April/May 2008

(4) How does computing the limit help in comparing the order of growth of 2 specific function?
Compare the orders of growth of n+nlogn and n.n^(1/2)
April/May 2008

(5) Write an algorithm to find the number of binary digits in n's binary representation and analyse the same
---> 8 mark

(6) write an algorithm to search linearly for an element X in an ordered list of ‘n’ entries. What is the best , worst, average case analysis and justify your answer?

(7) Write an algorithm that finds the product of 2 matrices

-->2marks Nov/Dec 2004

(8) Solve the following recursive relation

Q(n) = n-1 + 2Q(n/2) and given Q(1) =0. Assume that Q is defined for all powers of 2

(9) Find the order of n^2 + logn

->2marks April/May 2005

(10) Consider the following algorithm

Mystery(n)

//Input: A non-negative integer n

S<-0

For i<-1 to n do

s<- s + i*i

return s

a) What does this algorithm compute?

b) What is its basic operation?

c) How many times is the basic operation executed ?

d) What is the efficiency class of this algorithm ?

e) Suggest improvements for this algorithm and justify your improvement by analysing its efficiency

May/June2009

Asymptotic Notations

Topics covered in the file:

• Big-theta notation(Asymptotically tight bound)
  
• Big-Oh notation(O-notation) - Asymptotically upper bound
  
• Big-Omega notation - Asymptotically lower bound
• Properties(Transitivity, Reflexivity, Symmetry, Transpose symmetry)
• Standard notations(Floors and ceilings)

Click here to download....