Hyderabad Institute of Technology and Management
III B.Tech I Sem II Mid Term Examination, JAN – 2023
Design and Analysis of Algorithm
Objective Exam
Name: ____________________________________ Hall Ticket No. A
Answer All Questions. All Question Carry Equal Marks. Time: 20 Min. Marks. 10 M
I. Choose the correct Alternative:
Q. No. Question Marks CO’s PO’s
Dynamic programming problem has ______ time complexity [ ] CO3 PO1
1. a) Logarithmic b) polynomial c) quadratic d) exponential ½
In optimization procedure of dynamic programming problems is done with CO3 PO1
____
2. a) Seperability b) monotonicity c)implicit enumeration d) explicit ½
enumeration
For obtaining OBST using DP procedure _____ is the running time. [ ] CO3 PO1
3. ½
a) O(n) b) O(n2) c)O(n3) d) O(n logn)
_______ is shown in the knapsack problem. [ ] CO3 PO1
a) Overlapping subproblems. b) Optimal substructures c) Overlapping
4. subproblems and optimal substructure d) neither overlapping ½
subproblems nor optimal substructure.
Greedy solution exists for ______ CO3 PO1
a) No problems b) no optimization problem c) some problems d)all
5. problems ½
The greedy choices property is a globally optimal solution that can be found CO3 PO1
by a series of _______ improvements from a starting configuration.
6. a) Local b) global c) local or global d) local and global ½
Kruskal’s algorithm total running time is _______ where |E| is the no. of edges CO3 PO1
and n no. of nodes in a graph .
7. a) O(|E|) b) O(|E| log n) c) O(|E| log|E|) d) O(n log |E|) ½
The Halting problem is ________ CO3 PO1
8. a) Undecidable b) intractable c) NP-complete d) optimization ½
Decision problems are equivalent to ______________ CO3 PO1
a) Formulas in propositional logic b) assertions c) array manipulation
9. d) languages ½
What is the relation between P and NP? CO3 PO1
a) P=NP b) P > NP c) P < NP d) P ? NP, but no one knows whether
10. P = NP ½
________ is the advantage over greedy method in dynamic programming. CO4 PO2
a) Repeatedly solving subproblems
11. b) Not repeatedly solving subproblems ½
c) Generating one decision sequence as optional solution
d) Many decision sequences are generated
In a binary tree, the no.of terminal nodes are10, then the no.of nodes with CO4 PO2
children are ______
12. a) 9 b) 10 c)11 d)12 ½
For ________ minimum spanning tree ia an attribute. CO4 PO2
a) Array b) weighted graphs c) unweighted graphs d) sets of
13. points ½
A state space is ____________. CO4 PO2
a) Part of RAM b) one set of variable assignments c) a set of possible
14. arrangements of values d) a graph. ½
If M=15, n=4, P=(10,10,12,18) and W=(2,4,6,9) of 0/1 knapsack problem CO4 PO2
then the maximum profit is ________
15. a) 32 b) 38 c) 34 d) 36 ½
The knapsack problem searches _______ CO4 PO2
a) A tree b) a graph c) an array d) a state space
16. ½
In branch and bound terminology, a D-search like state space search will be CO4 PO2
called _______ search.
17. a) Random b) linear c) FIFO d) LIFO ½
The LC branch and bound search of a tree will begin with upper=_____ CO4 PO2
a) 1 b)0 c) 2 d) infinity
18. ½
NP- complete problems are believed to have _______ CO4 PO2
a) Polynomial time solutions b) no Polynomial time solutions c) no
19. exponential time solution d) no solution checkable in Polynomial ½
time
In the AND/OR graph, the solvable terminal nodes are represented by CO4 PO2
_______
20. a) Circles b) dots c) rectangles d) triangles ½
II. Fill in the blanks:
Q. No. Question Marks CO’s PO’s
An optimal solution is a feasible solution with _______ CO3 PO1
1. ½
The travelling sales person tour is a ________ in the graph. CO3 PO1
2. ½
The ______ problem is to determine a matrix A such that A(i, j) is the length CO3 PO1
3. of a shortest path from i to j. ½
CO3 PO1
4. For 0/1 knapsack algorithm space complexity is ______. ½
A _____ may be defined as connected graph without any cycle. CO3 PO1
5. ½
The one with maximum benefits from multiple choices is selected is the basic CO3 PO1
6. idea of ________ method. ½
Prim’s algorithm runs in ______ time, where n is the number of modes in the CO3 PO1
7. graph. ½
A _________ problem is to find shortest paths from a source vertex v to all CO3 PO1
8. other vertices in the graph. ½
A feasible solution that either maximizes or minimizes a given objective CO3 PO1
9. function is called an __________. ½
Job sequencing with deadlines total running time, in worst case, is _________ CO3 PO1
10. ½
The starting vertex of the path is referred to as the _________ and the last CO4 PO1
vertex is _________.
11. ½
_________ is the another name for adjacency matrix. CO4 PO2
12. ½
If adjacency matrix is used, then _______ is the time complexity of BFS CO4 PO2
algorithm.
13. ½
Problems that can be solved in _________ time are treated as easy problems. CO4 PO2
14. ½
NP stands for _________. CO4 PO2
15. ½
_________ theorem states that any problem is class up can be reduced to an CO4 PO2
16. instance of SAT in polynomial time. ½
The complexity of best algorithm knapsack problem is _________. CO4 PO2
17. ½
___________ is used by FIFO BB as an auxiliary data structure. CO4 PO2
18. ½
A travelling sales person tour is often called a _______ CO4 PO2
19. ½
______ has a finite state control , a two way infinite tape and a read write head CO4 PO2
20. ½
