ANALYSIS & DESIGEN OF ALGORITHM
Analysis and Design of Algorithm
1. Which symbol is used for assignment in algorithm
a. ->
b. =
c. <-
d. =>
Ans C
2. An instance of a problem is also called a _________.
a. Question
b. Equation
c. Algorithm
d. None of the above
Ans A
3. An algorithm has zero or more but only ________________ number of inputs
a. Infinite
b. Finite
c. N
d. 8
Ans B
4. When the sequence of execution of instruction is to be the same as the sequence in which instructions are written in program text, the control mechanism is called_______
a. Direct Sequencing
b. Serial Sequencing
c. Parallel Sequencing
d. None of the above
Ans A
5. A function f: X->Y is said to ________ if to every element of, the co domain of there is an element xЄX such that f(x)=y
a. On to
b. In to
c. One-One
d. One to One`
Ans A
6. For all real numbers x the exponential function ex is defined as
a. 1 - x +x2/2!-x3/3! +x4/4! …………..
b. 1 - x -x2/2!-x3/3!-x4/4! …………..
c. 1 + x +x2/2!+x3/3! +x4/4! …………..
d. None of the above
Ans C
7. The f(x) is said to be O (g(x)) if there exist two positive integers/ real number constant C and k such that ________for x≥k
a. f(x)≤c(g(x)
b. f(x)≥c(g(x)
c. f(x)=C(g(x)
d. C1(g(x))≤ f(x) ≤C2(g(x))
Ans A
8. The f(x) is said to be Ω(g(x)) if there exist two positive integers/ real number constant C and k such that ________for x≥k
a. f(x)≤c(g(x)
b. f(x)≥c(g(x)
c. f(x)=C(g(x)
d. C1(g(x))≤ f(x) ≤C2(g(x))
Ans B
9. The f(x) is said to be Θ(g(x)) if there exist two positive integers/ real number constant C and k such that ________for x≥k
a. f(x)≤c(g(x)
b. f(x)≥c(g(x)
c. f(x)=C(g(x)
d. C1(g(x))≤ f(x) ≤C2(g(x))
Ans D
10. For the function defined by f(x)=2x3+ 3x2 +1
a. F(x)=O(x3)
b. F(x)=O(x2)
c. F(x)=O(x)
d. None of the above
Ans A
11. For the function defined by f(x)=2x3+ 3x2 +1 and h(x)= 2x3- 3x2 +1
a. f(x)= Ω(x4)
b. f(x)= Ω(x2)
c. f(x)= Ω(x3)
d. None of the above
Ans C
12. For any two functions f(x) and g(x), f(x)= Θ(g(x)) if and only if f(x)=O(g(x)) where f(x) and g(x) are ________
a. Negative
b. Non negative
c. Zero
d. None of the above
Ans B
13. A tree is called a binary tree, if it is either ___________, or it consist of a node called _______ together with two binary tree called the _________ sub tree or ______ sub tree.s
a. Full, Leaf, Left, Root
b. Full, Root, Left, Right
c. Empty, Root, Left, right
d. Empty, Leaf, Left, right
Ans C
14. Choose which one of the sorting technique comes under the “divide & conquer” technique of sorting?
a. Bubble sort, selection sort, heap sort, shell sort
b. Merge sort, quick sort
c. Merge sort, quick sort, Bubble sort, selections sort
d. Heap sort, shell sort, merge sort
Ans:B
15. A search tree can be used as a dictionary and as a ____________.
a. stack
b. priority queue
c. splay tree
d. red-black tree
Ans B
16. The worst case running time for most search tree operations is _______ to the height of tree
a. Inverse proportional
b. Equal
c. Proportional
d. Not equal
Ans C
17. In pre-order walk the sequence is
a. Root, Left, Right
b. Left, Root, Right
c. Left, Right, Root
d. Right, Left, Root
Ans A
18. In post-order walk the sequence is
a. Root, Left, Right
b. Left, Root, Right
c. Left, Right, Root
d. Right, Left, Root
Ans C
19. In IN -order walk the sequence is
a. Root, Left, Right
b. Left, Root, Right
c. Left, Right, Root
d. Right, Left, Root
Ans B
20. Using Divide and conquer technique in the Integer Multiplication the
Input of n-digit decimal numbers x represented as
a. x= xn-1xn-2xn-3………….x1x0
b. x= xn-1+xn-2+xn-3………….+x1x0
c. x= xn+1xn+2xn+3………….x2x1
d. x= x0x1x2………….xn+2xn+1
Ans A
21. Using Divide and conquer technique in the Integer Multiplication the
Output of n-digit decimal numbers z represented as
a. z= zn-1zn-2zn-3………….z1z0
b. z= z2n-1z2n-2z2n-3………….z1z0
c. z= z2n+1z2n+2z2n+3………….z2n
d. z= zn-1zn-2zn-3………….z1z0
Ans B
22. In the following diagram which of the following is performed
|
P |
|
X |
|
A |
|
B |
|
C |
|
X |
|
P |
|
C |
|
BB |
|
A |
a. Zig step
b. Zag step
c. Zig-Zag step
d. Zag-Zig step
Ans C
23. This sort runs linear time when input is drawn from a uniform distribution
a. Selection Sort
b. Bucket Sort
c. Heap sort
d. Shell sort
Ans B
24. ________________is search strategy in which the examination of a given vertex u, is delayed when a new vertex say v is reached and examination of v is displayed when new vertex say w is reached and so on.
a. Breadth First Search
b. Height First search
c. Length First Search
d. Depth first search
Ans D
25. Attaching some extra information tot eh problem space that can be used afterwards to fasten the process of finding the solution of each of these situations. This is known as ______________
a. Preconditioning
b. Post conditioning
c. Conditioning
d. None of the above
Ans A
26. In a directed graph vertex ‘v’ is ________________ to vertex ‘u’ if there is a directed edge from u to v
a. Incident
b. Parallel
c. Adjacent
d. None of the above
Ans C
27. ______________ discovers all vertices adjacent to a given vertex before moving to the vertices far ahead in the search graph
a. Breadth First Search
b. Best First search
c. Length First Search
d. Depth first search
Ans A
28. The best first search algorithm belongs to a branch of search algorithms known as _______________ search algorithms.
a. Knowledge
b. Heuristic
c. Binary
d. None of the above
Ans B
29. ________of a graph can be viewed as an ordering of its vertices along a horizontal line so that all directed edges go in one direction
a. Linear Sort
b. Selection Sort
c. Heap Sort
d. Topological sort
Ans D
30. The components of a globally optimum solution must themselves be optimal. This is given by the principle____
a. Dynamic Control Principle
b. Optimality Principle
c. Complexity Principle
d. None of the above
Ans B
31. A_____ of a weighted connected graph is its spanning tree of the smallest weight, where of a tree is defined as the sum of the weights on all its edges.
a. Spanning Tree
b. Maximum Spanning Tree
c. Minimum Spanning Tree
d. None of the above
Ans C
32. In ____________ method, we stress on the choice of edges of minimum weight from amongst all the available edges subject to the condition that chosen edges do not form a cycle.
a. Kruskal Algorithm
b. Prim’s Algorithm
c. Dijkastra Algorithm
d. None of the above
Ans A
33. If the word zzz is called c and the word zz is called d then the word formed by concatenating c and d is
a. zzzzz
b. zzz+zz
c. zzz-zz
d. zzz.zz
Ans A
34. If L= { aa, ab, ba, bb}, then the corresponding regular expression is
a. aaabbabb
b. aa+ab+ba+bb
c. aa-ab-ba-bb
d. None of the above
Ans B
35. A spanning tree of a connected graph , say G=(V<E) with V as set of vertices and E as set of edges, is its connected ___________________ that contains all the vertices of the graph.
a. Acyclic subgraph
b. Cyclic graph
c. Cyclic subgraph
d. Acyclic graph
Ans A
36. A _______________ G = (V(G),E(G)) where V(G) denotes the set of vertices of G and E(G) the set of directed edges, also called arcs, of G.
a. Graph
b. Trigraph
c. Digraph
d. None of the above
Ans C
37. A Turing machine is a sixtuple of the form:
a. (Q,∑,Γ,δ,q0, h)
b. (Q,∑,Γ,k,q0, h)
c. (Q,Ơ,Γ,δ,q0, h)
d. (Q,∑,Γ,δ,q0, H)
Ans A
38. A Transition diagram of the next – move function ________of a TM is a graphical representation consisting of a finite number of nodes and labeled arcs between the nodes.
a. Γ
b. γ
c. Θ
d. Μ
Ans B
39. A __________________________: is a polynomial time algorithm, which constructs the instances of a problem P2 from the instances of some other problem P1.
a. NP- Hard Problem
b. NP- Complete Problem
c. Polynomial- time reduction
d. None of the above
Ans: C
40. _____ denotes the class of all problems , for ach of which there is at least one known polynomial time Deterministic TM solving it.
a. PROB
b. e
c. t
d. P
Ans D
2-Marks
41. True/False
- Each of the floor function and ceiling function is a monotonically increasing function.
- Each of the floor function and ceiling function is strictly monotonically increasing function
- T, T
- T, F
- F, T
- F, F
Ans B
42. _______ function maps each real number x to the integer, which is________ of all integers less than or equal to x
a. Ceiling, Greatest
b. Floor, smallest
c. Ceiling, smallest
d. Floor, Greatest
Ans D
43. For n, a natural number and real numbers a, b and c all greater than 0, which of the following is true
- log a(bc)=loga b+ loga c
- loga(bn)=n log a b
- logba=logab
- loga(1/b)=loga(-b)
- loga(b)= logba
- alogbc=clogba
- All true
- All false
- 1, 3, 5
- 1,2,3,6
Ans D
44. There are _______- approach for determining complexity for executing an algorithm viz.__________
a. One, Empirical
b. Two, Empirical, Theoretical
c. Two, Empirical, Practical
d. Three, Empirical, Theoretical, Practical
Ans D
45. The ________ resources taken into consideration for efficiency measures, are ____________
a. One, Time
b. Two, Time & Space
c. Two, Time & Speed
d. Three, Time, Space & Speed
Ans B
46. A _______________ maintains a collection S={S1, S2, ………,Sk }of disjoint dynamic sets. Each set is identified by a ___________, which is some member of the set.
a. disjoint set data structure , representative
b. disjoint set data structure , component
c. semi-joint set data structure , representative
d. semi-joint set data structure , component
Ans A
47. The application of disjoint set data structures arises in determining the _______ component of an __________ graph
a. Connected, directed
b. Connected, Undirected
c. Unconnected, Directed
d. Unconnected, Undirected
Ans B
48. Which of the following is True
1. The alpha value is which holds best MAX value found at the MAX level
2. The alpha value is which holds best MAX value found at the MIN level
3. The beta value is which holds best MIN value at MAX level
4. The beta value is which holds best MIN value at MIN level
a. 1,2
b. 2,3
c. 1,3
d. 1,4
Ans D
49. Match the following
i) pop a) reads the top symbol and removes it from the stack
ii) push b) does nothing to the stack
iii) nop c) writes a designated symbol onto the top of the stack
a. i-b,ii-a,iii-c
b. i-a,ii-c,iii-b
c. i-a,ii-b,iii-c
d. i-c,ii-a,iii-b
Ans B
50. which of the following conditions are necessary to be satisfied for a problem to be a NP- complete problem
1. the problem L2 is in the class NP
2. the problem L2 is in the polynomial class
3. For any problem L2 in NP, there is a polynomial time reduction of L1 to L2
4. All of the above
a. 1,3
b. 2,4
c. 1,4
d. 2,3
Ans A
51. TM is an abstract entity constituted of mathematical objects like _________ and a _________
a. Sets, Relation,
b. Relation, Function
c. Function, Relation
d. Sets, function
Ans D
52. In ___________, we put all the elements that hash to the same slot in a linked list. The dictionary operations on a hash table T are easy to implement when ___________ are resolved by this method.
a. Cycle, Union
b. Cycle, Collision
c. Chaining, Collisions
d. Chaining, Union
Ans C
53. The total configuration at the start of the (Turing) Machine is called the _____________ configuration, and ______________ is a configuration whose state component is the Halt state.
a. Initial, Halted
b. Halted, Initial
c. Final, Initial
d. Final, Halted
Ans A
54. True /False
1. A language L over å, i.e. L Í å* is said to be Turing Decidable, if both the languages L and its complement å* ~L are Turing Acceptable
2. A language L over å, i.e. L Í å* is said to be Turing Decidable, if there is a function
fL : å* {Y, N}
such that for each w Îå*
fL (w)= Y if w Î L
N if w Ï L
a. Both are True
b. Both are false
c. 1 is true
d. 2 is true
Ans A
55. Consider the following instance of he PCP Alphabet å={0,1}
List L=(0,01000,01)
List M= (000,01,1)A sequence of integers that solves this problem is ______________ and concatenation of 01000, 0, 0,and 01 is equal to the concatenation of 01,000,000,1 is _____________
a. (1,1,2,3), 000000101
b. (1,2,1,3), 000100001
c. (3,1,1,2), 010001000
d. (2,1,1,3), 010000001
Ans D
56. Which of the following is True
1. There exist no algorithm for deciding whether any given context- free grammar is ambiguous
2. If the halting problem were undecidable, then every recursively enumerable language would be recursive, consequently the halting problem is decidable
a. 1 is true
b. 2 is true
c. 1 & 2 are true
d. Neither is true
Ans A
57. True/ False
1. The time complexity functions of the algorithms are compared in terms of their growth rates.
2. The size of the problem is measured in terms of the size of the output
a. T,F
b. F,T
c. T,T
d. F,F
Ans A
58. A problem which does not have any (known) polynomial time algorithm is called an ______________
a. Traceable
b. Intractable problem
c. Decidable
d. Undecidable
Ans B
59. Computers are generally used to solve complex problems. The complexity of solution may be either because of the large no. of involved _____________ and/or large size of _________.
a. Computational Steps, Output Data
b. Programmable Steps, Input data
c. Computational steps, input data
d. None of the above
Ans C
60. ___________ denotes the class o all problems , for each of which there is atleast one known polynomial time Deterministic TM solving it.
________ denotes the class of problems, for each of which , there is at least one known Non-Deterministic polynomial time solution .
a. P,NP
b. NP, P
c. RP, P
d. P, RP
Ans A
4-Marks
61. Which of the following statement is true
- Big O also known as Upper bound
- Big Θ also known as Tight bound
- Big Ω also known as Tight Bound
- Big O also known as Lower bound
- Big Ω also known as Lower bound
- Big Θ also known as Upper bound
- 1, 2, 3
- 1, 3, 5
- 1, 2, 4
- 1, 4, 6
Ans B
62. A tree is called a binary tree, if it is either ___________, or it consist of a node called _______ together with two binary tree called the _________ subtree or ______ subtree.
a. Full, Leaf, Left, Root
b. Full, Root, Left, Right
c. Empty, Root, Left, right
d. Empty, Leaf, Left, right
Ans C
63. Match the following
i Stack a) Binary search tree with one extra
bit of storage
ii Queue b) LIFO
iii Red-black tree c) self balancing binary search tree
iv Splay tree d) FIFO
a. i -b, ii -d, iii- a, iv –c
b. i- d, ii- b, iii- a, iv- c
c. i -b, ii -d, iii- c, iv –a
d. i -c, ii- a, iii- d, iv- b
Ans A
64. Which of the following are not the rules for Marienbad game
1. It is a two player game
2. It is a ‘n’ player games.
3. It starts with n matches (n >= 2)
4. The winner of the game is one who takes the last match, whosoever is left with no sticks, loses the game
5. On the very first turn, up to n-1 matches can be taken by the player having the very first move.
6. On the very first turn, up to n-1 matches can be taken by the player having the very first move.
7. On subsequent turns, one must remove at least one match and at most twice the number of matches picked up by the opponent in the last move.
8. The winner of the game is one who takes the last match whosoever is left with all the sticks
a. 1,4,6,7,8
b. 1, 3,4,6,7
c. 1,2,3,4,5
d. 1,3,4,5,6
Ans B
65. Which of the following is not the property of Depth First Search Algorithm in a graph
1. Parenthesis Structure
2. If v is a descendant of ‘u’ if and only if at the time of discovery of ‘u’, there is only one path from u to v contains only unknown vertices.
3. If v is a descendant of ‘u’ if and only if at the time of discovery of ‘u’, there is at least one path from u to v contains only unknown vertices.
4. DFS can be used to find unconnected components in a given graph.
5. DFS can be used to find connected components in a given graph.
6. DFS can be used to find the cycles in a directed graph.
7. DFS can be used to find cycles in an undirected graph.
a. 1,2, 3
b. 2, 4, 6
c. 1,3,5
d. 2, 3, 5
Ans B
66. Match the Following
Column 1 Column 2
1) Tree Edge A An edge to an already ‘discovered’ or
ancestor vertex i.e. edge (u,v) si a back
edge if it connects to a vertex v which is
already discovered which means v is an
ancestor of u
2) Back Edge B. An edge to an already visited edge
neighbor, which is not descendant.
3) Forward Edge C An edge to a still ‘unknown’ vertex i.e.
edge(u,v) is a tree edge if it is used to
discover v for the first time.
4) Cross Edge D An edge to a still “unknown” vertex i.e.
edge(u,v) is a tree edge if it is used to
discover v for the first time
- 1-D, 2- A, 3-C, 4-B
- 1-D, 2- B, 3-C, 4-A
- 1-A, 2- B, 3-C, 4-D
- 1-D, 2- A, 3-C, 4-B
Ans D
67. Match the following
Column 1 Column 2
1) Alphabet A Every member of any language is said to
be a string or a word.
2) Letter B. A finite set of symbols/characters.
3) Language over an alphabet C A set of words over an alphabet.
4) String over an alphabet D Each symbol of an alphabet.
a. 1-D, 2- A, 3-C, 4-B
b. 1-B, 2- D, 3-C, 4-A
c. 1-A, 2- B, 3-C, 4-D
d. 1-D, 2- A, 3-C, 4-B
Ans B
68. In a grammar G= (V, S, P, S)Match the following
Column 1 Column 2
1) V A is set of variables
2) S B. is a special variable
3) P C is a set of production rules
4) S D set of terminals
a. 1-D, 2- A, 3-C, 4-B
b. 1-B, 2- D, 3-C, 4-A
c. 1-A, 2- D, 3-C, 4-B
d. 1-D, 2- A, 3-C, 4-B
Ans C
69. According to Chomosky classification, match the following
Column 1 Column 2
1) Type 0 A. A production rule is of the form A-> Ù,
A-> a, or A-> aB where A, BÎV, aÎå
This grammar is called regular grammar
2) Type 1 B. A production is to be of the form A ->a
where AÎV and (aÎå)*. Also known as
context free grammar
3) Type 2 C. A production is of the form |x Ay| ≤ |xay|
as a≠ Ù, also known as context sensitive
language
4) Type 3 D. It is the grammar whose production rules
are unrestricted also known as
unrestricted grammar
a. 1-D, 2- B, 3-B, 4-A
b. 1-B, 2- D, 3-C, 4-A
c. 1-A, 2- D, 3-C, 4-B
d. 1-D, 2- A, 3-C, 4-B
Ans C
70. match the following
i) α,β,γ a) empty string
ii) ┌ b) variables for string over ∑
iii) e c) set of tape symbols
iv) R d) move the head to the right
a) i-a,ii-b,iii-c,iv-d
b) i-b,ii-c,iii-a,iv-d
c) i-b,ii-c,iii-a,iv-d
d) i-d,ii-a,iii-c,iv-b
Ans B
71. A string α over _____is said to be accepted by a TM, M =(Q,∑,Γ,δ,q0, h) if when the string ______is placed in the left most cells on the tape of M and TM is started in the initial state_____ then after a finite number of moves of the TM as determined by δ, Turing machine is in state_____.
a. Σ, α, q0, h
b. α, Σ, h, q0
c. q0, Σ, α, h
d. α, q0, h, Σ
Ans A
72. The language {anbn |n³0} can be accepted by a PDA. The following PDA will do the job, where x is the initial symbol on stack:
|
0 |
|
1 |
|
2 |
|
a, X push(X)
|
|
a, y push(Y)
|
|
b, Y pop
|
|
|
|
^, Y nop
|
|
^, Y nop
|
1. (1, a, Y, pop, 1)
2. (0, ^, X, nop,2)
3. (1, b, Y, nop, 1)
4. (0, a, X, push(Y), 0)
5. (1, b, Y, push(X), 0)
6. (0, a, Y push(Y), 0)
7. (0, b, Y, pop, 1)
8. (1, b, Y, pop, 1)
9. (1, ^, Y, pop, 1)
a. 1,2,3,4,5,6
b. 2,4,5,6,7,9
c. 2,4,6,7,8,9
d. 1,3,4,5,6,7
Ans C
73. TM can be represented as
|
D |
a |
|