Dynamic Programming Flashcards

Question

Knapsack Problem

Answer 1

This is a generalized problem of the Subset Sum problem. Input: two arrays of positive integers, one is weight, and the other is value and nonnegative T output: the maximal value of input items that does not exceed weight T The robber trying to maximize his heist

Answer 2

solution to Knapsack on W[1 . . n], V[1 . . n], and T as Kn(W, V, n, T). ■ For every W and V: Kn(W, V, n, 0) = 0, ■ For T > 0, it holds: Kn(W, V, 0, T) = 0, Kn(W, V, n, T) = { if W[n] ≤ T: max{ Kn(W, V, n−1, T), Kn(W, V, n−1, T−W[n]) + V[n]) } otherwise: Kn(W, V, n−1, T) . If the current weight is greater than the target weight limit then we do not do anything and we see if the previous is true or not. If the current weight is less than the target then we check if the previous index has a solution and we get the max of that value with the value with the current one being checked in the solution set. The max will be the answer because we are trying to optimize. Very close to Subset Sum.

Answer 3

Time Complexity: O(nT) Space: O(nT) can make it to T by storing the last two columns

Answer 4

Algorithm Knapsack(W, V, n, T) 1: for i ← 0 to n do K[i, 0] ← 0 2: for j ← 1 to T do K[0, j] ← 0 3: for i ← 1 to n do 4: for j ← 1 to T do 5: if W[i] ≤ j then 6: K[i, j] ← max( K[i−1, j], K[i−1, j − W[i]] + V[i] ) 7: else K[i, j] ← K[i−1, j] 8: return K[n, T]

Answer 5

Input: Array of integers Output: The largest size of increasing nonconsecutive sequence. EX: A = [3, 1, 5, 2, 6], then the algorithm should output 3 (corresponding to an example LIS: [3, 5, 6]).

Answer 6

Time Complexity: O(n^2) Space: O(n)

Answer 7

So the lemma is if array contains 1 element then LIS is always 1. When the array is less than 1 then 0 Denote solution to LIS to any index as LIS(k) When the Array size is greater than 1 LIS[n] = 1 + max{LIS[k], k < 5; when A[k] < A[n]; The largest LIS of the smallest number before it plus the number you will add to the end is the solution

Answer 8

procedure LIS(A[1 . . . n]) LISA[1..n] ← 1 for i ← 2 to n do for j ← 1 to i do if A[i] > A[j] and LISA[i] < LISA[j] + 1 then LISA[i] ← LISA[j] + 1 return max(LISA[1 . . . n])

Answer 9

FIRST Define BST: Every node has a key, All nodes to the left are smaller and all nodes to the right are greater. Array representation is left to right. Two arrays: 1. a depth array that contains the depth of each node [i]; d[i], where d[i] is defined as the number of nodes on the path from the node corresponding to ith smallest key to the root of T 2. Another array contains the amount of time node [i] is accessed called frequency array; f[i] Input: Given the frequency array f[i] Output: We want to print the Minimum Cost of traversing through all nodes i f[i] times. So Cost is defined as Cost(T, f) = Sum from i= 1 to n {d[i] * f[i]} ex. Values = [10 11 12] f = [2 1 2] BST #1: 10 \ 11 \ 12 index = [1 2 3] value = [10 11 12] d = [1 2 3] Cost(T, f) = (2*1) + (1*2) + (2*3) = 10 BST #2: 11 / \ 10 12 index = [1 2 3] value = [10 11 12] d = [2 1 2] Cost(T, f) = (2*2) + (1*1) + (2*2) = 9 BST #2 is more efficient than BST #1.

Answer 10

Time Complexity: O(n^3)

Answer 11

the F[i] array is the cumulative sum of the f[i] array up to that point The F array in your OptimalBST algorithm is used to store the prefix sums of the frequencies of the keys. The prefix sum is a technique used in algorithms to calculate the sum of elements in a range (i, j) efficiently. Instead of summing up elements each time a sum is needed, prefix sum calculates and stores the sum of elements up to a certain position beforehand. In your algorithm, F[i] stores the sum of frequencies from f[1] to f[i]. This allows for constant-time retrieval of the sum of frequencies between any two keys, which is used in line 10 of your algorithm. The expression (F[j] - F[i-1]) gives the sum of frequencies from f[i] to f[j], which represents the total search cost for keys between i and j. This technique significantly improves the efficiency of your algorithm by reducing repeated computation. Instead of recalculating the sum every time it’s needed, you calculate it once and reuse it, which is a common strategy in dynamic programming.

Answer 12

Algorithm OptimalBST(f[1 . . n]) 1: F[1] ← 0 2: for i ← 1 to n do 3: F[i + 1] ← F[i] + f[i] 4: for i ← 1 to n + 1 do A[i, i] ← 0 5: for l ← 1 to n do 6: for i ← 1 to n + 1 − l do 7: j ← i + l 8: A[i, j] ← ∞ 9: for r ← i to j − 1 do 10: if A[i, r] + A[r+1, j] < A[i, j] then 11: A[i, j] ← A[i, r] + A[r+1, j] 12: A[i, j] ← A[i, j] + (F[j] − F[i]) 13: return A[1, n + 1]

Answer 13

Trying to multiply n >= 2 amount of matrices together ■ Recall that matrix mul is associative, i.e., for all A, B, C (of right size), (A×B)×C = A×(B ×C), ■ When multiplying m × k and k × p matrices, we perform O(mkp) operations, When it is n >= 3 you can do the multiplication in a different order so the close of operations can vary Input: an array S[1..n] which is of integer pairs such that ith matrix is of size S[i].h * S[i].w. We assume for that for every i matrix width the matrix after has its height equal to the ith width. ensures matrix multiplication rule. Output: Cost of optimal chain matrix multiplication of n matrices with sizes stored in S. We denote this number as OptMul(S). Can multiply a bunch of different ways since it is associative

Answer 14

■ Let S[1 . . n] be our input, ■ If n = 1 then OptMul(S) = 0, ■ If n ≥ 2, then Optmul(S) = min from 1-n { Optmul(S[1..i])+Optmul(S[i+1..n])+S[1].h*S[i].w*S[n].w