Back to Subject

Unit 5: Dynamic Programming Problems - Practice Quiz

CSE330 — Competitive Coding Approaches-Techniques 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 What is an increasing subsequence of an array?

Longest increasing subsequence Easy
A. A subarray containing only distinct elements
B. A subsequence whose elements are in decreasing order
C. A subsequence whose elements are in increasing order
D. A subarray containing only positive elements

2 What is the length of the LIS in the sequence ?

Longest Increasing Subsequence (LIS) Easy
A.
B.
C.
D.

3 Which of the following is an increasing subsequence of ?

Longest increasing subsequence Easy
A.
B.
C.
D.

4 What does LCS stand for?

Longest Common Subsequence (LCS) Easy
A. Longest Consecutive Subarray
B. Longest Common Subsequence
C. Largest Continuous Sequence
D. Least Common Subarray

5 Which sequence is a common subsequence of and ?

Longest common subsequence Easy
A.
B.
C.
D.

6 What is the length of the LCS of and ?

Longest Common Subsequence (LCS) Easy
A.
B.
C.
D.

7 What does the binomial coefficient count?

Binomial coefficient Easy
A. Ways to order distinct objects
B. Ways to add objects to
C. Ways to choose objects from
D. Ways to divide by

8 What is the value of ?

Binomial coefficient Easy
A.
B.
C.
D.

9 What is the usual objective of the Box Stacking problem?

Box Stacking Easy
A. Minimize the number of available boxes
B. Minimize the weight of the stack
C. Maximize the height of a valid stack
D. Maximize the width of every box

10 When can one box normally be placed on another in the Box Stacking problem?

Box Stacking Easy
A. Its height equals the lower box's height
B. Its volume equals the lower box's volume
C. Its base is strictly smaller in both dimensions
D. Its base is strictly larger in both dimensions

11 What does "duplicate items forbidden" mean in the integer knapsack problem?

Integer Knapsack Problem (Duplicate Items Forbidden) Easy
A. Each item may be selected at most once
B. Only items with equal weights are selected
C. Each item must be selected exactly twice
D. Only items with distinct values are selected

12 What is the main objective of the knapsack problem?

Integer Knapsack Problem (Duplicate Items Forbidden) Easy
A. Minimize capacity without selecting items
B. Minimize value while filling the knapsack
C. Maximize weight without considering value
D. Maximize value without exceeding capacity

13 Which operation is commonly allowed in the standard Edit Distance problem?

Edit Distance Easy
A. Insert a character
B. Reverse the whole string
C. Sort all characters
D. Duplicate the whole string

14 What is the edit distance between and ?

Edit Distance Easy
A.
B.
C.
D.

15 What does the Matrix Chain Multiplication problem seek to minimize?

Matrix Chain Multiplication Easy
A. The number of scalar multiplications
B. The number of rows in each matrix
C. The number of matrices in the chain
D. The number of stored matrix elements

16 Multiplying a matrix of size by a matrix of size requires how many scalar multiplications?

Matrix Chain Multiplication Easy
A.
B.
C.
D.

17 What is the goal of a Balanced Partition problem?

Balanced Partition Easy
A. Remove every element with an odd value
B. Place all elements into one large subset
C. Split elements into subsets with close sums
D. Arrange elements in strictly increasing order

18 Which pair of subsets forms a perfectly balanced partition of ?

Balanced Partition Problem Easy
A. and
B. and
C. and
D. and

19 If two partition subsets have sums and , what is the difference between their sums?

Balanced Partition Easy
A.
B.
C.
D.

20 When is a partition considered perfectly balanced?

Balanced Partition Problem Easy
A. The two subsets contain only even values
B. The two subsets have equal total sums
C. The two subsets contain identical elements
D. The two subsets have increasing elements

21 What is the length of the longest strictly increasing subsequence in the sequence ?

Longest increasing subsequence Medium
A.
B.
C.
D.

22 In the LIS algorithm, what does the array of tail values represent?

Longest Increasing Subsequence (LIS) Medium
A. The number of subsequences ending at each index
B. The largest tail for each subsequence length
C. The smallest tail for each subsequence length
D. The predecessor index of every array element

23 For a strictly increasing subsequence, what is the LIS length of ?

Longest Increasing Subsequence (LIS) Medium
A.
B.
C.
D.

24 What is the length of the LCS of the strings AGGTAB and GXTXAYB?

Longest common subsequence Medium
A.
B.
C.
D.

25 If , which recurrence correctly computes the LCS table entry ?

Longest Common Subsequence (LCS) Medium
A.
B.
C.
D.

26 Which sequence is an LCS of ABCDGH and AEDFHR?

Longest Common Subsequence (LCS) Medium
A. ADH
B. DFR
C. BDH
D. AEH

27 Using the recurrence , what is ?

Binomial coefficient Medium
A.
B.
C.
D.

28 When computing binomial coefficients with a one-dimensional DP array, why should be processed from right to left for each new value of ?

Binomial coefficient Medium
A. To eliminate the base case at
B. To reduce multiplication overflow
C. To sort coefficients in decreasing order
D. To preserve values from the previous row

29 A box orientation has base dimensions . Which box orientation can be placed directly on top of it under the strict box-stacking rule?

Box Stacking Medium
A. Base
B. Base
C. Base
D. Base

30 After generating all valid rotations in the standard box-stacking DP, why are orientations commonly sorted by decreasing base area?

Box Stacking Medium
A. To guarantee equal base dimensions are stacked together
B. To minimize the number of rotations generated
C. To process larger supporting bases before smaller bases
D. To ensure every box uses its shortest side as height

31 A knapsack has capacity . Items have (weight, value) pairs , , , and . What is the maximum obtainable value?

Integer Knapsack Problem (Duplicate Items Forbidden) Medium
A.
B.
C.
D.

32 In a one-dimensional knapsack DP, in which order should capacities be updated for each item?

Integer Knapsack Problem (Duplicate Items Forbidden) Medium
A. From zero up to item value
B. From item weight up to capacity
C. From capacity down to item weight
D. From item value down to zero

33 With unit-cost insertion, deletion, and substitution, what is the edit distance between kitten and sitting?

Edit Distance Medium
A.
B.
C.
D.

34 Suppose insertion and deletion each cost , while substitution costs . What is the minimum cost to transform cat into cut?

Edit Distance Medium
A.
B.
C.
D.

35 Matrices , , and have dimensions , , and . What is the minimum number of scalar multiplications?

Matrix Chain Multiplication Medium
A.
B.
C.
D.

36 For five matrices, how many nontrivial contiguous matrix-chain subproblems are stored in the upper triangular portion of the standard DP table?

Matrix Chain Multiplication Medium
A.
B.
C.
D.

37 If matrix has dimensions , what multiplication cost is added when splitting the chain after ?

Matrix Chain Multiplication Medium
A.
B.
C.
D.

38 What is the minimum difference between subset sums when partitioning into two subsets?

Balanced Partition Medium
A.
B.
C.
D.

39 For positive integers with total sum , which subset sum should a balanced-partition DP try to maximize?

Balanced Partition Problem Medium
A. A reachable sum equal to the largest item
B. A reachable sum at most
C. A reachable sum at least
D. A reachable sum at most

40 What is the minimum partition difference for the array ?

Balanced Partition Problem Medium
A.
B.
C.
D.

41 For the sequence , how many distinct index-based longest strictly increasing subsequences exist?

Longest increasing subsequence Hard
A.
B.
C.
D.

42 After processing with the tails-array LIS algorithm, the tails array is . Which interpretation is correct?

Longest Increasing Subsequence (LIS) Hard
A. It is an LIS of the input
B. It stores minimum tails by length
C. It stores maximum tails by length
D. It stores the earliest LIS found

43 An LIS implementation replaces the first tails-array element that is greater than or equal to the current value. What change is required to compute the longest nondecreasing subsequence instead?

Longest increasing subsequence Hard
A. Replace the first element smaller than the value
B. Replace the last element equal to the value
C. Replace the last element greater than the value
D. Replace the first element greater than the value

44 How many distinct longest common subsequence strings do and have?

Longest common subsequence Hard
A.
B.
C.
D.

45 Suppose only insertions and deletions are allowed when transforming a string of length into a string of length . If their LCS length is , what is the minimum number of operations?

Longest Common Subsequence (LCS) Hard
A.
B.
C.
D.

46 A standard LCS reconstruction encounters a state where moving up and moving left preserve the same optimal length. What is necessary to guarantee the lexicographically smallest LCS?

Longest common subsequence Hard
A. Choose the path with fewer diagonal moves
B. Always move up at every tie
C. Always move left at every tie
D. Compare optimal suffix results at ties

47 Using Lucas's theorem, what is ?

Binomial coefficient Hard
A.
B.
C.
D.

48 A one-dimensional DP computes using . In what order must be processed for each new row?

Binomial coefficient Hard
A. Ascending from to
B. Ascending from to
C. Descending from to
D. Descending from to

49 Which expression gives the correct asymptotic growth of the central binomial coefficient ?

Binomial coefficient Hard
A.
B.
C.
D.

50 For each box orientation, normalize its base as . Under strict two-dimensional fitting, which graph formulation correctly represents the unrestricted box-stacking DP?

Box Stacking Hard
A. A DAG edge between bases having equal area
B. An undirected edge between any comparable bases
C. A DAG edge from a taller box to a shorter box
D. A DAG edge from a larger base to a smaller base

51 Why is ordinary longest-path DP over all box rotations insufficient when each physical box may be used at most once?

Box Stacking Hard
A. A path may use two rotations of one box
B. Rotations can produce negative box heights
C. Strict fitting makes the graph cyclic
D. Base normalization changes the box volume

52 In a one-dimensional knapsack DP, why must capacities be processed from down to the current item's weight?

Integer Knapsack Problem (Duplicate Items Forbidden) Hard
A. To exclude states below the capacity
B. To prevent reusing the current item
C. To maintain values in sorted order
D. To prefer items with larger weights

53 A knapsack has capacity and items equal to , , , and . What is the maximum value?

Integer Knapsack Problem (Duplicate Items Forbidden) Hard
A.
B.
C.
D.

54 Insertion and deletion each cost , while replacement costs . What is the minimum weighted edit distance from to ?

Edit Distance Hard
A.
B.
C.
D.

55 A rolling-row edit-distance implementation uses memory. What additional requirement prevents direct reconstruction of an optimal edit script from only the final rolling rows?

Edit Distance Hard
A. Sorted characters in both input strings
B. Predecessor decisions for discarded states
C. Equal lengths for both input strings
D. Symmetric insertion and deletion costs

56 Matrices have dimensions , , , and . What is the minimum number of scalar multiplications?

Matrix Chain Multiplication Hard
A.
B.
C.
D.

57 For a chain of compatible matrices, how many complete parenthesizations must a brute-force method potentially consider before using cost-based pruning?

Matrix Chain Multiplication Hard
A.
B.
C.
D.

58 For nonnegative integers with total sum , which subset-sum objective directly yields the minimum possible difference between two partition sums?

Balanced Partition Hard
A. Minimize reachable
B. Maximize reachable
C. Maximize reachable
D. Minimize reachable

59 The usual bitset solution for balanced partition indexes reachable sums from to . What modification is required if negative input values are allowed?

Balanced Partition Problem Hard
A. Discard all values smaller than zero
B. Replace each value by its absolute value
C. Offset indices across the full sum range
D. Sort values by their absolute magnitudes

60 For the multiset , what is the minimum absolute difference between the sums of two partitions?

Balanced Partition Problem Hard
A.
B.
C.
D.
Previous MCQ
Unit 4
Next MCQ
Unit 6