Dynamic Programming In Data Structures - Study Mode

Show All Answers

[#56] 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

Correct Answer

(C) 6

[#57] Find the maximum sub-array sum for the following array: {3, 6, 7, 9, 3, 8}

(A) 33

(B) 36

(C) 23

(D) 26

Correct Answer

(B) 36

[#58] You are given a boolean expression which consists of operators &, | and ∧ (AND, OR and XOR) and symbols T or F (true or false). You have to find the number of ways in which the symbols can be parenthesized so that the expression evaluates to true. This is the boolean parenthesization problem. Which of the following methods can be used to solve the problem?

(A) Dynamic programming

(B) Recursion

(C) Brute force

(D) Dynamic programming, Recursion and Brute force

Correct Answer

(D) Dynamic programming, Recursion and Brute force

[#59] If a problem can be broken into subproblems which are reused several times, the problem possesses . . . . . . . . property.

(A) Overlapping subproblems

(B) Optimal substructure

(C) Memoization

(D) Greedy

Correct Answer

(A) Overlapping subproblems

[#60] 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, naive method and Divide and conquer methods

Correct Answer

(D) Dynamic programming, naive method and Divide and conquer methods