CS 6515 ALGORITHMS FINAL PAPER EXAM QUESTIONS ACCURATE ANSWERS FULL
SOLUTION
Question:
Length of Longest Subsequence - Subproblem.
Answer:
T[i]: Length of the longest increasing subsequence of A[1.i] ending at index i and including element
A[i]
Question:
Length of Longest Subsequence - Runtime.
Answer:
Number of Subproblems: O(n) one for each index i. Time to Fill Table: O(n2) due to "global"
dependency on j, for each i, iterate on all previous j < i. Result Extraction: max{T[*]} final LIS
length is the maximum over all T[i]. Time for Result Extraction: O(n) due to the max operation
requiring a single pass over all n values, performing n simple comparisons.
Question:
Given a given sequence A[1.n], return the length of the longest increasing subsequence. E.g, A = [5,
7, 4, -3, 9, 1, 10, 4, 5, 8, 9, 3], LIS = [-3, 1, 4, 5, 8, 9], Length of LIS = 6.
Answer:
T[i]: Length of the longest increasing subsequence of A[1.i] ending at i and including A[i] Base
Case: T[1] = 1 Recurrence: T[i] = 1 + max{ T[j] if A[j]<A[i] }, Bounds: 2 ≤ i ≤ n & 1 ≤ j ≤ i-1
Number of Subproblems: O(n). Time to Fill Table: O(n2). Result Extraction: max{T[*]}. Time for
Result Extraction: O(n).
Question:
Max/Min of Contiguous Subsequence - Subproblem.
, Answer:
T[i]: Max/Min sum of a contiguous subsequence of A[1.i] ending at i and including element A[i]
Question:
Max/Min of Contiguous Subsequence - Recurrence.
Answer:
Base Case: T[0] = 0 (DP table T[0.n], 0 acts as a sentinel for the sum before any elements are
considered) Recurrence: Max Sum: T[i] = max{ A[i], A[i] + T[i-1] } = A[i] + max{ 0, T[i-1] },
Bounds: 1 ≤ i ≤ n Min Sum: T[i] = min{ A[i], A[i] + T[i-1] } = A[i] + min{ 0, T[i-1] }, Bounds: 1 ≤
i ≤ n Choice: Start new subarray at i (A[i]) OR extend previous subarray ending at i-1 (A[i] +
T[i-1]).
Question:
Max/Min of Contiguous Subsequence - Runtime.
Answer:
Number of Subproblems: O(n) one per index i. Time to Fill Table: O(n) due to "local" dependency
on T[i-1], only O(1) work per i (constant look-back to i-1). Result Extraction: Max Sum: max{T[*]}
final max sum is the maximum over all T[i]. Min Sum: min{T[*]} final max sum is the minimum
over all T[i]. Time for Result Extraction: O(n) single pass to find the max.
Question:
Find the Contiguous Subsequence (subarray) within array A[1.n] that has the largest sum. Return the
largest sum. E.g: A = [-2, 3, -1, 5, -3], subarray = [3, -1, 5], Max Sum = 7.
Answer:
T[i]: Maximum sum of a contiguous subsequence of A[1.i] ending at i and including A[i]. Base
Case: T[0] = 0. Recurrence: T[i] = A[i] + max(0, T[i-1]), 1 ≤ i ≤ n Number of Subproblems: O(n).
Time to Fill Table: O(n). Result Extraction: max{T[*]}. Time for Result Extraction: O(n).
Question:
Optimal Value (Max Profit/Min Cost) Up to i - Subproblem.
SOLUTION
Question:
Length of Longest Subsequence - Subproblem.
Answer:
T[i]: Length of the longest increasing subsequence of A[1.i] ending at index i and including element
A[i]
Question:
Length of Longest Subsequence - Runtime.
Answer:
Number of Subproblems: O(n) one for each index i. Time to Fill Table: O(n2) due to "global"
dependency on j, for each i, iterate on all previous j < i. Result Extraction: max{T[*]} final LIS
length is the maximum over all T[i]. Time for Result Extraction: O(n) due to the max operation
requiring a single pass over all n values, performing n simple comparisons.
Question:
Given a given sequence A[1.n], return the length of the longest increasing subsequence. E.g, A = [5,
7, 4, -3, 9, 1, 10, 4, 5, 8, 9, 3], LIS = [-3, 1, 4, 5, 8, 9], Length of LIS = 6.
Answer:
T[i]: Length of the longest increasing subsequence of A[1.i] ending at i and including A[i] Base
Case: T[1] = 1 Recurrence: T[i] = 1 + max{ T[j] if A[j]<A[i] }, Bounds: 2 ≤ i ≤ n & 1 ≤ j ≤ i-1
Number of Subproblems: O(n). Time to Fill Table: O(n2). Result Extraction: max{T[*]}. Time for
Result Extraction: O(n).
Question:
Max/Min of Contiguous Subsequence - Subproblem.
, Answer:
T[i]: Max/Min sum of a contiguous subsequence of A[1.i] ending at i and including element A[i]
Question:
Max/Min of Contiguous Subsequence - Recurrence.
Answer:
Base Case: T[0] = 0 (DP table T[0.n], 0 acts as a sentinel for the sum before any elements are
considered) Recurrence: Max Sum: T[i] = max{ A[i], A[i] + T[i-1] } = A[i] + max{ 0, T[i-1] },
Bounds: 1 ≤ i ≤ n Min Sum: T[i] = min{ A[i], A[i] + T[i-1] } = A[i] + min{ 0, T[i-1] }, Bounds: 1 ≤
i ≤ n Choice: Start new subarray at i (A[i]) OR extend previous subarray ending at i-1 (A[i] +
T[i-1]).
Question:
Max/Min of Contiguous Subsequence - Runtime.
Answer:
Number of Subproblems: O(n) one per index i. Time to Fill Table: O(n) due to "local" dependency
on T[i-1], only O(1) work per i (constant look-back to i-1). Result Extraction: Max Sum: max{T[*]}
final max sum is the maximum over all T[i]. Min Sum: min{T[*]} final max sum is the minimum
over all T[i]. Time for Result Extraction: O(n) single pass to find the max.
Question:
Find the Contiguous Subsequence (subarray) within array A[1.n] that has the largest sum. Return the
largest sum. E.g: A = [-2, 3, -1, 5, -3], subarray = [3, -1, 5], Max Sum = 7.
Answer:
T[i]: Maximum sum of a contiguous subsequence of A[1.i] ending at i and including A[i]. Base
Case: T[0] = 0. Recurrence: T[i] = A[i] + max(0, T[i-1]), 1 ≤ i ≤ n Number of Subproblems: O(n).
Time to Fill Table: O(n). Result Extraction: max{T[*]}. Time for Result Extraction: O(n).
Question:
Optimal Value (Max Profit/Min Cost) Up to i - Subproblem.
