CS6515 ALGORITHMS FINAL TEST PAPER
ONE 2026 DETAILED QUESTIONS GRADED
A+
⩥ 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]
⩥ 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.
⩥ 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).
⩥ 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]
⩥ 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]).
⩥ 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.
⩥ 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).
⩥ Optimal Value (Max Profit/Min Cost) Up to i - Subproblem. Answer:
T[i]: Optimal value (max profit, min penalty/cost) for prefix A[1...i] up
to i.
⩥ Optimal Value (Max Profit/Min Cost) Up to i - Recurrence. Answer:
Base Case:
ONE 2026 DETAILED QUESTIONS GRADED
A+
⩥ 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]
⩥ 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.
⩥ 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).
⩥ 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]
⩥ 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]).
⩥ 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.
⩥ 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).
⩥ Optimal Value (Max Profit/Min Cost) Up to i - Subproblem. Answer:
T[i]: Optimal value (max profit, min penalty/cost) for prefix A[1...i] up
to i.
⩥ Optimal Value (Max Profit/Min Cost) Up to i - Recurrence. Answer:
Base Case:
