[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.
More information about the Tutor
mailing list