CS502 Mcq's FinalTerm by Vu Topper RM

CS502 Fundamentals Of Algorithms
Update MCQS For FinalTerm

Solve By Vu Topper RM
80 To 100% Marks
For More Help Contact What’s app 03224021365

Question No:01 (Marks:01) Vu-Topper RM
If we encode and compress text using ASCII standard each character is
represented b
A. Fixed length code word of 4 bits
B. Variable length code word up to 4 bits
C. Fixed length code word of 8 bits
D. Variable length code word up to 8 bits

G power T for graph can be computed in
A. Theta(VE)
B. Theta(V log E)
C. Theta(E log V)
D .Theta (V+E)

Adding any edge to free tree
A .Keep it free tree and increase the size of the tree
B. Create a unique cycle
C. Not allow to add edge to free tree
D. Create multiple cycles

Which sorting algorithn is faster :
A. O(n^2)
B. O(nlogn)
C. O(n+k)
D. O(n^3)

There are no ________ edges in undirected graph.
A . Forward
B. Back
C. Cross
D. Both forward and back

Adding any edge to a free tree creates a unique ______ .
A. Vertex
B. cycle
C. Edge

D.Strong component

Networks are complete in the sense that it is possible from any location in the
network to reach any other location in the digraph.
A. True
B. False

Runtime complexity of Prim's algorithm is _______.
A. V log V
B. E log V
C. log V
D. None of the above

In Prim's algorithm, we start with the _______ vertex r; it can be any vertex.
A. First
B. Leaf
C. root
D. Mid

Adding any edge to a free tree creates a unique cycle.
A. true
B. false

For undirected graph, there is no distinction between forward and back edges.
A. true
B. false

in strong components algorithm, first of all DFS is run for computing finish
times of vertices.
A. true
B. false

Which method is preferable for dealing with chain matrix multiplication?
A. Divide and conquer strategy

B. Dynamic programming formulation
C. Graph theory
D. Greedy Approach

Huffman algorithm produces the…….prefix code tree.
A. Better
B. Optimal
C. Worst
D. Best

A….w is adjacent to vertex v if there is an edge from v to w.
A. Acyclic
B. Vertex
C. Loop
D. Cycle

Using ASCII standard the string “greedy” will be encoded with
A. 44 bits
B. 120 bits
C. 40 bits
D. 48 bits

In activity scheduling algorithm, each activity is
represented by a
A. Rectangle
B. Square
C. Circle
D. Triangle

Those problems in which greedy finds good, but not always best is
called a greedy…..
A. Heuristic
B. Solution

C. Result
D. Algorithm

The knapsack problem belongs to the domain of…..Problems
A. Searching
B. Sorting
C. Linear solution
D. Optimization

The general coin change problem can be solved using
A. Recursion
B. Greedy algorithm
C. Dynamic programming
D. Divide and conquer

Huffman algorithm generates an optimum ........... code
A. Postfix
B. Infix
C. None of the given options
D. Prefix

................... ways of representing graphics
A. 1
B. 2
C. 3
D. 4

Knapsack word originates from……language
A. German
B. English
C. French
D. Norwegian

Graphs are important ................. model for many application problems
A. Mathematical
B. Unpredictable
C. Haphazard
D. Unsystematic

Which type of algorithm is harder to prove the correctness?
A. Dynamic
B. Greedy
C. Divide and conquer
D. Brute force

Items are not allowed in 0/1 knapsack problem
A. Fractional
B. 0
C. 1
D. 0/1

Matrix multiplication is a(n) ............... operation
A. Nether commutative nor associative
B. Transitive
C. Commutative
D. Associative

For a Diagraph G= (V.E), Sum of in-degree (v) --.
A. Not equal to sum of out-degree(v)
B. = sum of out-degree(v)
C. < sum of out-degree(v)
D. > sum of out-degree(v)

DFS or BFS yields a of the graph.
A. Traversed tree
B. Spanning tree Page 125
C. Simple tree
D. Free tree

Using ASCII code, each character is represented by a fixed-length code of
bits per character.
A. 4
B. 6
C. 10
D. 8

In Knapsack Problem, the goal is to put items in the Knapsack such that the
value of the items is----------------subject to weight limit of the Knapsack.
A. Minimized
B. Decreased
C. Maximized
D. None of the above given

A graph is said to be acyclic if it contains --.
A. At least one cycle
B. Exactly one cycle
C. Always more than one cycle
D. No cycles

The number of edges that come out of a vertex is called the of that vertex
in the digraph.
A. Post-degree
B. in-degree
C. out-degree
D. pre-degree

If Matrix-A has dimensions “3x2” and Matrix-B has dimensions “2x3”, then
multiplication of Matrix-A and Matrix-B will result a new Matrix-C having
dimensions.
A. 3x2
B. 2x3
C. 2x2
D. 3x3

A/an is one in which you want to find, not just a solution, but the best
solution.
A. Optimization problem
B. Divide and Conquer
C. NP complete problem
D. Best problem

Fractional Knapsack is founded on ----------method.
A. Greedy page
B. Recursive
C. Divide and Conquer
D. Dynamic programming

Find the maximum value of the items which can carry using knapsack weight capacity
=50
ITEM 10 20 30 70
WEIGHT
VALUE 70 20 80 200
A. 90
B. 280
C. 200
D. 100

If the graph is represented using an adjacency matrix, then Breadth-first
search takes------------time.
A. O(E+1)
B. O(V^2)
C. O(V)

D. O(E)

In inductive approach of Knapsack problem, we consider 2 cases, ------------
or --.Median, Mode
A. Recursive, Iterative
B. Leave object, Take object
C. Sequentially, Parallel

A Greedy algorithm can NOT be used to solve all the problems.
A. Dynamic programming
B. Memorization programming
C. Edit-distance programming
D. Storing value programming

In Huffman encoding, the is the number of occurrences of a character
divided by the total characters in the message.
A. Counting
B. Parsing
C. Relative Probability
D. Weight

The Binary Tree constructed by a Huffman Encoding is a:
A. Full Binary Tree
B. Partial Binary Tree
C. Incomplete Binary Tree
D. None of the given option

Following is not the application of Edit Distance Problem.
A. Speech recognition
B. Spelling correction
C. Ascending order
D. Computational Molecular Biology

Consider three Matrices X, Y, Z of dimensions 1x2, 2x3, 3x4 respectively.
The number of multiplication of(XYZ) is:
A. 18
B. 32
C. 24
D. 30

In-----Knapsack Problem, limitation is that an item can either be put in the
bag or not. Fractional items are not allowed.
A. 0
B. 1
C. 0/1
D. Fractional

An in-place sorting algorithm is one that uses additional array for storage.
A. Always
B. Permanently
C. Does not
D. Sometime

If Matrix-A has dimensions “pxq” and Matrix-B has dimensions “qxr”, then
multiplication of Matrix-A and Matrix-B will result a new Matrix-C having
dimensions.
A. P x q
B. P x r
C. q x r
D. q x p

Counting sort is suitable to sort the elements in range 1 to K.
A. K is large
B. K is small
C. K may be large or small
D. None

When matrix A of 5x 3 is multiply with matrix B of 3x 4 then the
multiplication required is:
A. 15
B. 12
C. 36
D. 60

-------------------- is a linear time sorting algorithm.
Merge sort
Quick sort
Bubble sort
Radix sort

In Dynamic Programming approach, we do not store the solution to each sub
problem in case if it reappears.
A. True
B. False

Dynamic Programming approach is usually useful in solving optimization
problem.
A. True
B. False

Which of the following algorithm provides an optimal solution for the
activity selection problem?
A. Divide and Conquer
B. Brute force
C. Greedy
D. Recursive

A graph is if every vertex can reach every other vertex.
A. Connected
B. Cycle
C. Acyclic
D. Loop

In a Huffman encoding when a new node is created by combining two nodes,
the new node is placed in the _ .
A. Priority queue
B. Linked list
C. Min heap tree
D. Graph traversal

In algorithm, you hope that by choosing a local optimum at each step, you
will end up a global optimum.
A. Simple
B. Divide and conquer
C. Greedy
D. Brute Force

The string “Imncde” is coded with ASCII code, the message length would
be bits.
A. 24
B. 36
C. 48
D. 60

For graph traversal, breadth-first search strategy _
A. Is always recursive
B. Cannot br recursive
C. Cannot be non-recursive
D. Can be both recursive and non-recursive

In activity scheduling algorithm , the width of a rectangle _
A. Is always ignored
B. Directs towards recursion
C. Should be maximized
D. Indicates the duration of an activity

If the graph is represented using an adjacency list, then Breadth-first search
take time
A. O(V^2)
B. O(V)
C. O(V+E)
D.O(E+1)

Suppose you are given infinite coins of 1,2 ,3, and 4.Select the ways of the
minimum number of coins that required to achieve a sum of 6:
A. 1
B. 2
C. 3
D. 4

sing ASCII standard the string “greedy” will be encoded with
A. 48 bitS
B. 20 bits
C. 44 bits
D.40 bits

The Huffman codes provide a method of data efficiency.
A. Reading/Writing
B.Encoding/Decoding
B. Divide/Conquer
C. Inserting/Deleting

In the context of activity selection algorithm, time s dominated by sorting of
the activities by------.
A. Start Times
B. Finish Times
C. Average Times
D.CPU Burst Times

Time complexity of the “0-1” knapsack algorithm depends on----
A. Number of items
B. Capacity of the knapsack
C. Size of the Table
D. Number of items and capacity of knapsack

The greedy approach gives us an optimal solution when the coins are all
powers of a --------denomination
A. Fixed
B. Variable
C. Constant
D.Static

In Activity Selection, we say that two activities are non-interfering if their
start-finish interval overlap
A. Do
B. Do not
C. Sometimes
D.Once

How many steps are involved to design the dynamic programming strategy?
A. 2
B. 3
C. 1
D. 4

Bag is a
A. type of algorithm
B. data structure
C. program
D.compiler

If a problem is in NP-complete, it must also be in NP.
A. True
B.False

The Huffman algorithm finds a optimal solution.
A. True
B. false

The Huffman algorithm finds an exponential solution
A. True
B. False

The Huffman algorithm finds a polynomial solution
A. True
B. False

The greedy part of the Huffman encoding algorithm is to first find two nodes
withs sallest frequency.
A. True
B. False

The code word assigned to characters by the Huffman algorithm have the
property that no code word is the prefix of any other.
A. True
B.False

Dijkestra’s single source shortest path algorithm works if all edges weights
are non-negative and there are negative cost cycles.
A. True
B. False

The term “coloring” came form the original application which was in
architectural design.
A. True
B. False

In the clique cover problem, for two vertices to be in the same group, they
must be adjacent to each other.

A. True
B. False

Dijkstra’s algorithm is operates by maintaining a subset of vertices
A. True
B.False

We do sorting to,
A. keep elements in random positions
B. keep the algorithm run in linear order
C. keep the algorithm run in (log n) order
D. keep elements in increasing or decreasing order

After partitioning array in Quick sort, pivot is placed in a position such that
A. Values smaller than pivot are on left and larger than pivot are on
right
B. Values larger than pivot are on left and smaller than pivot are on right
C. Pivot is the first element of array
D. Pivot is the last element of array

Merge sort is stable sort, but not an in-place algorithm
A. True
B.False

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.
A. O (q)
B. O (1)
C. O (n2)
D. O (n3)

One of the clever aspects of heaps is that they can be stored in arrays
without using any ---------.
A. Pointers
B. constants

C. variables
D.functions

Merge sort requires extra array storage,
A. True
B.False

The Huffman codes provide a method of encoding data inefficiently when
coded using ASCII standard.
A. True
B. False

Using ASCII standard the string abacdaacac will be encoded with bits.
A. 80
B. 160
C. 320
D. 100

Using ASCII standard the string abacdaacac will be encoded with 160 bits.
A. True
B. False

Using ASCII standard the string abacdaacac will be encoded with 10 bytes.
A. True
B. False

The greedy part of the Huffman encoding algorithm is to first find two nodes
with character frequency
A. True
B. False

Huffman algorithm uses a greedy approach to generate an prefix code T that
minimizes th expected length B (T) of the encoded string.
A. True
B. False

An optimization problem is one in which you want to find,
A. Not a solution
B. An algorithm
C. Good solution
D. The best solution

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 vert
A. True
B.False

If a problem is in NP, it must also be in P.
A. True
B. False
C.unknown

What is generally true of Adjacency List and Adjacency Matrix
representations of graphs?
A. Lists require less space than matrices but take longer to find the
weight of an edge (v1,v2)
B.Lists require less space than matrices and they are faster to find the
weight of an edge (v1,v2)
C. Lists require more space than matrices and they take longer to find
the weight of an edge (v1,v2)
D. Lists require more space than matrices but are faster to find the weight
of an edge (v1,V2)

If a graph has v vertices and e edges then to obtain a spanning tree we have
to delete
A. v edges.
B. v – e + 5 edges
C. v + e edges.
D. None of these

Maximum number of vertices in a Directed Graph may be |V2|
A. True
B. False

The Huffman algorithm finds a (n) _ solution.
A. Optimal
B. Non-optimal
C. Exponential
D.Polynomial

Edge (u, v) is a forward edge if
A. u is a proper descendant of v in the tree
B. v is a proper descendant of u in the tree pg#129
C.None of these

In counting sort, once we know the ranks, we simply numbers to their
final positions in an output array.
A. Delete
B. copy
C. Mark
D.arrange

Dynamic programming algorithms need to store the results of intermediate
sub-problems.
A. True
B.False

________is a graphical representation of an algorithm
A. notation
B. notation
C. Flowchart
D.Asymptotic notation

Which of the following is calculated with big o notation?
A. Lower bounds
B. Upper bounds
C. Both upper and lower bound
D.Medium bounds

Merge sort makes two recursive calls. Which statement is true after these
recursive calls finish, but before the merge step?
A. The array elements form a heap
B. Elements in each half of the array are sorted amongst themselves
C. Elements in the first half of the array are less than or equal to
elements in the second half of the array

What is the solution to the recurrence T(n) = T(n/2)+n, T(1) = 1
A. O(logn)
B.O(n)
C. O(nlogn)
D. O(2n)

Consider the following Huffman Tree The binary code for the string TEA is
A. 00 010
B. 011 00 010
C. 10 00 110
D. 11 10 110

A greedy algorithm does not work in phases.
A. True
B. False

Can an adjacency matrix for a directed graph ever not be square in shape?
A. Yes
B. No

One of the clever aspects of heaps is that they can be stored in arrays without
using any .
A. Pointers
B. constants
C. variables
D.functions

Non-optimal or greedy algorithm for money change takes_
A. O(k)
B. O(kN)
C. O(2k)
D. O(N)

A. True
B. False

A. True
B. False

Using ASCII standard the string abacdaacac will be encoded with 32 bytes
A. True
B. False

Huffman algorithm uses a greedy approach to generate an antefix code T that
minimizes the expected length B (T) of the encoded string.
A. True
B. False

Depth first search is shortest path algorithm that works on un-weighted
graphs.
A. True
B.False

Floyd-Warshall algorithm is a dynamic programming algorithm; the genius of
the algorithm is in the clever recursive formulation of the shortest path
problem.
A. True
B. Flase

Floyd-Warshall algorithm, as in the case with DP algorithms, we avoid
recursive evaluation by generating a table for
A. k
B. d k i
C. True j
D. Flase

The term coloring came from the original application which was in map
drawing.
A. True
B. False

must be each other.
A. Apart from
B. Far from
C. Near to
D. Adjacent to

Fixed-length codes may not be efficient from the perspective of the total
quantity of data.
A. Minimizing
B. Averaging
C. Maximizing
D. Summing

In greedy algorithm, at each phase, you take the you can get right now,
without regard for future consequences.
A. Worst
B. Minimum

C. Good
D.Best

The difference between Prim s algorithm and Dijkstra s algorithm is that
Dijkstra s algorithm uses a same key.
A. True
B.False

If there are n items, there are possible combinations of the items.
A. 2
B. N
C. 2^n
D. 3^n

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.
A. Value
B.Weight
C. Length
D.Balance

The knapsack problem does not belong to the domain of optimization
problems.
A. True
B.False

In Huffman encoding, for a given message string, the frequency of
occurrence (relative probability) of each character in the message is
determined last.
A. True
B.False

Fixed-length codes are known for easy break up of a string into its individual
characters.
A. True
B. False

In Knapsack Problem, value and weight both are to be under consideration.
A. True
B. False

Multiplication is .
A. log n
B. n
C. n2
D. n3

In DP based solution of knapsack problem, to compute entries of V we will
imply a/an approach.
A. Subjective
B. Inductive
C.Brute force
D.Combination

A greedy algorithm sometimes works well for optimization problems.
A. True
B. False

In Huffman encoding, frequency of each character can be determined by
parsing the message and how many times each character (or symbol)
appears.
A. Printing
B. Incrementing
C. Counting
D. Deleting

Greedy algorithm can do very poorly for some problems.
A. True
B. False

The Huffman codes provide a method of data efficiently.
A. Reading
B. Encoding
C. Decoding
D. Printing

In based solution of knapsack problem, we consider 2 cases, Leave object
Or Take object.
A. Brute force
B. Dynamic programming

In brute force based solution of knapsack problem, we consider 2 cases,
Leave object Or Take object.
A. TRUE
B. False

problem, we want to find the best solution.
A. Minimization
B. Averaging
C. Optimization
D. Maximization

Counting Money problem is an example which cannot be optimally solved by
greedy algorithm.
A. True
B. False

Huffman algorithm generates an optimum prefix code.
A. True
B. False

If the string “lmncde” is coded with ASCII code, the message length would
be bits.
A. 24
B. B36
C. 48 6*8=48
D. 60

There are nested loops in DP based algorithm for computing the minimum
cost of chain matrix multiplication.
A. 2
B. 3
C. 4

A number of lectures are to be given in a single lecture hall. Optimum
scheduling for this is an example of Activity selection.
A. True
B. False

The activity scheduling is a simple scheduling problem for which the greedy
algorithm approach provides a/an solution.
A. Simple
B. Sub optimal
C. Optimal
D. Non optimal

The string |xyz|, if coded with ASCII code, the message length would be 24
bits.
A. True (3*8=24)
B. False

An application problem is one in which you want to find, not just a solution,
but the solution.
A. Simple
B. Good
C. Best

Suppose that a graph G = (V,E) is implemented using adjacency lists. What
is the complexity of a breadth-first traversal of G?
A. O(|V |^2)
B. O(|V | |E|)
C. O(|V |^2|E|)
D. O(|v|+|E|)

Which is true statement?
A. Breadth first search is shortest path algorithm that works on un-
weighted graphS
B. Depth first search is shortest path algorithm that works on un-
weighted graphs.
C. Both of above are true.
D. None of above are true.

Using ASCII standard the string “abacdaacacwe” will be encoded with
__________ bits
A. 64
B. 128
C. 96
D. 120

Forward edge is:
A. (u, v) where u is a proper descendent of v in the tree.
B. (u, v) where v is a proper descendent of u in the tree.
C. (u, v) where v is a proper ancesstor of u in the tree.
D. (u, v) where u is a proper ancesstor of v in the tree.

In digraph G=(V,E) ;G has cycle if and only if
A. The DFS forest has forward edge.
B. The DFS forest has back edge
C. The DFS forest has both back and forward edge
D. BFS forest has forward edge

Back edge is:
A. (u, v) where v is an ancestor of u in the tree.
B. (u,v) where u is an ancesstor of v in the tree.
C. (u, v) where v is an predcessor of u in the tree.
D. None of above

Cross edge is :
A. (u, v) where u and v are not ancestor of one another
B. (u, v) where u is ancesstor of v and v is not descendent of u.
C.(u, v) where u and v are not ancestor or descendent of one another
C. (u, v) where u and v are either ancestor or descendent of one another.

Kruskal's algorithm (choose best non-cycle edge) is better than Prim's
(choose best tree edge) when the graph has relatively few edges.
A. True
B. False

What algorithm technique is used in the implementation of Kruskal solution
for the MST?
A. Greedy Technique
B. Divide-and-Conquer Technique
C. Dynamic Programming Technique
D. The algorithm combines more than one of the above techniques

The ___________ given by DFS allow us to determine whether the graph
contains any cycles.
A. Order
B. Time stamps
C. BFS traversing
D. Topological sort

In Prim's algorithm, we will make use of_______________.
A. Priority Queue

___________ technique is look like propagating wave-front outward.
Breath first traversal

What is the time complexity to extract a vertex from the priority queue in
Prim’s algorithm?
A. O (log E)
B. (V)
C. (V+E)
D. O(log V)

The relationship between number of back edges and number of cycles in DFS
is,
A. Both are equal
B. Back edges are half of cycles
C. Back edges are one quarter of cycles
D. There is no relationship between no. of edges and cycles

You have an adjacency list for G, what is the time complexity to compute
Graph transpose G^T.?
A. (V + E)
B. (V E)
C. (V)
D. (V^2)

There is relationship between number of back edges and number of cycles in
DFS
A. Both are equal.
B.Cycles are half of back edges.
C. Cycles are one fourth of back edges.
D. There is no relationship between back edges and number of
cycles.

A digraph is strongly connected under what condition?
A. A digraph is strongly connected if for every pair of vertices u, v e V, u
can reach v .

B.A digraph is strongly connected if for every pair of vertices u, v e
V, u can reach v and vice versa.
B. A digraph is strongly connected if for at least one pair of vertex u, v e
V, u can reach v and vice versa.
C. A digraph is strongly connected if at least one third pair of vertices u,
v e V, u can reach v and vice versa.

In in-place sorting algorithm is one that uses arrays for storage :
A. An additional array
B. No additional array
C.Both of above may be true according to algorithm
D.More than 3 arrays of one dimension.

In stable sorting algorithm
A. One array is used
B. In which duplicating elements are not handled.
C. More than one arrays are required.
D. Duplicating elements remain in same relative position after sorting.

Which sorting algorithm is faster :
A. O(n^2)
B. O(nlogn)
C. O(n+k)
D. O(n^3)

In Quick sort algorithm, constants hidden in T(n lg n) are
A. Large
B. Medium
C. Not known
D. Small

Quick sort is based on divide and conquer paradigm; we divide the problem
on base of pivot element and:
A. There is explicit combine process as well to conquer the solution.
B. No work is needed to combine the sub-arrays, the array is already
sorted
C. Merging the sub arrays

D.None of the above
Dijkstra’s algorithm :
A. Has greedy approach to find all shortest paths
B. Has both greedy and Dynamic approach to find all shortest paths
C. Has greedy approach to compute single source shortest paths to all
other vertices
D. Has both greedy and dynamic approach to compute single source
shortest paths to all other vertices.

Which may be stable sort:
A. Bubble sort
B. Insertion sort
C. Selection sort
D.Both of above

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,
A. linear
B. arithmetic
C. exponent
D. Geometric

Which may be stable sort:
A. Bubble sort
B. Insertion sort
C. Selection sort
D. Both of above

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,
A. linear
B. arithmetic
C. exponent
D. Geometric

How much time merge sort takes for an array of numbers?
A. T(n^2)
B. T(n)
C. T( log n)
D. T(n log n)

We do sorting to,
A. keep elements in random positions
B. keep the algorithm run in linear order
C. keep the algorithm run in (log n) order
D.keep elements in increasing or decreasing order

Dynamic programming algorithms need to store the results of intermediate
sub-problems.
A. True
B. False

Dijkstras single source shortest path algorithm works if all edges weights are
non negative and there are no negative cost cycles.
A. False
B. True

Dijkestra s single source shortest path algorithm works if all edges weights
are negative and there are no negative cost cycles.
A. True
B. False

must be each other.
A. Apart from
B. Far from
C. Near to
D.Adjacent to

Fixed-length codes may not be efficient from the perspective of the total
quantity of data.
A. Minimizing
B.Averaging
C. Maximizing
D. Summing

In based solution of knapsack problem, we consider 2 cases, Leave object
Or Take object.
A. Brute force
B. Dynamic programming

In brute force based solution of knapsack problem, we consider 2 cases,
Leave object Or Take object.
A. TRUE
B. False

problem, we want to find the best solution.
A. Minimization
B. Averaging
C. Optimization
D. Maximization

Using ASCII standard the string abacdaacac will be encoded with 10 bytes.
A. True
B. False

How many elements do we eliminate in each time for the Analysis of
Selection algorithm?
A. (n / 2) + n elements
B. n / 4 elements
C. 2 n elements
D.n / 2 elements

Slow sorting algorithms run in,
A. T(n^2)
B. T(n)
C. T( log n)
D. T(n log n)

Counting sort is suitable to sort the elements in range 1 to k:
A. K is large
B. K is small
C. K may be large or small
D. None

Heaps can be stored in arrays without using any pointers; this is due to the
nature of the binary tree,
A. left-complete
B. right-complete
C. tree nodes
D. tree leaves

A heap is a left-complete binary tree that conforms to the
A. increasing order only
B. heap order
C. decreasing order only
D. (log n) order

Divide-and-conquer as breaking the problem into a small number of
A. pivot
B. Sieve
C. smaller sub problems
D. Selection

In Sieve Technique we do not know which item is of interest
A. True
B. False

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?
A. 16
B. 10
C. 32
D. 31

For the heap sort, access to nodes involves simple
operations.
A. arithmetic
B. binary
C. algebraic
D. logarithmic

For the sieve technique we solve the problem,
A. recursively
B. mathematically
C. precisely
D. accurately

The sieve technique works in as follows
A. phases
B. numbers
C. integers
D. routines

A (an) is a left-complete binary tree that conforms to the heap order
A. heap
B. binary tree
C. binary search tree
D. array

The sieve technique is a special case, where the number of sub problems is
just
A. 5
B. Many
C. 1
D. Few

Analysis of Selection algorithm ends up with,
A. T(n)
B. T(1 / 1 + n)
C. T(n / 2)
D. T((n / 2) + n)

For the heap sort we store the tree nodes in
A. level-order traversal
B. in-order traversal
C. pre-order traversal
D. post-order traversal

The reason for introducing Sieve Technique algorithm is that it illustrates a
very important special case of,
A. divide-and-conquer
B. decrease and conquer
C. greedy nature
D. 2-dimension Maxima

Sieve Technique applies to problems where we are interested in finding a
single item from a larger set of _
A. n items
B. phases
C. pointers
D. constant

Memorization is?
A. To store previous results for future use

B. To avoid this unnecessary repetitions by writing down the results
of recursive calls and looking them up again if we need them later
C. To make the process accurate

Quick sort is
A. Not stable but in place
B. Stable & in place
C. Stable but not in place
D. Some time stable & some times in place

One example of in place but not stable algorithm is
A. Merger Sort
B.Quick Sort
B. Continuation Sort
C. Bubble Sort

Continuation sort is suitable to sort the elements in range 1 to k
A. K is Large
B. K is not known
C. K may be small or large
D.K is small

Which may be a stable sort?
A. Merger
B. Insertion
C. None of the above
D. Both above

An in place sorting algorithm is one that uses arrays for storage
A. Two dimensional arrays
B. More than one array
C. No Additional Array

Continuing sort has time complexity of ?
A. O(n)
B. O(n+k)
C. O(nlogn)
D. O(k)

single item from a larger set of
A. phases
B. n items
C. pointers
D. constant

For the Sieve Technique we take time
A. T(nk)
B. T(n / 3)
C. n^2
D. n/3

Due to left complete nature of binary tree, the heap can be stored in
A. Arrays
B. Structures
C. Link List
D. Stack

What type of instructions Random Access Machine (RAM) can execute?
A. Algebraic and logic
B. Geometric and arithmetic
C. Arithmetic and logic
D. Parallel and recursive

What is the total time to heapify?
A. Ο(log n)
B. Ο(n log n)
C. Ο(n2 log n)
D. Ο(log2 n)

word Algorithm comes from the name of the muslim author
A. Abu Ja’far Mohammad ibn Musa al-Khowarizmi.

Al-Khwarizmi’s work was written in a book titled
A. al Kitab al-mukhatasar ﬁ hisab al-jabr wa’l-muqabalah

Random access machine or RAM is a/an
A. Machine build by Al-Khwarizmi
B. Mechanical machine
C. Electronics machine
D. Mathematical model

A RAM is an idealized machine with _ random-access memory.
A. 256MB
B. 512MB
C. 100GB
D. an infinitely large

What will be the total number of max comparisons if we run brute-force
maxima algorithm with n elements?
A. 2 n
B. 2 n n
C. n
D. 8 n

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.

A. O(n)
B. O(n3)

C. O(n2 log n)
D. O(n2)

Is it possible to sort without making comparisons?
A. Yes
B. No

When we call heapify then at each level the comparison performed takes time
A. It will take Θ (1)
B. Time will vary according to the nature of input data
C. It can not be predicted
D. It will take Θ (log n)

In Quick sort, we don’t have the control over the sizes of recursive calls
A. True
B. False
C. Less information to decide
D. Either true or false

For Chain Matrix Multiplication we cannot use divide and conquer approach
because,
A. We do not know the optimum k
B. We use divide and conquer for sorting only
C. We can easily perform it in linear time
D. Size of data is not given

Suppose we have three items as shown in the following table, and suppose
the capacity of the knapsack is 50 i.e. W = 50.
Item Value Weigh
t
1 60 10
2 100 20
3 120 30
The optimal solution is to pick
A. Items 1 and 2

B. Items 1 and 3
C. Items 2 and 3
D. None of these

who invented the quick sort
A. C.A.R. Hoare

main elements to a divide-and-conquer
A. Divide, conquer, combine

Mergesort is a stable algorithm but not an in-place algorithm.
A. True
B. False

Counting sort the numbers to be sorted are in the range 1 to k where k is
small.
A. True
B. False

In selection algorithm, because we eliminate a constant fraction of the array
with each phase, we get the
A. Convergent geometric series
B. Divergent geometric series
C. None of these

In RAM model instructions are executed
A. One after another
B. Parallel

Due to left-complete nature of binary tree, heaps can be stored in
A. Link list
B. Structure
C. Array
D. None of above

The time assumed for each basic operation to execute on RAM model of
computation is-----
A. Constant
B. Infinite
C. Continuous
D. Variable

If the indices passed to merge sort algorithm are not equal, the algorithm may
return immediately.
A. True
B.False

Brute-force algorithm uses no intelligence in pruning out decisions.
A. True
B. False

In analysis, the Upper Bound means the function grows asymptotically no
faster than its largest term.
A. True
B. False

For small values of n, any algorithm is fast enough. Running time does
become an issue when n gets large
A. True .
B.False

In simple brute-force algorithm, we give no thought to efficiency.
A. True
B. False

The ancient Roman politicians understood an important principle of good
algorithm design that is plan-sweep algorithm.
A. True
B. False

If the indices passed to merge sort algorithm are ,then this means that there is
only one element to sort.
A. Small
B. Large
C. Equal
D. Not Equal

In pseudo code, the level of details depends on intended audience of the
algorithm.
A. True
B. False

In 2d-space a point is said to be _if it is not dominated by any other
point in that space.
A. Member
B. Minimal
C. Maximal
D. Joint

An algorithm is a mathematical entity that is dependent on a specific
programming language.
A. True
B. False

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.
A. TRUE
B. False

F (n) and g (n) are asymptotically equivalent. This means that they have
essentially the same _ for large n.
A. Results
B. Variables
C. Growth rates

D. Size

8n2 + 2n - 3 will eventually exceed c2*(n) no matter how large we make c2.
A. TRUE
B. False

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.
A. Fast
B. Slow
C. Cheap
D. Expensive

While solving Selection problem, in Sieve technique we partition input data
A. In increasing order
B. In decreasing order
C. According to Pivot
D. Randomly

In Sieve Technique, we know the item of interest.
A. True
B. False

In Heap Sort algorithm, we build for ascending sort.
A. Max heap
B. Min heap

Quick sort is best from the perspective of Locality of reference.
A. True
B. False

While Sorting, the ordered domain means for any two input elements x and y
satisfies only.
A. x < y
B. x > y

C. x = y
D. All of the above

Algorithm is a mathematical entity, which is independent of a specific machine
and operating system.
A. True
B. False

In Heap Sort algorithm, the total running time for Heapify procedure is
A. Theta (log n)
B. Order (log n)
C. Omega (log n)
D. O (1)

A point p in 2-dimensional space is usually given by its integer coordinate(s)
A. p.x only p.y
B. only p.x & p.z
C. p.x & p.y

In Heap Sort algorithm, the maximum levels an element can move upward is
A. Theta (log n)
B. Order (log n)
C. Omega (log n)
D. O

Floor and ceiling are to calculate while analyzing algorithms.
A. Very easy
B. Usually considered difficult

is one of the few problems, where provable lower bounds exist on how
fast we can sort.
A. Searching
B. Sorting
C. Both Searching & Sorting
D. Graphing

A RAM is an idealized algorithm with takes an infinitely large random-access
memory.
A. True
B. False

Upper bound requires that there exist positive constants c2 and n0 such that f(n)
c2n for all n <= n0(ye question ghalat lag raha hai mujhae
A. Less than
B. Equal to or Less than
C. Equal or Greater than
D. Greater than

In Heap Sort algorithm, if heap property is violated
A. We call Build heap procedure
B. We call Heapify procedure
C. We ignore
D. Heap property can never be violated

In we have to find rank of an element from given input.
A. Merge sort algorithm
B. Selection problem
C. Brute force technique
D. Plane Sweep algorithm

A point p in 2-dimensional space is usually given by its integer coordinate(s)
A. p.x only
B. p.y only
C. p.x & p.z
D. p.x & p.y

In Quick Sort Constants hidden in T(n log n) are
A. Large
B. Medium
C. Small
D. Not Known

The running time of quick sort depends heavily on the selection of
A. No of inputs
B. Arrangement of elements in array
C. Size o elements
D. Pivot elements

Choose one Counting sort has time complexity:
A. O(n) (Page 58)
B. O(n+k)
C. O(k)
D. O(nlogn)

In place stable sorting algorithm.
A. If duplicate elements remain in the same relative position after
sorting
B. One array is used
C. More than one arrays are required
D. Duplicating elements not handled

Cont sort is suitable to sort the elements in range 1 to k
A. K is Large
B. K is not known
C. K may be small or large
D. K is small

The sieve technique works where we have to find item(s) from a large input.
A. Single
B. Two
C. Three
D. Similar

A RAM is an idealized machine with random-access memory.
A. 256MB
B. 512MB
C. an infinitely large

D. 100GB

A RAM is an idealized machine with random-access memory.
A. 256MB
B. 512MB
C. an infinitely large
D. 100GB

For the sieve technique we solve the problem,
A. recursively
B. mathematically
C. precisely
D. accurately

number of nodes in a complete binary tree of height h is
A. 2^(h+1) – 1
B. 2 * (h+1) – 1
C. 2 * (h+1)
D. ((h+1) ^ 2) – 1 25

Heaps can be stored in arrays without using any pointers; this is due to the
nature of the binary tree,
A. left-complete
B. right-complete
C. tree nodes
D. tree leaves

Sorting is one of the few problems where provable bonds exits on how fast we
can sort,
A. upper
B. lower
C. average
D. log n

The analysis of Selection algorithm shows the total running time is indeed
in no
A. arithmetic
B. geometric
C. linear
D. orthogonal

What algorithm technique is used in the implementation of Kruskal solution for
the MST?
A. Greedy Technique
B. Divide-and-Conquer Technique
C. Dynamic Programming Technique
D. The algorithm combines more than one of the above techniques

one If you find yourself in maze the better traversal approach will be :
A. BFS
B. BFS and DFS both are valid
C. Level order
D. DFS

In digraph G=(V,E) ;G has cycle if and only if
A. The DFS forest has forward edge.
B. The DFS forest has back edge (Page 131)
C. The DFS forest has both back and forward edge
D. BFS forest has forward edge

Suppose that a graph G = (V,E) is implemented using adjacency lists.
What is the complexity of a breadth-first traversal of G?
A. O(|V |^2)
B. O(|V | |E|)
C. O(|V |^2|E|)
D. O(|V | + |E|)

There are nested loops in DP based algorithm for computing the minimum
cost of chain matrix multiplication.

A. 2
B. 3
C. 4
D. 5

Counting Money problem is an example which cannot be optimally solved by
greedy algorithm.
A. True
B. False

Who invented Quick sort procedure?
A. Hoare
B. Sedgewick
C. Mellroy
D. Coreman

An activity scheduling algorithm, the width of a rectangle --.
A. Is always ignored
B. Direct toward recursion
C. Should be maximized
D. Indicates the duration of an activity

In recursive formulation of Knapsack Problem: V [0, j] = for
j>=0
A. -1
B. 0
C. 1
D. 2

The Probability in Huffman encoding is the number of occurrences of a
character divided by the total--------------in the message.
A. Numbers
B. Frequencies
C. Strings
D. Characters

Graphs can be represented by an--------------- and --.
A. queue , stack
B.adjacency list , adjacency matrix
C.adjacency right , adjacency left
D.Binary , linear

Edge weights can be interpreted as distance .
A. in breadth-First Search
B. in Queue's
C. in the shortest-paths
D. in depth-First Search

algorithm allows negative weights edges and no negative cost cycles.
A. Brute-force technique
B. Bellman-Ford
C. Dijkstra’s
D. Print

According to parenthesis lemma vertex u is a descendent of v vertex if and
only if:
A. f [d[u], f[u]] ⊆ [d[v], f[v]] (Page 129)

There exist a unique path between any ________ vertices of a free tree.
A. Two

Keeping in mind the shortest-path, if given scenarios occur in computer
networks like the internet where data packets have to be routed. The vertices
are_________and Edges are _____________which may be wired or wireless.
A. Routers, communication links

In undirected graph, by convention all the edges are called _________ edges.
A. back

Bellman-Ford algorithm is slower than_______________.
A. Dijkstra’s

From the given option’s which one is correct regarding the time complexity of
Dijkstra’s algorithm:
A. O(N^2)

In the shortest-paths problem, we are given a weighted of___________G = (V,
E).
A. Un-directed graph

You have an adjacency list for G, what is the time complexity to compute
Graph transpose G^T ?
A. (V+E)

If you find yourself in maze the better traversel approach will be :
A. BFS
B. BFS and DFS both are valid
C. Level order
D. DFS

In strong components algorithm, first of all DFS is run for computing finish
times of vertices.
A. [d[u], f[u]]⊆[d[v], f[v]]
B. [d[u], f[u]]⊇[d[v], f[v]]
C. unrelated
D. Disjoint

The relationship between number of back edges and number of cycles in DFS
is,
A. Both are equal
B. Back edges are half of cycles
C. Back edges are one quarter of cycles
D. There is no relationship between no. of edges and cycles

What general property of the list indicates that the graph has an isolated
vertex?
A. There is Null pointer at the end of list.
B. The Isolated vertex is not handled in list.
C. Only one value is entered in the list.
D. There is at least one null list.

As the Kruskal’s runs, the edges in viable set A induce a _________ on the
vertices.
A. Set
B. Graph
C. Tree
D. Fore
Visit My YouTube Channel

For More Important Notes
Channel Name = #VuTopperRM

CS502 Mcq's FinalTerm by Vu Topper RM

Uploaded by

Copyright:

Available Formats

CS502 Mcq's FinalTerm by Vu Topper RM

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CS502 Mcq's FinalTerm by Vu Topper RM

Uploaded by

Copyright:

Available Formats

CS502 Fundamentals Of Algorithms

Update MCQS For FinalTerm

For More Help Contact What’s app 03224021365

Question No:02 (Marks:01) Vu-Topper RM

Question No:03 (Marks:01) Vu-Topper RM

Question No:04 (Marks:01) Vu-Topper RM

Question No:05 (Marks:01) Vu-Topper RM

Question No:06 (Marks:01) Vu-Topper RM

For More Help Contact What’s app 03224021365

Question No:07 (Marks:01) Vu-Topper RM

Question No:08 (Marks:01) Vu-Topper RM

Question No:09 (Marks:01) Vu-Topper RM

Question No:10 (Marks:01) Vu-Topper RM

Question No:11 (Marks:01) Vu-Topper RM

Question No:12 (Marks:01) Vu-Topper RM

Question No:13 (Marks:01) Vu-Topper RM

For More Help Contact What’s app 03224021365

Question No:14 (Marks:01) Vu-Topper RM

Question No:15 (Marks:01) Vu-Topper RM

Question No:16 (Marks:01) Vu-Topper RM

Question No:17 (Marks:01) Vu-Topper RM

Question No:18 (Marks:01) Vu-Topper RM

For More Help Contact What’s app 03224021365

Question No:19 (Marks:01) Vu-Topper RM

Question No:20 (Marks:01) Vu-Topper RM

Question No:21 (Marks:01) Vu-Topper RM

Question No:22 (Marks:01) Vu-Topper RM

Question No:23 (Marks:01) Vu-Topper RM

For More Help Contact What’s app 03224021365

Question No:25 (Marks:01) Vu-Topper RM

Question No:26 (Marks:01) Vu-Topper RM

Question No:27 (Marks:01) Vu-Topper RM

Question No:28 (Marks:01) Vu-Topper RM

For More Help Contact What’s app 03224021365

Question No:30 (Marks:01) Vu-Topper RM

Question No:31 (Marks:01) Vu-Topper RM

Question No:32 (Marks:01) Vu-Topper RM

Question No:33 (Marks:01) Vu-Topper RM

For More Help Contact What’s app 03224021365

Question No:35 (Marks:01) Vu-Topper RM

Question No:36 (Marks:01) Vu-Topper RM

Question No:37 (Marks:01) Vu-Topper RM

Question No:38 (Marks:01) Vu-Topper RM

For More Help Contact What’s app 03224021365

Question No:39 (Marks:01) Vu-Topper RM

Question No:40 (Marks:01) Vu-Topper RM

Question No:41 (Marks:01) Vu-Topper RM

Question No:42 (Marks:01) Vu-Topper RM

Question No:43 (Marks:01) Vu-Topper RM

For More Help Contact What’s app 03224021365

Question No:45 (Marks:01) Vu-Topper RM

Question No:46 (Marks:01) Vu-Topper RM

Question No:47 (Marks:01) Vu-Topper RM

Question No:48 (Marks:01) Vu-Topper RM

For More Help Contact What’s app 03224021365

Question No:50 (Marks:01) Vu-Topper RM

Question No:51 (Marks:01) Vu-Topper RM

Question No:52 (Marks:01) Vu-Topper RM

Question No:53 (Marks:01) Vu-Topper RM

Question No:54 (Marks:01) Vu-Topper RM