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