[Tutor] python programmin problem

Danny Yoo dyoo at hashcollision.org
Sun Jul 24 15:58:08 EDT 2016

```On Jul 23, 2016 9:27 AM, "monikajg at netzero.net" <monikajg at netzero.net>
wrote:
>
> IM sorry I do not understand:
>
> For array A of length N, and for an integer k < N:
> -- By k do you mean value of k or position of k in the list?
>

The letter 'k' is typically intended to be used as an index, a position
into a list.  I'm trying to say that k had to be pointed somewhere in the
list by constraining it to be less than the size of the list.

>
>     1.  If we know L(A, 1), L(A, 2), ... all the way to L(A, N), then
> we can just look at the maximum value of those pieces.  That's going
> to be a solution to the general problem.
> -- By maximum value do you mean I have to sum up the values in the list?
Why?

"Maximum" is a notion of comparing and picking out the biggest thing we
see.  It doesn't have to do with addition.

If we have a bunch of numbers, we can do a lot more than just add then
together. Numbers are more interesting than that.

Both summation and maximum-finding are operations that are intended to take
a bunch of bits of information in order to discover something new.  So,
conceptually speaking, there *is* a deep, underlying connection.  But I
don't think that's what you're intending to talk about.

>     2.  For a subproblem L(A, k), if we know the values for L(A, 1),
> L(A, 2), ... , L(A, k-1), then we can compute L(A, k) by looking at
> those other subproblems: the result of L(A, k) is related to them.
> -- How do we find those subproblems? And then how do you relate them to
the main problem?
>
> Can you please explain more in details?

Unfortunately, no.  This is the wrong venue.

Please: I strongly encourage you to talk with your professor or study
group: it really does sound like this is the first time you've seen these
kinds of concepts.  Longest common subsequence is not the ideal problem to
use to introduce these concepts: it is meant to help you *master* them.  I
would not dare trying to use it as a first example into learning dynamic
programming.

You probably want to use a problem that has fewer moving parts.  Your
instructor likely has a much nicer introductory problem so that you can
learn the patterns of thinking through these problems.

Anyway, hope that makes sense.
```