[go: up one dir, main page]
Scribd
Upload
237 views3 pages

Daa Question Paper

This document contains a 20 question multiple choice exam on algorithms and data structures concepts like knapsack problem, spanning trees, single source shortest path problem, and complexity analysis notations like Big-O and Theta. It also contains short answer questions asking to explain algorithms like merge sort, knapsack problem using greedy approach, Dijkstra's algorithm for single source shortest path, Strassen's matrix multiplication, and all pairs shortest path.

Uploaded by

varsha reddy
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
237 views3 pages

Daa Question Paper

This document contains a 20 question multiple choice exam on algorithms and data structures concepts like knapsack problem, spanning trees, single source shortest path problem, and complexity analysis notations like Big-O and Theta. It also contains short answer questions asking to explain algorithms like merge sort, knapsack problem using greedy approach, Dijkstra's algorithm for single source shortest path, Strassen's matrix multiplication, and all pairs shortest path.

Uploaded by

varsha reddy
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

SRINIVASA INSTITUTE OF TECHNOLOGY AND SCIENCE, KADAPA

III B.Tech II SEM - I MID Examination March-2020


Branch: CSE Date: 0-03-2020( )
Sub: DAA
Reg. No:
1.

Time: 20min. Max.Marks:10 Sign of Invigilator

Choose the correct answer


1.In Knapsack problem, the optimized function is_______ profit. [ ]
A)Minimized B)Maximized C)Both D)None
2. Feasible solution subset consist of [ ]
A)input satisfying constraint B)input dissatisfying the constraint C)optimal solutions D)none

3.Spanning tree of G should have n vertices ___ edges. [ ]


A)n-2 B)n! C)n-1 D)n*n
4. _____ problem staring with one vertex and traverse the all vertices and return to [ ]
Same vetex.
A) 0/1 Knapsack problem B)Travelling sales man C)Single source shortest path D)ALL
5.In optimal storage on tapes the programs are stored in_____ permutations. [ ]
A)n-2 B)n! C)n-1 D)n*n
6. In _______ method based on rule principle of optimality. [ ]
A) A)Back tracking B)Dynamic C)Divide-and-conquer D)Greedy
7._____ formula is used to calculate no.of spanning trees of Connected graph. [ ]
n-2
A)n! B)n C)n D)n*n
8.The computing time of Kruskal’s Algorithm is__ [ ]
A)O(E log) B)O(nm) C)O(E logn) D)O(E)
9. ____Tree should not a allow the cycles . [ ]
A)Binary B)Spanning C)B-tree D)None
10. The Recurrence relation isT(n)= 9T(n/3)+n then what is the time complexity. [ ]
A)O(n3) B)O(n logn) C)O(logn) D) O(n2)

11. Each step of the algorithm must be clear and Unambiguous. [ ]


A)Finiteness B)Effectiveness C)Definiteness D)Generality
12.______ notation is used to find the lower bound of a function f(n) [ ]
A)Big-oh B)Theta C)Omega D)All

13. An algorithm call itself is called ______________ [ ]


A)Indirect recursive B)Direct recursive C)Both A& B D)ALL
14.The best case time complexity of linear search. [ ]
A)O(n logn) B)O(1) C)O(n) D)O(logn)
15.___notation is used to find the run time between lower bound to upper bound. [ ]
A)Big-oh B)Theta C)Omega D)All
16 .In theta notation ____ constraint to check f(n)=theta(g(n). [ ]
A )c1g(n)>=g(n)>=c2g(n) B)f(n) <= c*g(n) C)c1g(n)<=g(n)<=c2g(n)D)f(n) ==c*g(n)
3
17.In Big oh what is the meaning of O(n ) [ ]
A) constant B)Linear C)Cubic D)Quadratic

18. The worst case complexity of quick sort stands when the elements in the array are [ ]
A) increasing order B ) random order C) decreasing order D)ALL

19. ._____is the process of executing the correct program on data sets and measuring the [ ]
Time and space it takes to compute the results.
A)Profiling B)Analysis C)testing D)Debugging
20.In space complexity the Sp denotes [ ]
A)constants B)instance characteristics C)characteristics D)None

SRINIVASA INSTITUTE OF TECHNOLOGY AND SCIENCE, KADAPA


III B.Tech II SEM - I MID Examination March-2020
Branch: CSE Sub: DAA
Time: 90min. Date: 0-03-2020(N) Max.Marks:30
Note: Answer any three of the following questions

1. Write about Merge sort algorithm using example.


(9,2,5,4,6,8,7,3)
2. Explain Knapsack problem by using Greedy approach with Example?
(p1,p2,p3)=(90,100,50) (w1,w2,w3)=(6,8,3) and m=14
3. Explain Single source shortest path problem in detail using dijikstras algorithm?
4. Explain in detail about the Stressen’s matrix multiplication using example?
A= 2 4 B= 2 7
5 6 8 2

5.Explain in detail about all pairs shortest path using example?

You might also like