Register

Recent questions tagged dynamic-programming

0 0 votes
0 0 answers
33
33 views
CMI 2026 | CS | Part C | Question: 4
In the Pots-of-Gold game, there is a row of $n$ pots $P_{1}, \ldots, P_{n}$. Each pot contains some number of gold coins. You remove pots and collect the gold coins from ...
User Avatar
2 2 votes
1 1 answer
172
172 views
GO Classes DPP | GATE CS, DA | Algorithms | Dynamic Programming
True or False:In every dynamic-programming solution, the asymptotic space requirement must be at least as large as the total number of distinct subproblems.True False
User Avatar
2 2 votes
1 1 answer
118
118 views
GO Classes DPP | GATE CS, DA | Algorithms | Dynamic Programming
True or False:The root of an optimal binary search tree must always contain the key having the highest search probability.True False
User Avatar
0 0 votes
1 1 answer
89
89 views
GO Classes DPP | GATE CS, DA | Algorithms | Dynamic Programming
An instance of Subset Sum contains:$n$ positive integersa positive target value $m$What is the running time of the standard dynamic-programming solution?$\Theta(m+n)$ $\T...
User Avatar
1 1 vote
1 1 answer
113
113 views
GO Classes DPP | GATE CS, DA | Algorithms | Dynamic Programming
There is an unlimited supply of three item types:$$\begin{array}{|c|cc|}\hline\text{Item} & \text{Size} & \text{Value} \\\hlineA & 1 & 2 \\B & 2 & 6 \\C & 3 & 9 \\\hline\...
User Avatar
0 0 votes
1 1 answer
100
100 views
GO Classes DPP | GATE CS, DA | Algorithms | Dynamic Programming
The following function $\texttt{CalcEditDistance}$ computes the edit distance between two strings.For this problem:Inserting one character has cost $1$.Deleting one chara...
User Avatar
0 0 votes
1 1 answer
148
148 views
GO Classes DPP | GATE CS, DA | Algorithms | Longest Increasing Subsequence
For an array, $a ,a ,\ldots,a[n]$ consider the proposed DP state:$LIS[i]=$ length of the longest increasing subsequence contained anywhere within $a[1\ldots i]$.Using onl...
User Avatar
3 3 votes
1 1 answer
178
178 views
GO Classes DPP | GATE CS, DA | Algorithms | 0/1 Knapsack
A $15$ kg knapsack is given with the following items:$$\begin{array}{|c|cc|}\hline\text{Item} & \text{Weight} & \text{Value} \\\hlineA & 2 & 7 \\B & 3 & 10 \\C & 5 & 18 \...
User Avatar
2 2 votes
1 1 answer
120
120 views
GO Classes DPP | GATE CS, DA | Algorithms | Longest Common Subsequence
Consider the sequences:$X=\{A,C,B,C,D,C\}$$Y=\{C,D,B,D,C,A\}$What is the length of their longest common subsequence?
User Avatar
1 1 vote
1 1 answer
123
123 views
GO Classes DPP | GATE CS, DA | Algorithms | Matrix Chain Multiplication
Consider four matrices whose dimension array is:$p=[5,2,2,4,6]$Thus:$A_1:5\times2$$A_2:2\times2$$A_3:2\times4$$A_4:4\times6$Using optimal matrix-chain multiplication, wha...
User Avatar
2 2 votes
1 1 answer
103
103 views
GO Classes DPP | GATE CS, DA | Algorithms | Dynamic Programming
Consider the following statements.Dynamic programming generally solves smaller subproblems, stores their solutions, and combines those stored results to solve progressive...
User Avatar
0 0 votes
1 1 answer
159
159 views
UGC NET CSE | December 2025 | Part 2 | Question: 47
Match the LIST-I with LIST-IILIST-ILIST-IIA.Dynamic programmingI.Floyd Warshall Shortest pathB.GreedyII.Huffman codingC.Back trackingIII.Hamiltonian cycle problemD.Branch...
User Avatar
10 10 votes
2 2 answers
1.3k
1.3k views
GATE CSE 2026 | Set 2 | Question: 29
Consider a table $T$, where the elements $T[i][j], 0 \leq i, j \leq n$, represent the cost of the optimal solutions of different subproblems of a problem that is being so...
User Avatar
1 1 vote
2 2 answers
515
515 views
UGC NET CSE | June 2025 | Part 2 | Question: 28
The longest common subsequence of $\{1,2,3,2,4,1,2\}$ and $\{2,4,3,1,2,1\}$ is$2,1,2,3$$1,3,2,1$$2,3,2,1$$2,3,1,2,1$
User Avatar
0 0 votes
1 1 answer
642
642 views
UGC NET CSE | June 2025 | Part 2 | Question: 50
When developing a dynamic programming algorithm, the sequence of steps followed is:Construct an optimal solution from computed information.Recursively define the value of...
User Avatar
0 0 votes
1 1 answer
498
498 views
UGC NET CSE | August 2024 | Part 2 | Question: 48
Arrange the following steps in the correct order to solve the Knapsack problem using Dynamic Programming.Define the base case when the capacity is zero ($0$) or no items ...
User Avatar
1 1 vote
1 1 answer
201
201 views
NIELIT Scientific Assistant June 2025 | Question: 119
Which of the following problems is solved using dynamic programming?Merge sortDepth-first searchBreadth-first searchFibonacci sequence calculation
User Avatar
0 0 votes
1 1 answer
306
306 views
CMI2024-B: 7
A subsequence of an array $A$ is any sub-array of $A$, obtained by deleting zero or more elements of $A$ without changing the order of the remaining elements. The input t...
User Avatar
Page: