What is the space complexity of computing the LENGTH of the Longest Common Subsequence of two strings of lengths m and n using space optimization?
Computing only the length requires only the current row and the previous row of the DP table. By allocating the array for the smaller string, space is O(min(m, n)).
What is the time complexity to find the length of the Longest Common Subsequence of two strings of lengths m and n using Dynamic Programming?
The DP table is of size (m+1) x (n+1), and each entry is computed in O(1) time. Total time complexity = O(m * n).
If string X has length m and string Y has length n with no common characters between X and Y, what is the length of their LCS?
Since there are no common characters, no non-empty subsequence exists in both X and Y. LCS length = 0.
What is the time complexity of the OPTIMAL algorithm to find the length of the Longest Increasing Subsequence (LIS) of an array of size n?
The standard DP takes O($n^2)$ time. Using Patient Sorting / Binary Search (Patience Sorting with std::lower_bound), LIS length is found in O(n log n) time.
What is the length of the Longest Increasing Subsequence of the array A = [10, 22, 9, 33, 21, 50, 41, 60, 80]?
An optimal increasing subsequence is [10, 22, 33, 50, 60, 80] or [10, 22, 33, 41, 60, 80] with length 6.