Design and Analysis of Algorithm MCQ Unit-IV

 

Unit -IV

1.      Which of the following is/are property/properties of a dynamic programming problem?

A.    Optimal substructure

B.     Overlapping sub-problems

C.     Greedy approach 
 D.    Both optimal substructure and overlapping sub-problems
 
2.      When a top-down approach of dynamic programming is applied to a problem, it usually _____________
A.    Decreases both, the time complexity and the space complexity
B.     Decreases the time complexity and increases the space complexity
C.     Increases the time complexity and decreases the space complexity
D.    Increases both, the time complexity and the space complexity
 
3.      Time complexity of the 0/1 Knapsack problem
A.    O(n)
B.     O(n!)
C.    O(2^n) 
D.    O(n³)
 
4.      I: Greedy algorithm is more efficient in terms of memory as it never look back or revises previous choice.II: Dynamic Programming requires table for memorization and it increases it’s memory complexity.
A.    Only I is correct
B.     Only II is correct
C.    Both are correct
D.    Both are not correct
 
5.      I: A Greedy method follows the problem solving heuristic of making the locally optimal choice at each stage.
II: A Dynamic programming is an algorithmic technique not uses some previously calculated states.
A.    Only I is correct
B.     Only II is correct
C.     Both are correct
D.    Both are not correct

6.     

I: Greedy algorithm is one which finds the optimal solution at every stage with the hope of finding global optimum solution.

II: Dynamic programming is one which breaks up the problem into series of overlapping sub-problems.
A.    Only I is correct
B.     Only II is correct
C.     Both are correct
D.    Both are not correct
 
7.      We use dynamic programming approach when
A.    We need an optimal solution
B.     The solution has optimal substructure
C.     The given problem can be reduced to the 3-SAT problem
D.    It's faster than Greedy
 
8.      Time complexity of Huffman Coding is
A.    n
B.     n log n
C.     n log n²
D.    n²
 
9.     

I:Huffman coding may become lossy in some cases 

II: In Huffman coding, no code is prefix of any other code.
A.    Only I is correct
B.     Only II is correct
C.     Both are correct
D.    Both are not correct
 
 
10.  Number of comparisons requires merging files by optimal merge pattern, f1, f2, f3, f4 and f5 with 20, 30, 10, 5 and 30 numbers of elements respectively.
A.    205
B.     210
C.     200
D.    95
 
 
11.  Time Complexity of job sequencing problem
A.    O(n)
B.     O(nlogn)
C.     O(nlogn²)
D.    O(n²)
 
 
12.  Which of the following algorithms is the best approach for solving Huffman codes?
A.    exhaustive search
B.     greedy algorithm
C.     brute force algorithm
D.    divide and conquer algorithm
 
 
13.  The type of encoding where no character code is the prefix of another character code is called?
A.    optimal encoding
B.     prefix encoding
C.     frequency encoding
D.    trie encoding
 
 
14.  job sequencing with deadline is based on ____________method
A.    Greedy Method
B.     Branch and Bound
C.     Dynamic Programming
D.    Divide and Conquer
 
 
15.  If an optimal solution can be created for a problem by constructing optimal solutions for its subproblems, the problem possesses ____________ property.
A.    Overlapping subproblems
B.     Optimal substructure
C.     Memoization
D.    Greedy
 
 
16.  Which of the following is/are property/properties of a dynamic programming problem?
A.    Optimal substructure
B.     Overlapping subproblems
C.     Greedy approach
D.    Both optimal substructure and overlapping subproblems
 
 
17.  Consider the recursive implementation to find the nth fibonacci number: int fibo(int n) if n <= 1 return n return __________ Which line would make the implementation complete?
A.    fibo(n) + fibo(n)
B.     fibo(n) + fibo(n – 1)
C.     fibo(n – 1) + fibo(n + 1)
D.    fibo(n – 1) + fibo(n – 2)
 
 
18.  you are given infinite coins of denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. This problem can be solved using ____________
A.    Greedy algorithm
B.     Dynamic programming
C.     Divide and conquer
D.    Backtracking
 
 
19.  The characters a to h have the set of frequencies based on the first 8 Fibonacci numbers as follows:a : 1, b : 1, c : 2, d : 3, e : 5, f : 8, g : 13, h : 21A Huffman code is used to represent the characters. What is the sequence of characters corresponding to the following code?110111100111010
A.    fdheg
B.     ecgdf
C.     dchfg
D.    fehdg
 
 
20.  You are given infinite coins of denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. This problem can be solved using ____________
A.    Greedy algorithm
B.     Dynamic programming
C.     Divide and conquer
D.    Backtracking
 
21.  Suppose you have coins of denominations 1, 3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm NOT produce an optimal answer?
A.    20
B.     12
C.     6
D.    5
 
 
22.  Given a one-dimensional array of integers, you have to find a sub-array with maximum sum. This is the maximum sub-array sum problem. Which of these methods can be used to solve the problem?
A.    Dynamic programming
B.     Two for loops (naive method)
C.     Divide and conquer
D.    Dynamic programming, naïve method and Divide and conquer methods
 
 
23.  In how many directions do queens attack each other?
A.    1
B.     2
C.    3
D.    4
 
 
24.  Where is the n-queens problem implemented?
A.    carom
B.     chess
C.    ludo
D.    cards
 
 
25.  Total number of enumerations required for a 0-1 knapsack problem with 5 binary variables will be
A.    10
B.     16
C.     25
D.    32
 
 
26.  Which one of the following statement is not true about Exhaustive enumeration technique for solving Integer Linear Programming problems?
A.    Exhaustive enumenration generates all possible integer solutions
B.     Exhaustive enumenration evaluates all possible integer solutions
C.     Exhaustive enumenration chooses the optimal among all possible integer solutions
D.    Exhaustive enumenration cannot gurantee an optimal solution
 
 
27.  While finding optimal solution for a Travelling Salesman problem, sub-tours are to be blocked because:
A.    All sub-tours cannot be found
B.     Some sub-tours are not possible to cover
C.     Travelling Salesman problem considers only some sub-tours, not all
D.    Travelling Salesman problem considers only complete tours, not sub-tours
 
 
28.  It is known that solution of the corresponding Assignment Problem provides a bound for aTravelling Solution Problem. Hence, the optimal solution for a Travelling Salesman Problem and thecorresponding Assignment problem will be:
A.    Always same
B.     Always different
C.    Sometime same
D.    Not related at all
 
 
29.  Consider the Travelling Salesman Problem of Question 10. In order to solve the problem, weneed to replace distance between A to A, B to B, C to C, and D to D by:
A.    0
B.     Lowest distance in the matrix
C.     Highest distance in the matrix
D.    A very high value M
 
30. 

I : Objective job sequencing problem, to find a sequence of jobs, which is completed within their deadlines and gives maximum profit.
II. Objective of optimal merge patterns, Merge a set of sorted files of different length into a single sorted file
A.    Only I is correct
B.     Only II is correct
C.     Both are correct

D.    Both are not correct

 

 

Design and Analysis MCQ Unit- III

 

Unit-III

1.      How many directions do queens attack each other?

A.    4
B.     2
C.    3

D.    5

2.      State space is
A.       All paths from root to other nodes define the state space of the problem
B.        Are rules, which restrict, each vector element to be chosen from given set
C.        All rules which determine which tuples in the solution space satisfy the criterion function

D.       None of these

 

3.      Explicit Constraints is

A.    All paths from root to other nodes define the state space of the problem

B.     Are rules, which restrict, each vector element to be chosen from given set

C.     All rules which determine which tuples in the solution space satisfy the criterion function
D.    None of these

 

4.      Which one not returns optimal solution?

A.    Backtracking

B.     Dynamic Programming
C.     Branch and Bounding

D.    Greedy Method

 

5.      Statement- I: Backtracking involves feasibility function.   
    Statement-II: Branch-and-Bound involves a bounding function.
    Statement III: Branch-and-Bound traverses the tree in any manner, DFS or BFS.Statement IV:             Backtracking traverses the state space tree by DFS[Depth First Search] manner.

A.    All are Correct
B.     Only IV is Wrong
C.     Only III is Wrong
D.    Only I,II is Wrong

 

6.      Which of the problems can be solved by backtracking method?

A.    4-queen problem
B.     insertion sort
C.     Travelling Salesman Problem
D.    Merge sort
 

7.      Backtracking is

A.    Depth first search with some bounding function
B.     Depth first search no bounding function
C.     Breath first search with some bounding function
D.    Breath first search no bounding function
 

 8.      Minimum number of unique colors required for vertex coloring of a graph is called?

 
A.    vertex matching
B.     chromatic number
C.     chromatic index
D.    color number
 
 
9.      Backtracking algorithm is
A.    Depth first search with some bounding function
B.     Depth first search no bounding function
C.     Breath first search with some bounding function
D.    Breath first search no bounding function
 
10.  Which of the problems can be solved by backtracking method?
A.    4-queen problem
B.     insertion sort
C.     Travelling Salesman Problem
D.    Merge sort
 
11.  Which one not returns optimal solution?
A.    Backtracking
B.     Dynamic Programming
C.     Branch and Bounding
D.    Greedy Method
 
12.  Backtracking used to solve
A.    Logical problems
B.     Exhaustive search
C.     Arithmetic problems
D.    Combinatorial problems
 
13.  What is vertex coloring of a graph?
 
A.     A condition where any two vertices having a common edge should always have same color.
B.     A condition where any two vertices having a common edge should not have same color.
C.     A condition where all vertices should have a different color.
D.    A condition where all vertices should have same color.
 
14.  Which one provides an optimal solution for 4-queens problem?
A.    (2,3,1,4)
B.     (4,3,2,1)
C.     (4,2,3,1)
D.    (3,1,4,2)
 
15.  Branch and bound is a __________
A.    problem solving technique
B.     data structure
C.     sorting algorithm
D.    type of tree
 
 
16.  Which of the following can traverse the state space tree only in DFS manner?
A.    branch and bound
B.     dynamic programming
C.     greedy algorithm
D.    backtracking
 
 
17.  Choose the correct statement from the following.
A.    branch and bound is more efficient than backtracking
B.     branch and bound is not suitable where a greedy algorithm is not applicable
C.    branch and bound divides a problem into at least 2 new restricted sub problems
D.    backtracking divides a problem into at least 2 new restricted sub problems
 
 
18.  The travelling salesman problem can be solved using _________
A.    A spanning tree
B.     A minimum spanning tree
C.     Bellman – Ford algorithm
D.    DFS traversal
 
19.  Which of the problems cannot be solved by backtracking method?
A.    n-queen problem
B.     subset sum problem
C.     Hamiltonian circuit problem
D.    travelling salesman problem
 
 
20.  Backtracking algorithm is implemented by constructing a tree of choices called as?
A.    State-space tree
B.     State-chart tree
C.     Node tree
D.    Backtracking tree
 
 
21.  What happens when the backtracking algorithm reaches a complete solution?
A.    It backtracks to the root
B.     It continues searching for other possible solutions
C.     It traverses from a different route
D. Recursively traverses through the same route
 
 
22.  In what manner is a state-space tree for a backtracking algorithm constructed?
A.    Depth-first search
B.     Breadth-first search
C.     Twice around the tree
D.    Nearest neighbour first
 
 
23.  The problem of placing n queens in a chessboard such that no two queens attack each other is called as?
A.    n-queen problem
B.     eight queens puzzle
C.     four queens puzzle
D.    1-queen problem
    
 
24.  For how many queens was the extended version of Eight Queen Puzzle applicable for n*n squares?
A.    5
B.     6
C.     8
D.    n
 
25.  What is the condition for proper coloring of a graph?
A.    two vertices having a common edge should not have same color
B.     two vertices having a common edge should always have same color
C.     all vertices should have a different color
D.    all vertices should have same color
 
 
26.  The number of colors used by a proper coloring graph is called?
A.    k coloring graph
B.     x coloring graph
C.     m coloring graph
D.    n coloring graph
 
 
27.  What is a chromatic number?
A.    The maximum number of colors required for proper edge coloring of graph
B.     The maximum number of colors required for proper vertex coloring of graph
C.    The minimum number of colors required for proper vertex coloring of graph
D.    The minimum number of colors required for proper edge coloring of graph
 
28.  What will be the chromatic number for an empty graph having n vertices?
A.    0
B.     1
C.     2
D.    n
 
29.  What will be the chromatic number for an bipartite graph having n vertices?
A.0
B.1
C.2
D. n
 
 
30.  What will be the chromatic number for a line graph having n vertices?
A.0
B.1
C.2

D.n