CS502 Quiz No 1 Solution Mega File Question No: 1 ( Marks: 1 ) - Please choose one An optimization problem is one in w...
CS502 Quiz No 1 Solution Mega File
|
Question No:
1 ( Marks: 1 ) - Please choose one An optimization problem is one in which you want to find, ► Not a solution ► An algorithm ► Good solution ► The best solution (Page 97) Question No:
2 ( Marks: 1 ) - Please choose one Although it requires more complicated data structures, Prim's
algorithm for a minimum spanning tree is better than Kruskal's when the graph
has a large number of vertices. ► True click here 4 detail ► False Question No:
3 ( Marks: 1 ) - Please choose one If a problem is in NP, it must also be in P. ► True ► False ► unknown (Page 173) Question No:
4 ( Marks: 1 ) - Please choose one What is generally true of Adjacency List and Adjacency Matrix
representations of graphs? ► Lists require
less space than matrices but take longer to find the weight of an edge (v1,v2) ► Lists require
less space than matrices and
they are faster to find the weight of an edge (v1,v2) ► Lists require
more space than matrices and
they take longer to find the weight of an edge (v1,v2) ► Lists require more space than matrices but are faster to find the weight of an edge (v1,v2) Question No: 5 ( Marks: 1
) - Please choose one If a graph has v vertices and e edges then to obtain a spanning tree
we have to delete ► v edges. ► v – e + 5 edges ► v + e edges. ► None of these Question No:
6 ( Marks: 1 ) - Please choose one Maximum number of vertices in a Directed Graph may be |V2| ► True ► False click here for details Question No: 7 ( Marks: 1
) - Please choose one The Huffman algorithm finds a (n) _____________ solution. ► Optimal
click here
for detail ► Non-optimal ► Exponential ► Polynomial Question No:
8 ( Marks: 1 ) - Please choose one The Huffman algorithm finds an exponential solution ► True ► False Question No:
9 ( Marks: 1 ) - Please choose one The Huffman algorithm finds a polynomial solution ► True ► False Question No:
10 ( Marks: 1 ) - Please choose one The greedy part of the Huffman encoding algorithm is to first
find two nodes with larger frequency. ► True ► False (Page 100) Question No: 11 ( Marks: 1
) - Please choose one The codeword assigned to characters by the Huffman algorithm have the
property that no codeword is the postfix of any other. ► True (Page 101) ► False Question No:
12 ( Marks: 1 ) - Please choose one Huffman algorithm uses a greedy approach to generate a postfix
code T that minimizes the expected length B (T) of the encoded string. ► True ► False (Page 102) Question No:
13 ( Marks: 1 ) - Please choose one Shortest path problems can be solved efficiently by modeling the
road map as a graph. ► True
(Page 153) ► False Question No:
14 ( Marks: 1 ) - Please choose one Dijkestra’s single source shortest path algorithm works if all
edges weights are non-negative and there are negative cost cycles. ► True ► False (Page
159) Question No:
15 ( Marks: 1 ) - Please choose one Bellman-Ford allows negative weights edges and negative cost
cycles. ► True
► False (Page 159) Question No:
16 ( Marks: 1 ) - Please choose one The term “coloring” came form the original application which was
in architectural design. ► True ► False (Page 176) Question No:
17 ( Marks: 1 ) - Please choose one In the clique cover problem, for two vertices to be in the same
group, they must be adjacent to each other. ► True (Page 176) ► False Question No:
18 ( Marks: 1 ) - Please choose one Dijkstra’s algorithm is operates by maintaining a subset of
vertices ► True (Page 155) ► False Question No:
19 ( Marks: 1 ) - Please choose one The difference between Prim’s algorithm and Dijkstra’s algorithm
is that Dijkstra’s algorithm uses a different key. ►True (
Page 156) ► False Question No:
21 ( Marks: 1 ) - Please choose one We do sorting to, ► keep elements in random positions ► keep the algorithm run in linear order ► keep the algorithm run in (log n) order ► keep
elements in increasing or decreasing order
(Page 40) Question No: 22 ( Marks: 1
) - Please choose one After partitioning array in Quick sort, pivot is placed in a position
such that ► Values
smaller than pivot are on left and larger than pivot are on right (Page 48) ► Values
larger than pivot are on left and smaller than pivot are on right ► Pivot
is the first element of array ► Pivot is the last element
of array Question No: 23 ( Marks: 1 ) - Please choose one Merge sort is stable sort, but not an in-place algorithm ► True (Page
54) ► False Question No:
24 ( Marks: 1 ) - Please choose one In counting sort, once we know the ranks, we simply _________
numbers to their final positions in an output array. ► Delete ► copy (Page 57) ► Mark ► arrange Question No:
25 ( Marks: 1 ) - Please choose one Dynamic programming algorithms need to store the results of
intermediate sub-problems. ► True (Page 75) ► False Question No:
26 ( Marks: 1 ) - Please choose one A p × q matrix A can be multiplied with a q × r matrix B. The
result will be a p × r matrix C. There are (p . r) total entries in C and each takes _________ to compute. ► O (q) (Page 84) ► O (1) ► O (n2) ► O (n3) Question No: 1 ( Marks: 1 ) - Please choose one _______________ is a graphical representation of an
algorithm ► ► ►
Flowchart Click here for detail ► Asymptotic
notation Question No: 2 ( Marks: 1 ) - Please choose one Which of the following is calculated with big o
notation? ·
►Lower bounds ·
►Upper bounds (Page 25) ·
►Both upper and lower bound ·
►Medium bounds Question No: 3 ( Marks: 1 ) - Please choose one Merge sort makes two recursive calls. Which statement is
true after these recursive calls finish, but before the merge step? ·
►The array elements form a heap ·
►Elements in
each half of the array are sorted amongst themselves click here 4
detail ·
►Elements in the first half of the array are
less than or equal to elements in the second half of the array ·
►None of the above Question No: 4 ( Marks: 1 ) - Please choose one Who invented Quick sort procedure? ·
►Hoare click
here 4 detail ·
►Sedgewick ·
►Mellroy ·
►Coreman Question No: 5 ( Marks: 1 ) - Please choose one What is the solution to the recurrence T(n) = T(n/2)+n,
T(1) = 1 ·
►O(logn) ·
►O(n) (Page 37) ·
►O(nlogn) ·
►O(2n) Question No: 6 ( Marks: 1 ) - Please choose one Consider the following Huffman Tree The binary code for the string TEA is ·
►10 00 010 click here 4 detail ·
►011 00 010 ·
►10 00 110 ·
►11 10 110 Question No: 7 ( Marks: 1 ) - Please choose one A greedy algorithm does not work in phases. ►True ►False (Page 97) Question No: 8 ( Marks: 1 ) - Please choose one Can an adjacency matrix for a directed graph ever not be
square in shape? ·
►Yes ·
►No click
here 4 detail Question No: 9 ( Marks: 1 ) - Please choose one One of the clever aspects of heaps is that they can be
stored in arrays without using any____________. ·
►Pointers (Page 40) ·
►constants ·
►variables ·
►functions Question No: 10 ( Marks: 1 ) - Please choose one Merge sort requires extra array storage, ·
►True (Page 54) ·
►False Question
No: 11 ( Marks: 1 ) - Please choose one Non-optimal
or greedy algorithm for money change takes____________ ·
►O(k) (Page 99) ·
►O(kN) ·
►O(2k) ·
►O(N) Question No: 12 ( Marks: 1 ) - Please choose one The Huffman codes provide a method of encoding data inefficiently
when coded using ASCII standard. ·
►True ·
►False (Page 99) Question
No: 13 ( Marks: 1 ) - Please choose one Using
ASCII standard the string abacdaacac will be encoded with __________ bits. ·
►80 (Page 99) ·
►160 ·
►320 ·
►100 Question No: 14 ( Marks: 1 ) - Please choose one Using ASCII standard the string abacdaacac will be encoded
with 160 bits. ·
►True ·
►False (Page 99) Question No: 15 ( Marks: 1 ) - Please choose one Using ASCII standard the string abacdaacac will be encoded
with 320 bits. ·
►True ·
►False (Page 99) Question No: 16 ( Marks: 1 ) - Please choose one Using ASCII standard the string abacdaacac will be encoded
with 100 bits. ·
►True ·
►False (Page 99) ·
Question No: 17 ( Marks: 1 ) - Please choose one Using ASCII standard the string abacdaacac will be encoded
with 32 bytes ·
►True ·
►False (Page 99) Question No: 18 ( Marks: 1 ) - Please choose one The greedy part of the Huffman encoding algorithm is to
first find two nodes with smallest frequency. ·
►True (Page 100) ·
►False Question No: 19 ( Marks: 1 ) - Please choose one The greedy part of the Huffman encoding algorithm is to
first find two nodes with character frequency ·
►True ·
►False (Page 100) Question No: 20 ( Marks: 1 ) - Please choose one Huffman algorithm uses a greedy approach to generate an antefix
code T that minimizes the expected length B (T) of the encoded string. ·
►True ·
►False (Page
102) Question No: 21 ( Marks: 1 ) - Please choose one Depth first search is shortest path algorithm that works
on un-weighted graphs. ·
►True ►False (Page 153) Question No: 22 ( Marks: 1 ) - Please choose one Dijkestra s single source shortest path algorithm works if
all edges weights are non negative and there are no negative cost cycles. ·
►True (Page 159) ·
►False Question No: 23 ( Marks: 1 ) - Please choose one Dijkestra s single source shortest path algorithm works if
all edges weights are negative and there are no negative cost cycles. ·
►True ·
►False (Page
159) Question No: 24 ( Marks: 1 ) - Please choose one Floyd-Warshall algorithm is a dynamic programming
algorithm; the genius of the algorithm is in the clever recursive formulation
of the shortest path problem. ·
►True (Page 162) ·
►Flase Question No: 25 ( Marks: 1 ) - Please choose one Floyd-Warshall algorithm, as in the case with DP
algorithms, we avoid recursive evaluation by generating a table for ·
►k ·
► ·
►True ·
►Flase Question No: 26 ( Marks: 1 ) - Please choose one The term coloring came from the original application which
was in map drawing. ·
►True (Page 176) ·
►False Question No: 27 ( Marks: 1 ) - Please choose one In the clique cover problem, for two vertices to be in the
same group, they must be_______________each other. ·
►Apart from ·
►Far from ·
►Near to ·
►Adjacent to (Page
176) Question No: 28 ( Marks: 1 ) - Please choose one Fixed-length
codes may not be efficient from the perspective of _______the total quantity
of data. Select correct option: ►Minimizing (Page 99) ►Averaging ►Maximizing ►Summing Question No: 29 ( Marks: 1 ) - Please choose one In greedy algorithm, at each phase, you take the________
you can get right now, without regard for future consequences. ►Worst ►Minimum ►Good ►Best (Page 97) Question No: 30 ( Marks: 1 ) - Please choose one The difference between Prim s algorithm and Dijkstra s
algorithm is that Dijkstra s algorithm uses a same key. ·
►True ·
►False ( Page
156) Question No:
1 ( Marks: 1 ) - Please choose one If a problem is in NP-complete, it must also be in NP. ► True (Page 178) ► False Question No:
2 ( Marks: 1 ) - Please choose one If
there are n items, there are _______ possible combinations of the items. ►2 ►n ►2^n (Page 92) ►3^n Question No:
3 ( Marks: 1 ) - Please choose one Using
ASCII code, each character is represented by a fixed-length code word of
________ bits per character. ►4 ►6 ►8 (P)age 99) ►10 Question No:
4 ( Marks: 1 ) - Please choose one In
Knapsack Problem, the thief’s goal is to put items in the bag such that the
______ of the items does not exceed the limit of the bag. ►Value (Page 91) ►Weight ►Length ►Balance Question No:
5 ( Marks: 1 ) - Please choose one The
knapsack problem does not belong to the domain of optimization problems. ►True ►False (Page 91) Question No:
6 ( Marks: 1 ) - Please choose one In
Huffman encoding, for a given message string, the frequency of occurrence
(relative probability) of each character in the message is determined last. ►True ►False (Page 100) Question No:
7 ( Marks: 1 ) - Please choose one Fixed-length
codes are known for easy break up of a string into its individual characters. ►True (Page
99) ►False Question No:
8 ( Marks: 1 ) - Please choose one In
______ Knapsack Problem, limitation is that an item can either be put in the
bag or not-fractional items are not allowed. ►0 ►1 ►0/1 (Page 91) ►Fractional Question No:
9 ( Marks: 1 ) - Please choose one The term “coloring” came from
the original application which was in architectural design. ► True ► False (Page 173) Question No:
10 ( Marks: 1 ) - Please choose one In Knapsack Problem, value and weight both are to be under
consideration. ►True (page 91) ►False Question No:
11 ( Marks: 1 ) - Please choose one Time complexity of DP based algorithm for computing the
minimum cost of chain matrix Multiplication is ________ . ►log n ►n ►n2 ►n3 (Page 90) Question No:
12 ( Marks: 1 ) - Please choose one In
DP based solution of knapsack problem, to compute entries of V we will imply
a/an _______ approach. ►Subjective ►Inductive (Page 93) ►Brute force ►Combination Question No:
13 ( Marks: 1 ) - Please choose one A
greedy algorithm sometimes works well for optimization problems. ►True (Page 97) ►False Question No:
14 ( Marks: 1 ) - Please choose one In Huffman encoding, frequency of each character can be
determined by parsing the message and __________ how many times each
character (or symbol) appears. ►Printing ►Incrementing ►Counting (Page 100) ►Deleting Question No:
15 ( Marks: 1 ) - Please choose one Greedy
algorithm can do very poorly for some problems. ►True (Page 97) ►False Question No:
16 ( Marks: 1 ) - Please choose one The Huffman codes
provide a method of _________ data efficiently. ►Reading ►Encoding (Page 99) ►Decoding ►Printing Question No:
17 ( Marks: 1 ) - Please choose one In _______ based solution of knapsack problem, we consider
2 cases, Leave object Or Take object. ►Brute force ►Dynamic programming (Page 93) Question No:
18 ( Marks: 1 ) - Please choose one Those problems in which Greedy finds good, but not always
best is called a greedy________. ►Algorithm ►Solution ►Heuristic (Page 97) ►Result Question No:
19 ( Marks: 1 ) - Please choose one In brute force based solution of knapsack problem, we
consider 2 cases, Leave object Or Take object. ►TRUE ►FALSE (Page 97) Question No:
20 ( Marks: 1 ) - Please choose one ________ problem, we want to find the best solution. ►Minimization ►Averaging ►Optimization (Page 97) ►Maximization Question No:
21 ( Marks: 1 ) - Please choose one Using ASCII standard the
string abacdaacac will be encoded with 10 bytes. ·
►True (Page 101) ·
►False
Question No:
22 ( Marks: 1 ) - Please choose one In _______ algorithm, you hope that by choosing a local
optimum at each step, you will end up at a global optimum. ►Simple ►Non Greedy ►Greedy (Page 97) ►Brute force Question No: 23 ( Marks: 1 ) - Please choose one Huffman algorithm uses a
greedy approach to generate an prefix code T that minimizes the expected
length B (T) of the encoded string. ·
►True (Page
102) ·
►False Question # 1 of 10 ( Marks: 1
) Please choose one Counting Money problem is an example which cannot be
optimally solved by greedy algorithm. ►True (Page 97) ►False Question # 1 of 10 ( Marks: 1
) Please choose one Huffman algorithm generates an optimum prefix code. ►True (Page 102) ►False Question # 1 of 10 ( Marks: 1
) Please choose one If the string “lmncde” is coded with ASCII code, the
message length would be _______ bits. ►24 ►36 ►48 (6*8=48) ►60 Question # 1 of 10 ( Marks: 1
) Please choose one There are _________ nested loops in DP based algorithm for
computing the minimum cost of chain matrix multiplication. ►2 ►3 (Page 90) ►4 ►5 Question # 1 of 10 ( Marks: 1
) Please choose one Inductive approach to compute entries of V is implied in
_____ based solution of knapsack problem. ►Brute force ►Dynamic programming (Page 93) Question # 1 of 10 ( Marks: 1
) Please choose one A number of lectures are to be given in a single lecture
hall. Optimum scheduling for this is an example of Activity selection. ►True (Page 105) ►False Question # 1 of 10 ( Marks: 1
) Please choose one The activity scheduling is a simple scheduling problem for
which the greedy algorithm approach provides a/an ________solution. ►Simple ►Sub optimal ►Optimal (Page 105) ►Non optimal Question # 1 of 10 ( Marks: 1
) Please choose one The string |xyz|, if coded with ASCII code, the message
length would be 24 bits. ►True (3*8=24) ►False Question # 1 of 10 ( Marks: 1
) Please choose one An application problem is one in which you want to find,
not just a solution, but the ____ solution. ►Simple ►Good (Page 113) not sure ►Best ►Worst Question # 1 of 10 ( Marks: 1
) Please choose one A dense undirected graph is: ► A graph
in which E = O(V^2) click
here 4 detail ►A graph in which E = O(V) ►A graph in which E = O(log V) ►All items above may be used to characterize a dense
undirected graph Question # 1 of 10 ( Marks: 1
) Please choose one Suppose that a graph G = (V,E) is implemented using
adjacency lists. What is the complexity of a breadth-first traversal of
G? ►O(|V |^2) ►O(|V | |E|) ►O(|V |^2|E|) ►O(|V | + |E|) pg
116 Question # 1 of 10 ( Marks: 1
) Please choose one Which is true statement? ►Breadth first search
is shortest path algorithm that works on un-weighted graphs (Page 153) ►Depth first search is shortest path algorithm that works
on un-weighted graphs. ►Both of above are true. ►None of above are true. Question # 1 of 10 ( Marks: 1
) Please choose one Forward edge is: ► (u, v) where u is a proper descendent of v in the tree.
► (u, v) where v is a
proper descendent of u in the tree. (Page 129) ► (u, v) where v is a proper ancesstor of u in the tree. ► (u, v) where u is a proper ancesstor of v in the tree. Question # 1 of 10 ( Marks: 1
) Please choose one What general property of the list indicates that the graph
has an isolated vertex? ►There is Null pointer at the end of list. ►The Isolated vertex is not handled in list. ►
Only one value is entered in the list. ►There is at least one null list. Question # 1 of 10 ( Marks: 1
) Please choose one If you find yourself in maze the better traversal approach
will be : ►BFS and DFS both are valid ►Level order ►DFS Question # 1 of 10 ( Marks: 1
) Please choose one In digraph G=(V,E) ;G has cycle if and only if ►The DFS forest has forward edge. ►The DFS forest has
back edge (Page 131) ►The DFS forest has both back and forward edge ►BFS forest has forward edge Question # 1 of 10 ( Marks: 1
) Please choose one Back edge is: ► (u, v) where v is an
ancestor of u in the tree. (Page 128) ► (u,v) where u is an ancesstor of v in the tree. ► (u, v) where v is an predcessor of
u in the tree. ►None of above Question # 1 of 10 ( Marks: 1
) Please choose one Which statement is true?
►If a dynamic-programming problem satisfies the
optimal-substructure property, then a
locally optimal solution is globally optimal. ►If a greedy choice property satisfies the
optimal-substructure property, then a locally optimal solution is globally
optimal. ► Both of
above ►None of above
Question # 1 of 10 ( Marks: 1
) Please choose one Cross edge is : ►
(u, v) where u and v are not ancestor of one another ►
(u, v) where u is ancesstor of v and v is not
descendent of u. ► (u, v) where u and v are
not ancestor or descendent of one another (Page
129) ► (u, v) where u and v are either ancestor or descendent
of one another. Question
# 1 of 10 ( Marks: 1 ) Please choose one Kruskal's
algorithm (choose best non-cycle edge) is better than Prim's (choose best
tree edge) when the graph has relatively few edges. ►True click here 4 detail ►False Question # 1 of 10 ( Marks: 1
) Please choose one Which is true statement in the following? ►Kruskal algorithm is
multiple source technique for finding MST. click here for detail ►Kruskal’s algorithm is used to
find minimum spanning tree of a graph, time complexity of this algorithm is
O(EV) ►Both of above ►Kruskal's algorithm (choose
best non-cycle edge) is better than Prim's (choose best Tree edge) when the
graph has relatively few edges. click here 4 detail Question # 1 of 10 ( Marks: 1
) Please choose one What algorithm technique is used in the implementation of
Kruskal solution for the MST? ►Greedy
Technique (Page 142) ►Divide-and-Conquer Technique ►Dynamic Programming Technique ►The algorithm combines more
than one of the above techniques Question # 1 of 10 ( Marks: 1
) Please choose one What is the time complexity to extract a vertex from the
priority queue in Prim’s algorithm? ►O (log E) ► (V) ► (V+E) ►O (log V) (Page
152) Question # 1 of 10 ( Marks: 1
) Please choose one The relationship between number of back edges and number
of cycles in DFS is, ►Both are equal ►Back edges are half of cycles ►Back edges are one quarter of
cycles ►There is no relationship between no. of edges and cycles (Page 131) Question # 1 of 10 ( Marks: 1
) Please choose one You have an adjacency list for G, what is the time
complexity to compute Graph transpose G^T.? ► (V + E) (Page
138) ► (V E) ► (V) ► (V^2) Question # 1 of 10 ( Marks: 1
) Please choose one There is relationship between number of back edges and
number of cycles in DFS ►Both are equal. ►Cycles are half of back edges. ►Cycles are one fourth of back
edges. ►There is no relationship between back edges and number of
cycles. (Page 131) Question # 1 of 10 ( Marks: 1
) Please choose one A digraph is strongly connected under what condition? ►A digraph is strongly connected if for every pair of
vertices u, v e V, u can reach v . ►A digraph is strongly
connected if for every pair of vertices u, v e V, u can reach v and vice
versa. (Page 135) ►A digraph is strongly connected if for at least one pair
of vertex u, v e V, u can reach v and vice versa. ►A digraph is strongly connected if at least one third
pair of vertices u, v e V, u can reach v and vice versa. Question # 1 of 10 ( Marks: 1
) Please choose one In in-place sorting algorithm is one that uses arrays
for storage :
►No additional array (Page 54) ►Both of above may be true according
to algorithm ►More than 3 arrays of one dimension. Question # 1 of 10 ( Marks: 1
) Please choose one In stable sorting algorithm ►One array is used ►In which duplicating elements are
not handled. ►More then one arrays are
required. ►Duplicating elements remain in same relative position
after sorting. (Page 54) Question # 1 of 10 ( Marks: 1
) Please choose one Which sorting algorithm is faster : ►O(n^2) ►O(nlogn) (Page
46) ►O(n+k)
►O(n^3) Question # 1 of 10 ( Marks: 1
) Please choose one In Quick sort algorithm, constants hidden in T(n lg n) are ►Medium ►Not known ►Small Click
here for detail Question # 1 of 10 ( Marks: 1
) Please choose one Quick sort is based on divide and conquer paradigm; we
divide the problem on base of pivot element and: Ref: - random choices for the pivot element and each choice
have an equal probability of 1/n of occurring. So we can modify the above recurrence
to compute an average rather than a max Question # 1 of 10 ( Marks: 1
) Please choose one Dijkstra’s
algorithm : ►Has greedy approach to find all
shortest paths ►Has both greedy and Dynamic
approach to find all shortest paths ►Has greedy approach to compute single source shortest
paths to all other vertices (Page 154) ►Has both greedy and dynamic
approach to compute single source shortest paths to all other vertices. Question # 1 of 10 ( Marks: 1
) Please choose one Which may be stable sort: Question # 1 of 10 ( Marks: 1
) Please choose one In the analysis of Selection algorithm, we eliminate a
constant fraction of the array with each phase; we get the convergent
_______________ series in the analysis, How much time merge sort takes for an array of numbers? Question # 1 of 10 ( Marks: 1
) Please choose one Counting sort has time complexity: The analysis of Selection algorithm shows the total running
time is indeed ________in n, Sorting is one of the few problems where provable ________
bonds exits on how fast we can sort, Question # 1 of 10 ( Marks: 1
) Please choose one In the analysis of Selection algorithm, we make a
number of passes, in fact it could be as many as, ►T(n) ►T(n /
2) ►log n (Page 37) ►n / 2 +
n / 4 Question # 1 of 10 ( Marks: 1
) Please choose one The number of nodes in a complete binary tree of
height h is ►2^(h+1) – 1 (Page
40) ►2 *
(h+1) – 1 ►2 *
(h+1) ► ((h+1)
^ 2) – 1 Question # 1 of 10 ( Marks: 1
) Please choose one How many elements do we eliminate in each time for
the Analysis of Selection algorithm? ►n / 2 elements (Page 37) ► (n /
2) + n elements ►n / 4
elements ►2 n
elements Question
# 1 of 10 ( Marks: 1 ) Please choose one Slow sorting
algorithms run in, ►T(n^2) (Page
39) ►T(n) ►T( log n) ►T(n log n) Question # 1 of 10 ( Marks: 1
) Please choose one Counting sort is suitable to sort the elements in
range 1 to k: ►K is
large ►K is small (Page 57) ►K may
be large or small ►None Question
# 1 of 10 ( Marks: 1 ) Please choose one Question # 1 of 10 ( Marks: 1
) Please choose one
Question # 1 of 10 ( Marks: 1
) Please choose one Question # 1 of 10 ( Marks: 1
) Please choose one
Question # 1 of 10 ( Marks: 1
) Please choose one
Question # 1 of 10 ( Marks: 1
) Please choose one Question # 1 of 10 ( Marks: 1
) Please choose one Memorization
is? ►To store previous results for
future use ►To avoid this unnecessary repetitions by writing down the
results of recursive calls and looking them up again if we need them later
(Page 47) ►To make the process accurate ►None of the above Question # 1 of 10 ( Marks: 1
) Please choose one Quick
sort is ►Stable & in place ►Not stable but in place (Page 57) ►Stable but not in place ►Some time stable & some
times in place Question # 1 of 10 ( Marks: 1
) Please choose one One
example of in place but not stable algorithm is ►Merger Sort ►Quick Sort (Page 54) ►Continuation Sort ►Bubble Sort Question # 1 of 10 ( Marks: 1
) Please choose one Continuation
sort is suitable to sort the elements in range 1 to k ►K is Large ►K is not known ►K may be small or large ►K is small (Page 57) Question # 1 of 10 ( Marks: 1
) Please choose one Which
may be a stable sort? ►Merger ►Insertion ► Both above (Page 54) ►None of
the above Question # 1 of 10 ( Marks: 1
) Please choose one An in
place sorting algorithm is one that uses ___ arrays for storage ►Two dimensional arrays ►More than one array ►No Additional Array (Page 54) ►None of the above Question # 1 of 10 ( Marks: 1
) Please choose one Continuing
sort has time complexity of ? ►O(n) Click
here fir detail ►O(n+k) ►O(nlogn) ►O(k) Question # 1 of 10 ( Marks: 1
) Please choose one single
item from a larger set of _____________ ►n items (Page 34) ►phases ►pointers ►vconstant Question
# 1 of 10 ( Marks: 1 ) Please choose one For the
Sieve Technique we take time ►T(nk) ( Page 34) ►T(n / 3) ►n^2 ►n/3 Question # 1 of 10 ( Marks: 1
) Please choose one One
Example of in place but not stable sort is ►Quick (Page 54) ►Heap ►Merge ►Bubble Question # 1 of 10 ( Marks: 1
) Please choose one Consider
the following Algorithm: Factorial (n){ if (n=1) return 1 else return (n * Factorial(n-1)) } Recurrence for the following algorithm is: ► T(n) = T(n-1) +1 ► T(n) = nT(n-1) +1 ► T(n)= T(n-1) +n ► T(n)=T(n(n-1))
+1 Question No: 1
( Marks: 1 ) - Please choose
one ► Arrays (Page 40) ► Structures ► Link Lis ►Stack Question No: 2
( Marks: 1 ) - Please choose
one What type of instructions Random
Access Machine (RAM) can execute?
►Algebraic and logic
►Geometric and arithmetic
►Arithmetic and logic (Page
10)
►Parallel and recursive Question No: 3
( Marks: 1 ) - Please choose
one What is the total time to
heapify? ► Ο(log n) (Page
43) ► Ο(n log
n) ► Ο(n2
log n) ► Ο(log2
n) Question No: 4
( Marks: 1 ) - Please choose
one word Algorithm comes from the
name of the muslim author
____________ ►Abu Ja’far Mohammad ibn
Musa al-Khowarizmi. Question No: 5
( Marks: 1 ) - Please choose
one al-Khwarizmi’s work was written
in a book titled _______________ ►al Kitab al-mukhatasar
fi hisab al-jabr wa’l-muqabalah
Question No: 6
( Marks: 1 ) - Please choose
one Random access machine or RAM
is a/an ► Machine build by Al-Khwarizmi ► Mechanical machine ► Electronics machine ► Mathematical model (Page 10) Question No: 7
( Marks: 1 ) - Please choose
one A RAM is an idealized machine
with ______________ random-access memory. ► 256MB ► 512MB ► an infinitely large (Page 10) ► 100GB Question No: 8
( Marks: 1 ) - Please choose
one What will be the total number of max comparisons if we
run brute-force maxima algorithm with n elements? ► ► ► ► Question No: 9
( Marks: 1 ) - Please choose
one Consider
the following code: For(j=1; j<n;j++) For(k=1; k<15;k++) For(l=5;
l<n; l++) { Do_something_constant(); } What is the order of execution for this code. ► O(n) ► O(n3) ► O(n2
log n) ► O(n2) Question No: 10 ( Marks: 1 ) - Please choose one Is it possible to sort without making comparisons? ► Yes (Page 57) ► No Question No: 11 ( Marks: 1 ) - Please choose one When we call heapify then at each level
the comparison performed takes time ► It will
take Θ (1) (Page 43) ► Time will
vary according to the nature of input data ► It can
not be predicted ► It will
take Θ (log n) Question No: 12 ( Marks: 1 ) - Please choose one In Quick sort, we don’t have the control over the sizes
of recursive calls ► True (Page 40) ► False ► Less
information to decide ► Either true
or false Question No:
13 ( Marks: 1 ) - Please choose one If there are Θ (n2) entries in edit distance
matrix then the total running time is ► Θ (1) ► Θ (n2) Click here for detail ► Θ (n) ► Θ (n log
n) Question No:
14 ( Marks: 1 ) - Please choose one For Chain Matrix Multiplication we can not use divide
and conquer approach because, ► We do not know the optimum k (Page 86) ►
We use divide and conquer for sorting only ► We can
easily perform it in linear time ► Size of
data is not given Question No:
15 ( Marks: 1 ) - Please choose one The Knapsack problem belongs to the domain of
_______________ problems. ►
Optimization (Page 91) ► NP
Complete ► Linear
Solution ► Sorting
Question No: 16 ( Marks: 1 ) - Please choose one Suppose we have three items as
shown in the following table, and suppose the capacity of the knapsack is 50
i.e. W = 50.
The
optimal solution is to pick ► Items 1 and 2 ► Items 1 and 3 ► Items 2 and 3 (correct) ► None of these Question No: 17 ( Marks: 1 ) - Please choose one who invented the quick sort ►C.A.R. Hoare Click here
for detail Question No: 18 ( Marks: 1 ) - Please choose one main elements to a divide-and-conquer ►Divide, conquer, combine (Page 27) Question No: 19 ( Marks: 1 ) - Please choose one Mergesort
is a stable algorithm but not an in-place algorithm. ►True (Page 54) ►false Question No: 20 ( Marks: 1 ) - Please choose one Counting sort the numbers to be sorted are in the range 1
to k where k is small. ►True (Page 57) ►False Question No: 21 ( Marks: 1 ) - Please choose one In selection algorithm, because we eliminate a constant
fraction of the array with each phase, we get the ►Convergent geometric series
(Page 37) ►Divergent geometric series ►None of these Question No: 22 ( Marks: 1 ) - Please choose one If an algorithm has a complexity of log 2 n
+ nlog 2
n + n. we could say that it has complexity ►O(n) ►O( n log2 n) ►O(3) ►O( log2 ( log2 n )) ►O ( log2 n) Question No: 23 ( Marks: 1 ) - Please choose one In RAM model instructions are executed ►One after another (Page 10) ►Parallel ►Concurrent ►Random Question No: 24 ( Marks: 1 ) - Please choose one Due to left-complete nature of binary tree, heaps can be
stored in ►Link list ►Structure ►Array (Page 40) ►None of above Question No: 25 ( Marks: 1 ) - Please choose one The time assumed for each basic
operation to execute on RAM model of computation is----- ►Infinite ►Continuous ►Constant (Page 10) ►Variable Question No: 26 ( Marks: 1 ) - Please choose one If the indices passed to merge
sort algorithm are not equal, the algorithm may return immediately. ►True ►False (Page 28) Question No: 27 ( Marks: 1 ) - Please choose one Brute-force algorithm uses no
intelligence in pruning out decisions. ►True
(Page 18) ►False Question No: 28 ( Marks: 1 ) - Please choose one In analysis, the Upper Bound
means the function grows asymptotically no faster than its largest term. ►True (Page
24) ►False Question No: 29 ( Marks: 1 ) - Please choose one For small values of n, any algorithm
is fast enough. Running time does become an issue when n gets large. ►True
(Page 14) ►Fast Question No: 30 ( Marks: 1 ) - Please choose one The array to be sorted is not passed as argument to the
merge sort algorithm. ►True ►False Question No: 31 ( Marks: 1 ) - Please choose one In simple brute-force algorithm,
we give no thought to efficiency. ►True
(Page 11) ►False
Question No: 32 ( Marks: 1 ) - Please choose one The ancient Roman politicians understood an important
principle of good algorithm design that is plan-sweep algorithm. ►True ►False (Page 27)
[Divide and Conquer] Question No: 33 ( Marks: 1 ) - Please choose one In 2d-space a point is said to be ________if it is not
dominated by any other point in that space. ►Member ►Minimal ►Maximal (Page 11) ►Joint Question No: 34 ( Marks: 1 ) - Please choose one An algorithm is a mathematical entity that is dependent on
a specific programming language. ► True ►False (Page 7) Question No: 35 ( Marks: 1 ) - Please choose one The running time of an algorithm would not depend upon the
optimization by the compiler but that of an implementation of the algorithm
would depend on it. ►True (Page 13) ►False Question No: 36 ( Marks: 1 ) - Please choose one F (n) and g (n) are asymptotically equivalent. This means
that they have essentially the same __________ for large n. ►Results ►Variables ►Size ►Growth rates (Page 23) Question No: 37 (
Marks: 1 ) - Please choose one 8n2 + 2n - 3 will eventually exceed c2*(n) no matter how
large we make c2. ►True (Page 25) ►False Question No: 38 ( Marks: 1 ) - Please choose one If we associate (x, y) integers pair to cars where x is the
speed of the car and y is the negation of the price. High y value for a car
means a ________ car. ►Fast ►Slow ►Expensive ►Cheap (Page 11) Question No: 39 ( Marks: 1 ) - Please choose one
Question No: 46 ( Marks: 1 ) - Please choose one In analysis, the Lower Bound
means the function grows asymptotically at least as fast as its largest term. ►True (Page 24) ►False Question No: 47 ( Marks: 1 ) - Please choose one Efficient algorithm requires
less computational……. ►Memory ►Running Time ►Memory and Running
Time (Page 9) ►Energy Question No: 48 ( Marks: 1 ) - Please choose one The O-notation is used to state
only the asymptotic ________bounds. ►Two ►Lower ►Upper (Page 25) ►Both lower & upper Question No: 49 ( Marks: 1 ) - Please choose one For the worst-case running time
analysis, the nested loop structure containing one “for” and one “while”
loop, might be expressed as a pair of _________nested summations. ►1 ►2 (Page 16) ►3 ►4
Before sweeping a vertical line in plane sweep approach,
in start sorting of the points is done in increasing order of their
_______coordinates. ►X (Page 18) ►Y ►Z ►X &
Y Question No: 51 ( Marks: 1 ) - Please choose one Brute-force algorithm for 2D-Maxima is operated by
comparing ________ pairs of points. ►Two ►Some ►Most ►All (Page 18) Question No: 52 ( Marks: 1 ) - Please choose one The function f(n)=n(logn+1)/2 is asymptotically equivalent
to nlog n. Here Lower Bound means function f(n) grows asymptotically at
____________ as fast as nlog n. ►Normal ►Least (Page 23) ►Most ►All Question No: 53 ( Marks: 1 ) - Please choose one In plane sweep approach, a vertical line is swept across
the 2d-plane and _______structure is used for holding the maximal points
lying to the left of the sweep line. ►Array ►Queue ►Stack (Page 18) ►Tree Question No: 54 ( Marks: 1 ) - Please choose one Algorithm analysts know for sure about efficient solutions
for NP-complete problems. ►True ►False (Page 9) Question No: 55 ( Marks: 1 ) - Please choose one The analysis of Selection algorithm shows the total
running time is indeed ________in n, ►arithmetic ►geometric ►linear (Page 37) ►orthogonal Question No: 56 ( Marks: 1 ) - Please choose one Question No: 57
( Marks: 1 ) - Please choose
one
In
which order we can sort? ►increasing
order only ►decreasing
order only ►increasing order or decreasing order (Page 39) ►both
at the same time Question No: 58 ( Marks: 1 ) - Please choose one For the heap sort we store the tree nodes in ►level-order traversal (Page 40) ►in-order traversal ►pre-order traversal ►post-order traversal Question No: 60 ( Marks: 1 ) - Please choose one Question No: 61 ( Marks: 1 ) - Please choose one Memoization is? ►To store previous results for
future use ►To avoid this unnecessary
repetitions by writing down the results of recursive calls and looking them
up again if we need them later (page 74) ►To make the process accurate ►None of the above Question No: 62 ( Marks: 1 ) - Please choose one Cont sort is suitable to sort
the elements in range 1 to k ►K is Large ►K is not known ►K may be small or large ►K is small (Page 57) Question No: 63 ( Marks: 1 ) - Please choose one In place stable sorting
algorithm. ►If duplicate elements
remain in the same relative position after sorting (Page 54) ►One array is used ►More than one arrays are
required ►Duplicating elements not
handled Question No: 64 ( Marks: 1 ) - Please choose one Sorting is one of the few
problems where provable ________ bonds exits on how fast we can sort, ►upper ►lower (Page 39) ►average ►log n Question No: 65 ( Marks: 1 ) - Please choose one
The running time of quick
sort depends heavily on the selection of Question No: 67 ( Marks: 1 ) - Please choose one Question No: 68 ( Marks: 1 ) - Please choose one In Quick Sort Constants hidden in T(n log n)
are ►Large ►Medium ►Small Click
here for detail ►Not Known
Quick sort is based on divide and conquer paradigm; we
divide the problem on base of pivot element and: Question No: 70 ( Marks: 1 ) - Please choose one
Question No: 75 ( Marks: 1 ) - Please choose one Question No: 76 ( Marks: 1 ) - Please choose one Floor and ceiling are ____________ to calculate
while analyzing algorithms. ►Very easy ►Usually considered
difficult (Page 31) Question No: 77 ( Marks: 1 ) - Please choose one In Heap Sort algorithm, the maximum levels an element can
move upward is _________ ►Theta (log n) (Page 43) ►Order (log n) ►Omega (log n) ►O (1) i.e. Constant time Question No: 78 ( Marks: 1 ) - Please choose one A point p in 2-dimensional space is usually given by its
integer coordinate(s)____________ ►p.x only p.y ►only p.x & p.z ► p.x & p.y (Page 17) Question No: 79 ( Marks: 1 ) - Please choose one In Heap Sort algorithm, the total running time for Heapify
procedure is ____________ ► Theta (log n) (Page
43) ►Order (log n) ►Omega (log n) ►O (1) i.e. Constant time
Question No: 82 ( Marks: 1 ) - Please choose one Question No: 84 ( Marks: 1 ) - Please choose one In Sieve Technique, we know the item of interest. Question No: 85 ( Marks: 1 ) - Please choose one Question No: 86 ( Marks: 1 ) - Please choose one Question No: 87 ( Marks: 1 ) - Please choose one ( Marks: 1 ) - Please choose one 1.Random access machine or RAM is a/an Machines build by Al-Khwarizmi Mechanical machine Electronics machine Mathematical model (lec#2 pg#10) 2._______________ is a graphical representation of an algorithm Σ notation Θ notation Flowchart( refrence cls10 chapter no1) Asymptotic notation 3. A RAM is an idealized machine with ______________ random-access memory. 256MB 512MB an infinitely large (page#10) 100GB 4.What type of instructions Random Access Machine (RAM) can execute? Choose best Algebraic and logic Geometric and arithmetic Arithmetic and logic(page#10) Parallel and recursive 5.What will be the total number of max comparisons if we run brute-force maxima algorithm with n elements. 2 2 8 * * * * n n n n n Answe is option 3 8. Consider the following Algorithm: Factorial (n){ if (n=1) return 1 else return (n * Factorial(n-1)) Recurrence for the following algorithm is: T(n) = T(n-1) +1 T(n) = nT(n-1) +1 T(n)= T(n-1) +n T(n)=T(n(n-1)) +1 (lec#9) 9. What is the total time to heapify? (Olog n) (page#43) (n log n) ( n2 log n) ( log2 n) 10.When we call heapify then at each level the comparison performed takes time It will take (1) Time will vary according to the nature of input data It can not be predicted It will take (log n) 11.In Quick sort, we don’t have the control over the sizes of recursive calls True(page#49) False Less information to decide Either true or false 12.Is it possible to sort without making comparisons? Yes (pge#57) No Question No: 13 ( Marks: 1 ) - Please choose one If there are 𝛉 n2 entries in edit distance matrix then the total running (1) ( n2 ) (pg#84) (n) (n log n) 14. For Chain Matrix Multiplication we can not use divide and conquer approach because, We do not know the optimum k (pg#86) We use divide and conquer for sorting only We can easily perform it in linear time Size of data is not given 15.The Knapsack problem belongs to the domain of _______________ problems. Optimization (pg#91) NP Complete Linear Solution Sorting 16.Suppose we have three items as shown in the following table, and suppose the capacity of the knapsack is 50 i.e. W = 50. The optimal solution is to pick item value weight 1 60 10 2 100 20 3 120 30 Items 1 and 2 Items 1 and 3 Items 2 and 3 None of these 17 - What type of instructions Random Access Machine (RAM) can execute? Choose best answer 1. Algebraic and logic 2. Geometric and arithmetic 3. Arithmetic and logic (rep) 4. Parallel and recursive Correct Choice : 3 From Lectuer # 1 18 - Random access machine or RAM is a/an 1. Machine build by Al-Khwarizmi 2. Mechanical machine 3. Electronics machine 4. Mathematical model (rep) Correct Choice : 4 From Lectuer # 1 19- _______________ is a graphical representation of an algorithm 1. Segma Notation 2. Thita Notation 3. Flowchart (rep) 4. Asymptotic notation Correct Choice : 3 From Lectuer # 2 20 - What will be the total number of max comparisons if we run brute-force maxima? algorithm with n elements? 1. n^2 2. n^n/2 3. n 4. n^8 Correct Choice : 1 From Lectuer # 3 21 - function is given like 4n^4+ 5n^3+n what is the run time of this 1. theata(n^4) 2. theata(n^3) 3. theata(4n^4+ 5n^3) 4. theata(4n^4+ 5n^3) Correct Choice : 1 From Lectuer # 4 22 - Let us say we have an algorithm that carries out N2 operations for an input of size N. Let us say that a computer takes 1 microsecond (1/1000000 second) to carry out one operation. How long does the algorithm run for an input of size 3000? 1. 90 seconds 2. 9 seconds 3. 0.9 seconds 4. 0.09 seconds Correct Choice : 2 From Lectuer # 4 23 - The appropriate big θ classification of the given function. f(n) = 4n2 + 97n + 1000 is 1. ?(n) 2. O(2^n) 3. O(n^2) 4. O(n^2logn) Correct Choice : 3 From Lectuer # 4 24 - Which sorting algorithm is faster 1. O (n log n) 2. O n^2 3. O (n) (pg#26) 4. O n^3 Correct Choice : 3 From Lectuer # 5 25 - If algorithm A has running time 7n^2 + 2n + 3 and algorithm B has running time 2n^2, then 1. Both have same asymptotic time complexity 2. A is asymptotically greater 3. B is asymptotically greater 4. None of others Correct Choice : 1 From Lectuer # 6 26 - What is the solution to the recurrence T(n) = T(n/2)+n . 1. O(logn) 2. O(n) 3. O(nlogn) 4. O(n^2) Correct Choice : 1 From Lectuer # 8 27- - How much time merge sort takes for an array of numbers? 1. (n^2) 2. T(n) 3. T( log n) 4. T(n log n) Correct Choice : 2 From Lectuer # 8 28 - Consider the following Algorithm: Factorial (n){ if (n=1) return 1 else return (n * Factorial(n-1)) } Recurrence for the following algorithm is: 1. T(n) = T(n-1) +1 2. T(n) = nT(n-1) +1 3. T(n)= T(n-1) +n 4. T(n)=T(n(n-1)) +1 Correct Choice : 4 From Lectuer # 9 29 - For the Sieve Technique we take time 1. T(nk) . (pg#34) 2. T(n / 3) 3. n^2 4. n/3 Correct Choice: 1 From Lectuer # 10 30 - Sieve Technique applies to problems where we are interested in finding a single item from a larger set of _____________ 1. n items (pg#34) 2. phases 3. pointers 4. constant Correct Choice : 1 From Lectuer # 10 31 - In Sieve Technique we do not know which item is of interest 1. FALSE 2. TRUE(pg#34) Correct Choice : 2 From Lectuer # 10 32 - For the sieve technique we solve the problem, 1. recursively (pg#34) 2. mathematically 3. accurately 4. precisely Correct Choice : 1 From Lectuer # 10 33 - For the Sieve Technique we take time 1. Tθ(nk) (pg#34) 2. T(n / 3) 3. n^2 4. n/3 Correct Choice : 1 From Lectuer # 10 34 - How many elements do we eliminate in each time for the Analysis of Selection algorithm? 1. n / 2 elements 2. (n / 2) + n elements 3. n / 4 elements 4. n elements Correct Choice : 4 From Lectuer # 10 35- Sieve Technique applies to problems where we are interested in finding a single item from a larger set of _____________ 1. n items 2. phases 3. pointers 4. constant Correct Choice : 1 From Lectuer # 10 36 - The analysis of Selection algorithm shows the total running time is indeed ________in n, 1. arithmetic 2. geometric 3. linear (pg#37) 4. orthogonal Correct Choice : 3 From Lectuer # 10 37- The reason for introducing Sieve Technique algorithm is that it illustrates a very important special case of, 1. divide-and-conquer (pg#34) 2. decrease and conquer 3. greedy nature 4. 2-dimension Maxima Correct Choice : 1 From Lectuer # 10 38 - The sieve technique works in ___________ as follows 1. phases (pg#34) 2. numbers 3. integers 4. routines Correct Choice : 1 From Lectuer # 10 39 - A (an) _________ is a left-complete binary tree that conforms to the heap order 1. heap (pg#40) 2. binary tree 3. binary search tree . array Correct Choice : 1 From Lectuer # 11 40 - For the heap sort, access to nodes involves simple _______________ operations. 1. arithmetic (pg#41) 2. binary 3. algebraic 4. logarithmic Correct Choice : 1 From Lectuer # 11 41 - We do sorting to, 1. keep elements in random positions 2. keep the algorithm run in linear order 3. keep the algorithm run in (log n) order 4. keep elements in increasing or decreasing order (pg#39) Correct Choice : 1 From Lectuer # 11 42 - For the heap sort we store the tree nodes in 1. level-order traversal (pg#40) 2. in-order traversal 3. pre-order traversal 4. post-order traversal Correct Choice : 1 From Lectuer # 11 43 - In the analysis of Selection algorithm, we make a number of passes, in fact it could be as many as, 1. T(n) 2. T(n / 2) 3. log n (pg#37) 4. n / 2 + n / 4 Correct Choice : 3 From Lectuer # 11 44 - In which order we can sort? 1. increasing order only 2. decreasing order only 3. increasing order or decreasing order (pg#39) 4. both at the same time Correct Choice : 3 From Lectuer # 11 46 - One of the clever aspects of heaps is that they can be stored in arrays without using any _______________. 1. pointers (pg#40) 2. constants 3. variables 4. functions Correct Choice : 1 From Lectuer # 1 47 - Slow sorting algorithms run in, 1. O(n^2) (pg#39) 2. O(n) 3. O( log n) 4. O(n log n) 48- What is the total time to heapify? 1. ?(log n) (pg#43) 2. ?(n log n) 3. ?(n^2 log n) 4. ?(log^2n) Correct Choice : 1 From Lectuer # 12 49 - When we call heapify then at each level the comparison performed takes time It will take O (1) 1. Time will vary according to the nature of input data 2. It can not be predicted 3. It will take O (log n) 4. None of the Given Correct Choice : 3 From Lecture # 12 50 - After partitioning array in Quick sort, pivot is placed in a position such that 1. Values smaller than pivot are on left and larger than pivot are on right ( 2. Values larger than pivot are on left and smaller than pivot are on right 3. Pivot is the first element of array 4. Pivot is the last element of array Correct Choice : 2 From Lectuer # 13 51 - The running time of quick sort depends heavily on the selection of 1. No of inputs 2. Arrangement of elements in array 3. Size o elements 4. Pivot element (pg#49) Correct Choice : 4 From Lectuer # 13 52- In Quick Sort Constants hidden in T(n log n) are 1. Large 2. Medium 3. Small 4. Not Known Correct Choice : 3 From Lectuer # 14 53 - Is it possible to sort without making comparisons? 1. Yes (pg#57) 2. No Correct Choice : 1 From Lectuer # 15 54 - Merge sort is stable sort, but not an in-place algorithm 1. TRUE (pg#54) 2. FALSE Correct Choice : 1 From Lectuer # 15 55 - In counting sort, once we know the ranks, we simply _________ numbers to their final positions in an output array. 1Delete 2 copy 3 Mark 4 arrange Correct Choice : 2 From Lectuer # 15 1. 56 - An in place sorting algorithm is one that uses ___ arrays for storage 1. Two dimensional arrays 2. More than one array 3. No Additional Array (pg#54) 4. None of the above Correct Choice : 3 From Lectuer # 15 2. 57 - Continuation/counting sort is suitable to sort the elements in range 1 to k 1. K is Large 2. K is not known 3. K may be small or large 4. K is small (pg#57) Correct Choice : 4 From Lectuer # 15 3. 58 - In stable sorting algorithm. 1. If duplicate elements remain in the same relative position after sorting 2. One array is used 3. More than one arrays are required 4. Duplicating elements not handled Correct Choice : 1 From Lectuer # 15 4. 59 - One example of in place but not stable algorithm is 1. Merger Sort 2. Quick Sort 3. Continuation Sort 4. Bubble Sort Correct Choice : 2 From Lecture # 15 5. 60 - One example of in place but not stable algorithm is 1. Merger Sort 2. Quick Sort (pg#54) 3. Continuation Sort 4. Bubble Sort Correct Choice : 2 From Lecture # 15 61- One of the clever aspects of heaps is that they can be stored in arrays without using any _______________. 1. pointers (rep) 2. constants 3. variables . functions Correct Choice : 1 From Lecture # 15 62 - Quick sort is 1. Stable & in place 2. Not stable but in place (pg#54) 3. Stable but not in place 4. Some time stable & some times in place 63 - Quick sort is 1. Stable & in place 2. Not stable but in place (rep) 3. Stable but not in place 4. Some time stable & some times in place Correct Choice : 2 From Lectuer # 15 64 - Which may be a stable sort? 1. Merger 2. Insertion 3. Both above (pg#54) 4. None of the above Correct Choice : 3 From Lectuer # 15 67 - Which of the following sorting algorithms is stable? (i) Merge sort, (ii) Quick sort, (iii) Heap sort, (iv) Counting Sort. 1. Only i 2. Only ii 3. Both i and ii 4. Both iii and iv Correct Choice : 1 From Lectuer # 15 68 Mergesort is a stable algorithm but not an in-place algorithm. 1. TRUE (pg#54) 2. FALSE Correct Choice : 1 From Lectuer # 16 69 - Memorization is? 1. To store previous results for future use 2. To avoid this unnecessary repetitions by writing down the results of recursive calls and looking them up again if we need them later (pg#74) 3. To make the process accurate 4. None of the above Correct Choice : 2 From Lectuer # 16 70 - Dynamic programming algorithms need to store the results of intermediate sub-problems. 1. TRUE (pg#75) 2. FALSE Correct Choice : 1 From Lectuer # 17 71 - Dynamic programming uses a top-down approach. 1. TRUE 2. FALSE Correct Choice : 2 From Lectuer # 17 73- The edit distance between FOOD and MONEY is 1. At most four (pg#76) 2. At least four 3. Exact four 4. Wrong Correct Choice : 1 From Lectuer # 17 74- The edit distance between FOOD and MONEY is 1. At most four 2. At least four 3. Exact four 4. Wrong Correct Choice : 1 From Lectuer # 17 75 - If there are O (n^2) entries in edit distance matrix then the total running time is 1. O (1) 2. O (n^2) (rep) 3. O (n) 4. O (n log n) Correct Choice : 2 From Lectuer # 18 76 - A p x q matrix A can be multiplied with a q x r matrix B. The result will be a p x r matrix C. There are (p . r) total entries in C and each takes _________ to compute. 1. O (q) (pg#84) 2. O (1) 3. O (n^2) 4. O (n^3) Correct Choice : 1 From Lectuer # 19 77 - For Chain Matrix Multiplication we can not use divide and conquer approach because, 1. We do not know the optimum k (rep) 2. We use divide and conquer for sorting only 3. We can easily perform it in linear time 4. Size of data is not given Correct Choice : 1 From Lectuer # 19 78 - A p x q matrix A can be multiplied with a q x r matrix B. The result will be a p x r matrix C. There are (p . r) total entries in C and each takes _________ to compute. 1. O (q) (rep) 2. O (1) 3. O (n^2) 4. O (n^3) Correct Choice : 1 From Lectuer # 19 79 - The Knapsack problem belongs to the domain of _______________ problems. 1. Optimization rep 2. NP Complete 3. Linear Solution 4. Sorting Correct Choice : 1 From Lectuer # 21 80 The codeword assigned to characters by the Huffman algorithm have the property that no codeword is the postfix of any other. 1. TRUE 2. FALSE Correct Choice : 2 From Lectuer # 22 81 - The greedy part of the Huffman encoding algorithm is to first find two nodes with larger frequency. 1. TRUE 2. FALSE Correct Choice : 2 From Lectuer # 22 82 - An optimization problem is one in which you want to find, 1. Not a solution 2. An algorithm 3. Good solution 4. The best solution Correct Choice : 4 From Lectuer # 22 83- We do sorting to, keep elements in random positions keep the algorithm run in linear order keep the algorithm run in (log n) order keep elements in increasing or decreasing order (rep) 84-Heaps can be stored in arrays without using any pointers; this is due to the ____________ nature of the binary tree, left-complete right-complete tree nodes tree leaves 85- Sieve Technique can be applied to selection problem? True ( pg#35) False 86-A heap is a left-complete binary tree that conforms to the ___________ increasing order only decreasing order only heap order (pg40) (log n) order 87- A (an) _________ is a left-complete binary tree that conforms to the heap order heap ( pg#40) binary tree binary search tree array 88- Divide-and-conquer as breaking the problem into a small number of Select correct option: pivot Sieve smaller sub problems (pg27) Selection 89- In Sieve Technique we do not know which item is of interest Select correct option: True (rep) False 90- The recurrence relation of Tower of Hanoi is given below T(n)={1 if n=1 and 2T(n-1) if n >1 In order to move a tower of 5 rings from one peg to another, how many ring moves are required? Select correct option: 16 10 32 31 (not sure) 91- In the analysis of Selection algorithm, we eliminate a constant fraction of the array with each phase; we get the convergent _______________ series in the analysis, Select correct option: linear arithmetic geometric (pg37) exponent 92- In the analysis of Selection algorithm, we eliminate a constant fraction of the array with each phase; we get the convergent _______________ series in the analysis, Select correct option: linear arithmetic geometric (rep) exponent 93-In inplace sorting algorithm is one that uses array for storage : 1. An additional array 2. No additional array (rep) 3. Both of the above 4. More then one array of one dimension. 94-The running time of quick sort depends heavily on the selection of. 1. No of inputs 2. Arrangement of element in array 3.Size Of element 4. Pivot element rep 95-For the sieve technique we solve the problem. Recursively rep mathematically precisely accurately 96-The sieve technique works in ___________ as follows Phases rep numbers integers routines 97-Slow sorting algorithms run in, T(n^2) rep T(n) T( log n) 98-A (an) _________ is a left-complete binary tree that conforms to the heap order Heap rep binary tree binary search tree array 99-In the analysis of Selection algorithm, we eliminate a constant fraction of the array with each phase; we get the convergent _______________ series in the analysis, linear arithmetic geometric rep exponent 100-In the analysis of Selection algorithm, we make a number of passes, in fact it could be as many as T(n) T(n / 2) log n (pg#37) n / 2 + n / 4 101-In which order we can sort? Select correct option: increasing order only decreasing order only increasing order or decreasing order (rep) both at the same time 102-The recurrence relation of Tower of Hanoi is given below T(n)={1 if n=1 and 2T(n-1) if n >1 In order to move a tower of 5 rings from one peg to another, how many ring moves are required? 16 10 32 31 103-Analysis of Selection algorithm ends up with, θ(n) rep T(1 / 1 + n) T(n / 2) T((n / 2) + n) 104-Memorization is? 1. To store previous results for future use 2. To avoid this unnecessary repetitions by writing down the results of recursive calls and looking them up again if we need them later (rep) 3. To make the process accurate 4. None of the above 105-Which sorting algorithm is faster 1. O (n log n) 2. O n^2 3. O (n) rep 4. O n^3 106-Quick sort is 1. Stable & in place 2. Not stable but in place (rep) 3. Stable but not in place 4. Some time stable & some times in place 107-One example of in place but not stable algorithm is 1. Merger Sort 2. Quick Sort rep 3. Continuation Sort 4. Bubble Sort 108-In Quick Sort Constants hidden in T(n log n) are 1. Large 2. Medium 3. Small rep 4. Not Known 109-Counting sort is suitable to sort the elements in range 1 to k 1. K is Large 2. K is not known 3. K may be small or large 4. K is small rep 110-In stable sorting algorithm. 1. If duplicate elements remain in the same relative position after sorting rep 2. One array is used 3. More than one arrays are required 4. Duplicating elements not handled 111-Which may be a stable sort? 1. Merger 2. Insertion 3. Both above rep 4. None of the above 112-An in place sorting algorithm is one that uses ___ arrays for storage 1. Two dimensional arrays 2. More than one array 3. No Additional Array rep 4. None of the above 113-Counting sort has time complexity of ? 1. O(n) 2. O(n+k) 3. O(nlogn) 4. O(k) 114-We do sorting to, keep elements in random positions keep the algorithm run in linear order keep the algorithm run in (log n) order keep elements in increasing or decreasing order rep 115-Divide-and-conquer as breaking the problem into a small number of pivot Sieve smaller sub problems rep Selection 116-The analysis of Selection algorithm shows the total running time is indeed ________in n, arithmetic geometric linear pg#37 orthogonal 117-How many elements do we eliminate in each time for the Analysis of Selection algorithm? n / 2 elements (pg#37) (n / 2) + n elements n / 4 elements 2 n elements 118-Sieve Technique can be applied to selection problem? True rep FALSE 119- For the heap sort we store the tree nodes in level-order traversal rep in-order traversal pre-order traversal post-order traverse 120-In RAM model instructions are executed One after another pg#10 Parallel Concurrent Random 121-In selection algorithm, becausewe eliminate a constant fraction of the array with each phase, we get the Convergent geometric series rep Divergent geometric series None of these 122-Due to left-complete nature of binary tree, heaps can be stored in Link list Structure Array None of above 123-If algorithm A has running time 7n2 + 2n + 3 and algorithm B has running time 2n2, then Both have same asymptotic time complexity rep A is asymptotically greater B is asymptotically greater None of others 124-Which of the following sorting algorithms is stable? (i) Merge sort, (ii) Quick sort, (iii) Heap sort, (iv) Counting Sort. Only i Only ii Both i and ii Both iii and iv 125-Execution of the following code fragment int Idx; for (Idx = 0; Idx < N; Idx++) { cout << A[Idx] << endl; } is best described as being O(N) O(N2) O(log N) O(N log N) 126-The edit distance between FOOD and MONEY is At most four rep At least four Exact four 127-Consider the following recurrence relation Then T(5) is 25 75 79 128-How much time merger sort takes for an array of numbers? T(n^2) T(n) (pg#29) T(log n) T(n log n) 129-Divide-and-Conquer is as breaking the problem into a small number of Smaller Sub Problems rep Pivot Sieve Solutions. 130-The Sieve Sequence is a special case where the number of smaller subproblems is just____. 4 Many 1 Few 131-How many elements do we eliminate each time for the Analysis of Selection Algorithm? (n / 2)+n Elements n / 2 Elements n / 4 Elements 2 n Elements 132-We do sorting to? Keep elements in random position Keep the algorithm run in linear order Keep Elements in Ascending or Descending Order rep Keep the algorithm run in (log n) order 133-Sorting is one of the few problems where provable ____ bounds exit on how fast we can sort? Upper Average Log n Lower rep 134-In the analysis of Selction Algorithm, we eliminate the constant fraction of the array with each phase, we get convergent _____ series in the analysis. Geometric rep Linear Arithmetic None of above 135-For the Sieve technique we take time? T (n/3) T𝛉 (n k) N^2 n/3 136-For the sieve technique we solve the problem Recursively Randomly Mathematically Precisely 137-The recurrence relation of Tower of Hanoi is T(n) = 1 if n = 1 and 2T(n-1) if n >1. In order to move a tower of 5 rings from one peg to another how many ring moves are required? 16 10 32 (Not Confirm) 31 138-An optimization problem is one in which you want to find, ►Not a solution ►An algorithm ►Good solution ►The best solution rep 139-Search technique is used to find the ►Maximum two solutions ►Minimum two solutions ►Sorting solution 140-What type of instructions Random access machine can execute? Geometric and arithmetic Algebraic and logic Arithmetic and logic rep Parallel and recursive 141-Due to left complete nature of binary tree, the heap can be stored in • Arrays rep • Structures • Link Lis • Stack 142-What type of instructions Random Access Machine (RAM) can execute? Algebraic and logic Geometric and arithmetic Arithmetic and logic rep Parallel and recursive 143-For Chain Matrix Multiplication we can not use divide and conquer approach because, We do not know the optimum k We use divide and conquer for sorting only rep We can easily perform it in linear time Size of data is not given 144-We do sorting to, Select correct option: keep elements in random positions keep the algorithm run in linear order keep the algorithm run in (log n) order keep elements in increasing or decreasing order rep 145-Heaps can be stored in arrays without using any pointers; this is due to the ____________ nature of the binary tree, left-complete Page 40 right-complete tree nodes tree leaves 146-Sieve Technique can be applied to selection problem? True Page 35 False 147-A heap is a left-complete binary tree that conforms to the___________ increasing order only decreasing order only heap order Page 40 (log n) order 148-A (an) _________ is a left-complete binary tree that conforms to the heap order Heap Page 40 binary tree binary search tree array 149-Divide-and-conquer as breaking the problem into a small number of pivot Sieve smaller sub problems Page 34 Selection 150-In Sieve Technique we do not know which item is of interest True Page 34 False 151-The recurrence relation of Tower of Hanoi is given below T(n)={1 if n=1 and 2T(n-1) if n >1 In order to move a tower of 5 rings from one peg to another, how many ring moves are required? 16 10 32 31 152-In the analysis of Selection algorithm, we eliminate a constant fraction of the array with each phase; we get the convergent _______________ series in the analysis, linear arithmetic geometric Page 37 exponent 153-For the heap sort, access to nodes involves simple _______________operations.: Arithmetic Page 41 binary algebraic logarithmic 154-For the sieve technique we solve the problem, Recursively Page 34 mathematically precisely accurately 155-The sieve technique works in ___________ as follows Phases Page 34 numbers integers routines 156-Slow sorting algorithms run in, O(n2) Page 39 T(n^2) T(n) T( log n) 157-A (an) _________ is a left-complete binary tree that conforms to the heap order Heap binary tree binary search tree array 158-In the analysis of Selection algorithm, we eliminate a constant fraction of the array with each phase; we get the convergent _______________ series in the analysis, linear arithmetic geometric exponent 159-In the analysis of Selection algorithm, we make a number of passes, in fact it could be as many as, T(n) T(n / 2) log n Page 37 n / 2 + n / 4 160- The sieve technique is a special case, where the number of sub problems is just 5 many 1 Page 34 few 161-In which order we can sort? increasing order only decreasing order only increasing order or decreasing order Page 39 both at the same time 162-The recurrence relation of Tower of Hanoi is given below T(n)={1 if n=1 and 2T(n-1) if n >1 In order to move a tower of 5 rings from one peg to another, how many ring moves are required? 16 10 32 31 163-Analysis of Selection algorithm ends up with, (n) pg#37 T(1 / 1 + n) T(n / 2) T((n / 2) + n) 164-We do sorting to, keep elements in random positions keep the algorithm run in linear order keep the algorithm run in (log n) order keep elements in increasing or decreasing order rep 165-Divide-and-conquer as breaking the problem into a small number of pivot Sieve smaller sub problems rep Selection 166-The analysis of Selection algorithm shows the total running time is indeed ________in n, Arithmetic geometric linear Page 37 orthogonal 167-How many elements do we eliminate in each time for the Analysis of Selection algorithm? n / 2 elements rep (n / 2) + n elements n / 4 elements 2 n elements 168-Sieve Technique can be applied to selection problem? True False 169-For the heap sort we store the tree nodes in level-order traversal Page 40 in-order traversal pre-order traversal post-order traversal 170-One of the clever aspects of heaps is that they can be stored in arrays without using any_______________. pointers rep constants variables functions 171-For the heap sort we store the tree nodes in level-order traversal rep in-order traversal pre-order traversal post-order traversal 172-. The sieve technique works in ___________ as follows Phases Page 34 numbers integers routines 173- In the analysis of Selection algorithm, we eliminate a constant fraction of the array with each phase; we get the convergent _______________ series in the analysis, linear arithmetic geometric rep exponent 174-. We do sorting to, keep elements in random positions keep the algorithm run in linear order keep the algorithm run in (log n) order keep elements in increasing or decreasing order 175-. In the analysis of Selection algorithm, we make a number of passes, in fact it could be as many as, T(n) T(n / 2) log n rep n / 2 + n / 4 176-. In which order we can sort? increasing order only decreasing order only increasing order or decreasing order rep both at the same time 177-. In Sieve Technique we do not know which item is of interest True False 178-. For the sieve technique we solve the problem, recursively mathematically precisely 179-. Divide-and-conquer as breaking the problem into a small number of pivot Sieve smaller sub problems Selection 180-Divide-and-Conquer is as breaking the problem into a small number of · Smaller Sub Problems · Pivot · Sieve · Solutions 181-Analysis of Selection Sort ends up with · T(n) Page 37 · T(1/1+n) · T(n/2) · T((n/2) +n) 182-How many elements do we eliminate each time for the Analysis of Selection Algorithm? · (n / 2)+n Elements · n / 2 Elements · n / 4 Elements · 2 n Elements 183-A heap is a left-complete binary tree that conforms to the ? · Increasing Order · Decreasing order · Heap Order · (nlog n) order 184-The Sieve Sequence is a special case where the number of smaller sub problems is just_ .· 4 · Many · 1 · Few 185-Heaps can be stored in arrays without using any pointers this is due to the of the binary tree? · Tree Nodes · Right-Complete Nature · Left-Complete Nature · Tree Leaves 186-For the Heap Sort access to nodes involves simple _ operations: · Geometric · Linear · Arithmetic · Algebraic 187-The Analysis of Selection Sort shows that the total running time is indeed in n? · Geometric · Linear · Arithmetic · Algebraic 188-For the sieve technique we solve the problem · Recursively · Randomly · Mathematically · Precisely 189-How much time merger sort takes for an array of numbers? · T(n^2) · T(n) Page 30 · T(log n) · T(n log n) 190-Divide-and-Conquer is as breaking the problem into a small number of · Smaller Sub Problems rep · Pivot · Sieve · Solutions 191-Analysis of Selection Sort ends up with · (n) rep · T(1/1+n) · T(n/2) · T((n/2) +n) 192-How many elements do we eliminate each time for the Analysis of Selection Algorithm? · (n / 2)+n Elements · n / 2 Elements · n / 4 Elements · 2 n Elements 193-A heap is a left-complete binary tree that conforms to the ? · Increasing Order · Decreasing order · Heap Order · (nlog n) order 194-The Sieve Sequence is a special case where the number of small er sub problems is just_ . · 4 · Many · 1 · Few 195-Heaps can be stored in array s without using any pointers this is due to the of the binary tree? · Tree Nodes · Right-Complete Nature · Left-Complete Nature · Tree Leaves 196-For the Heap Sort access to nodes involves simple _ operations: · Geometric · Linear · Arithmetic rep · Algebraic The Analysis of Selection Sort shows that the total running time is indeed in n? · Geometric · Linear pg#37 · Arithmetic · Algebraic For the sieve technique we solve the problem · Recursively rep · Randomly · Mathematically · Precisely How much time merger sort takes for an array of numbers? · T(n^2) · T(n) · T(log n) · T(n log n)
|
||||||||||||||
COMMENTS