1What is the main idea behind dynamic programming?
General method
Easy
A.Sort all input values first
B.Try only random candidate solutions
C.Store and reuse subproblem solutions
D.Avoid dividing the original problem
Correct Answer: Store and reuse subproblem solutions
Explanation:
Dynamic programming solves subproblems and stores their results so they do not need to be solved repeatedly.
Incorrect! Try again.
2Which property means that a problem contains repeatedly occurring subproblems?
General method
Easy
A.Overlapping subproblems
B.Greedy-choice property
C.Stable ordering
D.Independent variables
Correct Answer: Overlapping subproblems
Explanation:
Overlapping subproblems occur when the same smaller problems are solved multiple times.
Incorrect! Try again.
3Which property allows an optimal solution to be constructed from optimal solutions to smaller subproblems?
General method
Easy
A.Linear ordering
B.Randomized selection
C.Optimal substructure
D.Input independence
Correct Answer: Optimal substructure
Explanation:
Optimal substructure means that an optimal solution contains optimal solutions to its subproblems.
Incorrect! Try again.
4What is memoization in dynamic programming?
General method
Easy
A.A greedy method that chooses locally
B.A recursive method that discards results
C.A top-down method that caches results
D.A bottom-up method that sorts inputs
Correct Answer: A top-down method that caches results
Explanation:
Memoization uses recursion and saves computed subproblem results for later reuse.
Incorrect! Try again.
5What is tabulation in dynamic programming?
General method
Easy
A.Generating solutions in random order
B.Selecting the largest input each time
C.Filling a table from smaller subproblems
D.Calling recursion without storing results
Correct Answer: Filling a table from smaller subproblems
Explanation:
Tabulation is a bottom-up technique that fills a table using previously computed smaller cases.
Incorrect! Try again.
6Why does dynamic programming commonly use a table?
General method
Easy
A.To reorder source code
B.To store subproblem results
C.To remove all input values
D.To generate random choices
Correct Answer: To store subproblem results
Explanation:
The table records solutions to subproblems so they can be reused efficiently.
Incorrect! Try again.
7Which statement describes Bellman's principle of optimality?
General method
Easy
A.An optimal solution includes optimal subsolutions
B.Every local choice produces a global optimum
C.Every problem requires exhaustive enumeration
D.An optimal solution uses no stored values
Correct Answer: An optimal solution includes optimal subsolutions
Explanation:
Bellman's principle states that the remaining decisions of an optimal solution must also be optimal for the resulting subproblem.
Incorrect! Try again.
8What is optimized in the chained matrix multiplication problem?
Chained matrix multiplication
Easy
A.The number of scalar multiplications
B.The number of matrices in the chain
C.The dimensions of every matrix
D.The values stored in the matrices
Correct Answer: The number of scalar multiplications
Explanation:
The problem finds a parenthesization that minimizes the total number of scalar multiplications.
Incorrect! Try again.
9What can change when a matrix chain is parenthesized differently?
Chained matrix multiplication
Easy
A.The final matrix dimensions
B.The scalar multiplication cost
C.The order of matrix entries
D.The number of input matrices
Correct Answer: The scalar multiplication cost
Explanation:
Different parenthesizations produce the same result but may require different numbers of scalar multiplications.
Incorrect! Try again.
10How many matrix multiplication operations are required to multiply a chain of matrices?
Chained matrix multiplication
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
Combining matrices into one product requires exactly matrix multiplication operations.
Incorrect! Try again.
11What is the cost of multiplying a matrix by a matrix using the standard method?
Chained matrix multiplication
Easy
A. scalar multiplications
B. scalar multiplications
C. scalar multiplications
D. scalar multiplications
Correct Answer: scalar multiplications
Explanation:
The resulting matrix has entries, and each entry requires scalar multiplications, giving .
Incorrect! Try again.
12What is the scalar multiplication cost of multiplying a matrix by a matrix?
Chained matrix multiplication
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
The cost is scalar multiplications.
Incorrect! Try again.
13In matrix-chain dynamic programming, what does the base case equal?
Chained matrix multiplication
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
A single matrix requires no matrix multiplication, so its multiplication cost is .
Incorrect! Try again.
14What is the usual time complexity of the dynamic programming algorithm for matrix-chain multiplication?
Chained matrix multiplication
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
The standard algorithm considers chain lengths, starting positions, and split positions, resulting in time.
Incorrect! Try again.
15What is the main objective of optimal storage on tapes?
Optimal storage on tapes
Easy
A.Minimize mean retrieval time
B.Maximize individual file size
C.Maximize total tape length
D.Minimize the number of files
Correct Answer: Minimize mean retrieval time
Explanation:
Optimal tape storage arranges files so that their average retrieval time is as small as possible.
Incorrect! Try again.
16For files with equal retrieval probabilities, how should files be ordered on one tape?
Optimal storage on tapes
Easy
A.In decreasing order of length
B.In increasing order of length
C.In random order of position
D.In alphabetical order of name
Correct Answer: In increasing order of length
Explanation:
Placing shorter files first minimizes the cumulative access times and therefore the mean retrieval time.
Incorrect! Try again.
17Which file should be placed first when file lengths are , , and units and access probabilities are equal?
Optimal storage on tapes
Easy
A.The file of length
B.The file of length
C.Any file in the collection
D.The file of length
Correct Answer: The file of length
Explanation:
With equal access probabilities, files are stored in increasing order of length, so the length- file comes first.
Incorrect! Try again.
18If files of lengths , , and are stored in that order, what is the retrieval time of the third file?
Optimal storage on tapes
Easy
A. units
B. units
C. units
D. units
Correct Answer: units
Explanation:
The third file is reached after passing through all three files, so its retrieval time is units.
Incorrect! Try again.
19For files of lengths , , and stored in that order, what is the mean retrieval time?
Optimal storage on tapes
Easy
A. units
B. units
C. units
D. units
Correct Answer: units
Explanation:
The retrieval times are , , and , so the mean is units.
Incorrect! Try again.
20Why are shorter files generally placed before longer files on a tape?
Optimal storage on tapes
Easy
A.They reduce cumulative retrieval times
B.They remove the need for searching
C.They make every file equally large
D.They increase the physical tape length
Correct Answer: They reduce cumulative retrieval times
Explanation:
A file near the beginning affects the retrieval time of later files, so placing shorter files first reduces cumulative delay.
Incorrect! Try again.
21Which combination of properties most directly justifies solving a problem using dynamic programming?
General method
Medium
A.Sorted input and constant-time transitions
B.Unique subproblems and locally optimal choices
C.Optimal substructure and overlapping subproblems
D.Independent decisions and linear recursion
Correct Answer: Optimal substructure and overlapping subproblems
Explanation:
Dynamic programming is effective when optimal solutions contain optimal subsolutions and the same subproblems occur repeatedly.
Incorrect! Try again.
22A memoized algorithm computes with base cases and . How many distinct states are evaluated when computing ?
General method
Medium
A. states
B. states
C. states
D. states
Correct Answer: states
Explanation:
Memoization evaluates each state from through once, giving distinct states.
Incorrect! Try again.
23For the 0/1 knapsack problem, let be the maximum value using the first items with capacity . If item has weight and value , which recurrence is correct?
General method
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The recurrence compares excluding item with including it once and using the remaining capacity.
Incorrect! Try again.
24What is the length of the longest common subsequence of and ?
General method
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The sequence appears in both strings in the same relative order, so the LCS length is .
Incorrect! Try again.
25In a DAG shortest-path dynamic program, denotes the shortest distance from source to vertex . Which recurrence applies when vertices are processed in topological order?
General method
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
Every path to ends at an incoming edge , so the minimum predecessor distance plus edge weight is selected.
Incorrect! Try again.
26A two-dimensional DP recurrence uses only the previous row and already computed entries of the current row. Which optimization is generally valid?
General method
Medium
A.Replace the table with one or two rows
B.Remove the recurrence base cases
C.Evaluate all states in arbitrary order
D.Replace every state with a greedy choice
Correct Answer: Replace the table with one or two rows
Explanation:
Rows that can no longer affect future computations may be discarded, reducing space while preserving the required dependencies.
Incorrect! Try again.
27Matrices , , and have dimensions , , and . What is the minimum number of scalar multiplications needed to compute ?
Chained matrix multiplication
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
Using costs , which is less than the alternative.
Incorrect! Try again.
28For matrices with dimension sequence , which parenthesization has minimum multiplication cost?
Chained matrix multiplication
Medium
A. with cost
B. with cost
C. with cost
D. with cost
Correct Answer: with cost
Explanation:
The costs are for , for , and for multiplying the results, totaling .
Incorrect! Try again.
29Let matrix have dimensions . In the matrix-chain recurrence, what is the multiplication cost when the chain is split after ?
Chained matrix multiplication
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The two resulting matrices have dimensions and , giving cost .
Incorrect! Try again.
30How many complete parenthesizations are possible for a chain of five matrices?
Chained matrix multiplication
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The number is the Catalan number .
Incorrect! Try again.
31What are the standard time and auxiliary table-space complexities of dynamic programming for a chain of matrices?
Chained matrix multiplication
Medium
A. time and space
B. time and space
C. time and space
D. time and space
Correct Answer: time and space
Explanation:
There are subchains, and each examines up to split positions.
Incorrect! Try again.
32Besides the minimum-cost table, what information should be stored to reconstruct an optimal matrix-chain parenthesization?
Chained matrix multiplication
Medium
A.The split index for each subchain
B.The inverse of every matrix
C.The product of all dimensions
D.The determinant of every matrix
Correct Answer: The split index for each subchain
Explanation:
Recording the optimal split for every subchain allows the parenthesization to be reconstructed recursively.
Incorrect! Try again.
33Matrices , , and have dimensions , , and . How many fewer scalar multiplications does use than ?
Chained matrix multiplication
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
costs , while costs , so the difference is .
Incorrect! Try again.
34Why are matrix-chain DP table entries usually filled in increasing order of chain length?
Chained matrix multiplication
Medium
A.Only adjacent matrices may be multiplied
B.Matrix dimensions must first be sorted
C.Each entry depends on shorter subchains
D.Longer chains always have lower costs
Correct Answer: Each entry depends on shorter subchains
Explanation:
Every candidate split uses solutions for two shorter chains, so those entries must already be available.
Incorrect! Try again.
35Four files have lengths , , , and . Assuming equal retrieval probabilities and one tape, what order minimizes mean retrieval time?
Optimal storage on tapes
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
With equal probabilities, arranging files in nondecreasing order of length minimizes the sum of retrieval times.
Incorrect! Try again.
36Files of lengths , , and are stored in that order on one tape. What is their mean retrieval time if each file is equally likely to be requested?
Optimal storage on tapes
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The retrieval times are , , and , so the mean is .
Incorrect! Try again.
37For unequal access probabilities, file has length and probability . Which ordering rule minimizes expected retrieval time on one tape?
Optimal storage on tapes
Medium
A.Nonincreasing order of
B.Nondecreasing order of
C.Nondecreasing order of
D.Nonincreasing order of
Correct Answer: Nondecreasing order of
Explanation:
The weighted completion-time rule places files in nondecreasing order of the ratio .
Incorrect! Try again.
38File has length and access probability ; file has length and probability . What is the optimal order and expected retrieval time?
Optimal storage on tapes
Medium
A. with expected time
B. with expected time
C. with expected time
D. with expected time
Correct Answer: with expected time
Explanation:
Since , comes first. The expected time is .
Incorrect! Try again.
39Files , , and have values , , and . Which order minimizes expected retrieval time?
Optimal storage on tapes
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The ratios are , , and approximately , so their increasing order is .
Incorrect! Try again.
40Files of lengths , , , and are placed on two tapes as and , with each pair stored in the shown order. Assuming equal access probabilities, what is the mean retrieval time?
Optimal storage on tapes
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The retrieval times are , , , and . Their mean is .
Incorrect! Try again.
41A dynamic program merges multiple partial solutions into the same state. Which condition is essential for this state compression to preserve optimality?
General method
Hard
A.Merged histories must have identical feasible continuations and identical incremental continuation costs.
B.Every partial solution reaching the state must use the same sequence of decisions, even when those decisions no longer affect any future transition.
C.Every state must have a unique predecessor in the dynamic-programming dependency graph.
D.Merged histories must have accumulated exactly the same cost before entering the state.
Correct Answer: Merged histories must have identical feasible continuations and identical incremental continuation costs.
Explanation:
A state is sufficient only when it retains all information affecting future feasibility and cost. Past costs may differ because the DP can retain only the best one.
Incorrect! Try again.
42A top-down memoized DP is evaluated on an acyclic state graph. Exactly states are reachable from the initial state, and their transition lists contain edges in total. Each transition takes constant time. What is the tight running-time bound?
General method
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Memoization evaluates each reachable state once and inspects each outgoing transition once, giving time.
Incorrect! Try again.
43The standard 0/1 knapsack DP runs in time, where is an integer capacity encoded in binary. Which classification is most accurate?
General method
Hard
A.It is polynomial in the binary input length because arithmetic is constant-time.
B.It is pseudopolynomial because may be exponential in .
C.It is strongly polynomial because the table has only entries.
D.It is exponential in for every possible encoding of the capacity.
Correct Answer: It is pseudopolynomial because may be exponential in .
Explanation:
The numeric value , rather than its encoding length , appears in the bound. Thus is pseudopolynomial.
Incorrect! Try again.
44A DP with states uses rolling arrays to reduce value-table memory to . The complete optimal decision sequence must later be produced without asymptotically increasing the running time. Which modification provides the general guarantee?
General method
Hard
A.Store one selected predecessor for every DP state and backtrack from the optimum.
B.Store only the first and last selected decisions and interpolate the remaining ones.
C.Choose a locally optimal predecessor during backtracking without consulting discarded values.
D.Retain the final rolling array because it uniquely determines every earlier decision.
Correct Answer: Store one selected predecessor for every DP state and backtrack from the optimum.
Explanation:
Rolling values generally discard reconstruction information. Recording one optimal predecessor per state guarantees reconstruction, although it restores memory.
Incorrect! Try again.
45In a resource-constrained minimization DP, labels at the same logical state are pairs of accumulated cost and resource consumption. Under the usual monotonicity assumption that having less remaining resource cannot improve future feasibility, when can label safely be discarded?
General method
Hard
A.When another label satisfies and .
B.When another label satisfies but .
C.When its cost is above the average cost of all current labels.
D.When another label satisfies and .
Correct Answer: When another label satisfies and .
Explanation:
The first label is no more expensive and consumes no more resource, so every continuation feasible from the second label is matched or improved.
Incorrect! Try again.
46Consider the finite-horizon recurrence with known values . Which evaluation order is valid even if the underlying state-transition graph contains cycles?
General method
Hard
A.Apply a topological order to the unlayered state-transition graph.
B.Evaluate layers in decreasing order of , starting from the horizon.
C.Evaluate layers in increasing order of , starting from .
D.Evaluate states by decreasing immediate transition cost within every layer.
Correct Answer: Evaluate layers in increasing order of , starting from .
Explanation:
Every layer depends only on the completed layer . Adding the horizon dimension makes dependencies acyclic even when states can revisit one another.
Incorrect! Try again.
47Matrices have dimensions , , , and , respectively. What is the minimum number of scalar multiplications?
Chained matrix multiplication
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The optimal parenthesization is , costing .
Incorrect! Try again.
48For a chain of matrices, how many split points are examined in total by the standard bottom-up matrix-chain DP?
Chained matrix multiplication
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The number is .
Incorrect! Try again.
49A matrix-chain split table contains , , , and . Which parenthesization does it encode?
Chained matrix multiplication
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The root split separates from ; the left subchain then splits after .
Incorrect! Try again.
50Let have dimensions . If an optimal solution for splits after , what scalar-multiplication term must be added to the two subproblem costs?
Chained matrix multiplication
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The two resulting matrices have dimensions and , so combining them costs .
Incorrect! Try again.
51How many complete parenthesizations exist for a chain of matrices?
Chained matrix multiplication
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The count is the Catalan number .
Incorrect! Try again.
52For dimensions , a greedy algorithm repeatedly multiplies the adjacent pair with the smallest immediate cost. What costs do the greedy and optimal solutions obtain, respectively?
Chained matrix multiplication
Hard
A. and
B. and
C. and
D. and
Correct Answer: and
Explanation:
The greedy sequence costs . The optimal parenthesization costs .
Incorrect! Try again.
53Suppose each matrix in a chain may optionally be transposed before multiplication, provided the resulting products are dimensionally compatible. Why is the standard interval state generally insufficient?
Chained matrix multiplication
Hard
A.Transposition makes scalar multiplication nonassociative, so no interval recurrence can be used.
B.The state must record the numerical entries of every intermediate matrix.
C.The state must also represent possible boundary dimensions or orientations of the subchain result.
D.The original recurrence remains sufficient if every multiplication cost is doubled to account for testing both orientations and all compatibility constraints.
Correct Answer: The state must also represent possible boundary dimensions or orientations of the subchain result.
Explanation:
Different orientation choices can give the same interval different output dimensions. Those dimensions affect compatibility and future multiplication costs.
Incorrect! Try again.
54All four matrices in a chain are square matrices of dimension , and ordinary multiplication is used. How many parenthesizations achieve the minimum scalar-multiplication cost?
Chained matrix multiplication
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Every parenthesization performs three multiplications and therefore has cost . There are parenthesizations.
Incorrect! Try again.
55Four files have pairs , , , and . For one sequential tape, which order minimizes expected retrieval time, and what is that expectation?
Optimal storage on tapes
Hard
A. with expectation
B. with expectation
C. with expectation
D. with expectation
Correct Answer: with expectation
Explanation:
Smith's rule orders files by increasing length-to-probability ratio. The weighted completion sum is .
Incorrect! Try again.
56Seven equally likely files have lengths and are stored optimally across three identical tapes. Retrieval starts at the beginning of the selected tape. What is the minimum mean retrieval time?
Optimal storage on tapes
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Cyclic placement gives tapes , , and . Their retrieval-time sums are , , and , so the mean is .
Incorrect! Try again.
57On a single tape, adjacent files and have positive lengths and access probabilities . Under what condition is placing before no worse than placing before ?
Optimal storage on tapes
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Comparing the two orders gives , which is equivalent to ordering by nondecreasing .
Incorrect! Try again.
58For equally likely files and identical tapes, which construction yields an optimal arrangement under the standard sequential-retrieval model?
Optimal storage on tapes
Hard
A.Sort by nonincreasing length and fill one tape completely before using the next.
B.Assign each file to the currently shortest tape while preserving the original input order.
C.Partition files so every tape has exactly the same total length, then arrange each tape from longest to shortest to reduce the number of tape switches.
D.Sort by nondecreasing length and assign files cyclically across the tapes.
Correct Answer: Sort by nondecreasing length and assign files cyclically across the tapes.
Explanation:
Cyclic assignment gives shorter files positions with larger contribution coefficients in the total retrieval-time sum, minimizing that sum by an exchange argument.
Incorrect! Try again.
59When access probabilities differ and files may be assigned to multiple tapes, which statement is correct?
Optimal storage on tapes
Hard
A.Sorting all files by and assigning them cyclically is always globally optimal.
B.Each tape must follow nondecreasing , but choosing the tape allocation remains a global problem.
C.Each tape must follow nondecreasing , regardless of how files are allocated.
D.The allocation depends only on file probabilities because lengths affect ordering but never determine which tape should hold a file.
Correct Answer: Each tape must follow nondecreasing , but choosing the tape allocation remains a global problem.
Explanation:
An adjacent-exchange argument enforces Smith's rule within each tape. Unlike the equal-probability case, a simple cyclic allocation is not generally optimal.
Incorrect! Try again.
60A single tape contains several positive-length files. File has access probability , while every other file has positive access probability. What must hold in every optimal ordering if all lengths are positive?
Optimal storage on tapes
Hard
A. appears immediately after the shortest positive-probability file.
B. may appear anywhere without changing expected retrieval time.
C. appears first because its own retrieval cost is zero.
D.Every positive-probability file appears before .
Correct Answer: Every positive-probability file appears before .
Explanation:
Placing before a requested file delays that file by 's positive length while contributing no weighted benefit. Thus must be last.
Incorrect! Try again.
Did this save you a night before the exam?
LPU Notes is free, and it stays free. Ads cover part of the server bill.
The rest comes out of a student's own pocket: the domain, the storage,
and keeping the site up through the weeks everyone needs it at once.
The payment button didn't load. An ad blocker or a filtered network is the usual reason.
to try again.
Nothing here is ever locked, and nothing unlocks. Chip in only if it was worth it.
What it pays for →