DAA MID-1 IMP QUESTIONS

1.Define an algorithm?Describe the characteristics of an algorithm?

2.Define time and space complexity?with the help of mathematical formula by taking an example-

Calculate time and space req.of an algorithm?

3.Describe diff notations used to represent the complexities?

4.write an algorithm to find largest element in an array of n-elements and find its time complexity?

5.derive the complexity for general divide and conquer algorithm?

6.Explain strassen`s matrix multiplication concept? And also derive the time complexity for strassen`s algorithm?

7.Explain how a problem is solved using divide and conquer strategy?

8.Trace the quick sort algorithm to sort the list consists of elements {C,O,L,L,E,G,E} in an alphabetical order

9.a)Explain when the quick sort is preferred to an merge sort and viceversa

b)what is the principle of partioning in quick sort?give an example

10.Find the optimal solution to the knapsack instance

n=7 , m=15 , profits {p1,p2,p3,p4,p5,p6,p7}={10,5,15,7,6,18,3}

and weights {w1,w2,w3,w4,w5,w6,w7}={2,3,5,7,1,4,1}

11.Write an algorithm to find articulation point?

12.Write an algorithm to find collapsing rule?

13.solve the following recurrence relation

T(n)=a n=1

=2T(n/2) n>1

14.consider the following graph and find the shortest path as a vertex=’2’ as source

Fig: SARAJ SAHANI Page num:261 (a)

15.Assume that we have started with a forest of trees each having 1-node.Let ‘T’ be the tree with m-nodes created as a result of sequence of unions.each perform using weighted union .

Prove height of ‘T’ IS NO greater than (logn+1)

MP mid 1 IMP QUESTIONS

1.Block Diagram of 8085

2. Block Diagram of 8086

3.Min and Max modes of 8086 with timing diagram of read and write operations in MIN/MAX mode

4. a)What are the different types of assembler directives in 8086

b)What is the difference between 8085 and 8086

5.Explain briefly about 8255 PPI

6. ONE (1) PROGRAM

7.DMA

STM MID -1 IMPORTANT QUESTIONS

1. a) Differentiate the dichometrics

àFunction vs Structure

àDesigners vs Testers

b) Is complete testing possible

2. What are the consequences of bugs?

Present nightmare LIST.When to stop testing?

3.Write path testing criteria.How many types of loops are there? And discuss.

4.What is the test blindness?How many types are there?

Discuss present heuristic procedure for sensitizing paths?

5. Present in detail the transaction flow testing techniques?

6. What are nice and ugly domains? And explain their properties?

7.Trace the plan template using table for given example.

8.Write test cases for the following:

a)single loop min=0,max=n no excluded values

b)single loop min≠0

c)variable range 1-20 excluded values 7,8,9,10.

9.Discuss the following testing:

a)functional/structural

b) α/β

c)unit/integration

d)retest/regression

e)kiddle testing