2
$\begingroup$

I am trying to wrap my head around how dynamic programming helps avoid all possibilities that are exponential after reading Chapter 8 NP-complete problems of Algorithms by Dasgupta et al. where it says:

So far in this book we have seen the most brilliant successes of this quest, algorithmic techniques that defeat the specter of exponentiality: greedy algorithms, dynamic programming, linear programming (while divide-and-conquer typically yields faster algorithms for problems we can already solve in polynomial time).

Going back to Chapter 6 Dynamic programming, I followed along the longest increasing subsequence problem that this video also shows how to solve. It seemed to me that we were considering all other choices in the solution for the sequence $3, 4, -1, 0, 6, 2, 3$, but only did this with $n^2$ time.

What are the other possible subsequences that would reveal that this problem is exponential in nature without dynamic programming? I can see that in the 0-1 Knapsack problem there are $2^n$ possibilities to consider but can't see the exponential counterpart of the longest increasing subsequence problem.

$\endgroup$
3
$\begingroup$

Go over all $2^n$ subsequences. For each one, check whether it is increasing.

There are two meanings of subsequence: contiguous subsequence and arbitrary subsequence. For example, $1,3$ is a non-contiguous subsequence of $1,2,3$.

Formally, a subsequence of $a_1,\ldots,a_n$ is a sequence $a_{i_1},\ldots,a_{i_m}$ for some $1 \leq m \leq n$, where $1 \leq i_1 < \cdots < i_m \leq n$. A subsequence is contiguous if it is of the form $a_i,a_{i+1},\ldots,a_j$, that is, if it contains all elements from $a_i$ to $a_j$.

A sequence of length $n$ has $2^n-1$ subsequences, only $\binom{n+1}{2}$ of which are contiguous.

For example, here are all subsequences of $a,b,c$: $$ a \\ b \\ c \\ a,b \\ a,c \\ b,c \\ a,b,c $$ Of these, only $a,c$ is not contiguous.

$\endgroup$
6
  • $\begingroup$ Oh. So this means have an array of 0 or 1 on whether or not a number is included in a subsequence? $\endgroup$ Apr 3 at 14:26
  • $\begingroup$ What is a general subsequence? I haven't been able to find it on google but I have for contiguous. $\endgroup$ Apr 3 at 14:29
  • $\begingroup$ Use your imagination. $\endgroup$ Apr 3 at 15:12
  • $\begingroup$ I see you changed from general to arbitrary subsequence. Thanks. Wouldn't have known what my imagination came up with was correct. $\endgroup$ Apr 3 at 17:11
  • $\begingroup$ @heretoinfinity, on most (if not all) modern (meaning in the recent 20 or much more years) situations, a subsequence means what is meant by subsequence or arbitrary subsequence by Yuval here. A contiguous subsequence is also commonly called as a sublist, a subarray, or a substring. $\endgroup$
    – John L.
    Apr 3 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.