[Tutor] python programmin problem

Sat Jul 23 12:26:45 EDT 2016

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?

  L(A, k) is the length of the longest increasing subsequence of the
prefix of A with length k, where that subsequence needs to include the
k'th element too.

What is L?  This L function tries to capture the idea of having a
*partial* solution that involves a portion of the array A.

Why is it helpful?  Because of two crucial things:

    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?

    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? 
Thank you so much
Monika
---------- Original Message ----------
From: Danny Yoo <dyoo at hashcollision.org>
To: Alan Gauld <alan.gauld at yahoo.co.uk>
Cc: "monikajg at netzero.net" <monikajg at netzero.net>, tutor <tutor at python.org>
Subject: Re: [Tutor] python programmin problem
Date: Sat, 23 Jul 2016 00:13:36 -0700

On Thu, Jul 21, 2016 at 11:30 PM, Alan Gauld via Tutor <tutor at python.org> wrote:
>
> Forwarding to list. Please use reply-all when responding to tutor messages.
>
> As Danny suggested this is quite a complex problem. I wasn't sure whether
> it was just the programming or the bigger algorithm issue you were stuck on.

[warning: large message ahead.]

This problem is unfortunately not something you can just code by
trying to hack it till it works.  At this level of difficulty, these
kinds of problems are *not* easy: they require some understanding of
fundamentals in algorithms, not Python.  That is, the actual coding of
this is not the hard part.  A direct solution to this problem is a
couple of lines and involves nothing more loops and arrays.  The
difficulty is understanding how to use solutions of sub-problems
toward the general large problem.

I should state this more strongly: trying to hack the solution is not
going to work.  I have to ignore the code presented in this thread
because there's very little to preserve.  The approach of trying to
look at only the very previous element is simply not viable.  The most
direct approach I know to do this is by talking about this in terms of
subproblems.

Here is a sketch of the idea:

Let's put on our magical thinking cap, and say that we'd like to
design a function L(A, m) with the following funny property:

For array A of length N, and for an integer k < N:

  L(A, k) is the length of the longest increasing subsequence of the
prefix of A with length k, where that subsequence needs to include the
k'th element too.

What is L?  This L function tries to capture the idea of having a
*partial* solution that involves a portion of the array A.

Why is it helpful?  Because of two crucial things:

    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.

    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 so?

-------------------------------------------------------------------

As a concrete example, consider a list A = [5, 8, 6, 7].

* What is L(A, 1)?  We want the length of the longest subsequence of
the prefix [5] that includes the 5.  And that's just 1.

   L(A, 1) = 1.

That is, we're starting from scratch: we can't do better than just
pick the 5 as the start of our subsequence.  Since our subsequence
just has [5], that's a subsequence of length 1.

* What is L(A, 2)?  We want the length of the longest subsequence of
the prefix [5, 8] that includes the 8.  Why does knowing L(A, 1) help
us?  Because we know L(A, 1) is 1.  What does that mean?  We look at
L(A, 1) to see if maybe we can pick the subsequence that it is
measuring, and augment it.

We know L(A, 1) is the length of the longest sequence that ends up
including the first element of A, so we know that subsequence ends
with a [... 5].  And we can extend that subsequence so it look like
[..., 5, 8].  And we know that such an extension will be of length 2.
Can we do any better?  There are no other subproblems, so no.

That is, L(A, 2) = 2.

* What is L(A, 3)?  We want the length of the longest subsequence of
the prefix [5, 8, 6] that includes the 6.

    We look at L(A, 1): can we just extend [..., 5] with a 6?  Yes,
and that gives us 2 as a possible answer for L(A, 3).  Why 2?  Because
L(A, 1) = 1, and if we extend the subsequence measured by L(A, 1), we
make it one element longer, so 1 + 1 = 2.

    Can we do better?

    We look at L(A, 2): can we just extend [..., 8] with a 6?  No.

Ok, so L(A, 3) = 2.

* What is L(A, 4)?  We want the length of the longest subsequence of
the prefix [5, 8, 6, 7] that includes the 7.

   We look at L(A, 1):.  Can we just extend [..., 5] with a 7?  Yes,
and that gives us 2 as a possible answer for L(A, 4).

   Can we do better?

   We look at L(A, 2).  Can we just extend [..., 8] with a 7?  No.

   Can we do better?

   We look at L(A, 3).  Can we just extend [..., 6] with a 7?  Yes,
and that gives us 3 as a possible answer for L(A, 4).  Why 3?  Because
L(A, 3) = 2, and if we extend the subsequence measured by L(A, 3), we
make it one element longer, so 2+1 = 3.

Ok, we've got L(A, 1), L(A, 2), L(A, 3), and L(A, 4).

Which one was the largest?  3.  What's the subsequence that's of
length 3?  We know it's [5, 6, 7], and that's length 3, so that seems
to match.

So the length of the longest subsequence of the whole A is 3.

-------------------------------------------------------------------

Generalizing: when we're looking for a solution for L(A, k), we can
look at the prior values L(A, 1), L(A, 2), ... L(A, k), because those
represent the lengths of other longest subsequences that we can extend
by including the k'th element.  But we've got to look to see if the
extension is valid ifrst, and that requires looking at elements of A
at the respective positions.  Once we do this, we can then pick the
one that gives us the longest valid extension.

--------------------------------------------------------------------

You need to try to do similar reasoning for smaller examples to
convince yourself that this approach works in general.  For example,
try it on the input [5, 8, 3].
.

This is the kind of process that's expected when solving this class of
problems.  If you haven't seen this style of attacking a problem by
relating to smaller subproblems, then we strongly urge you to please
talk with your professor or study group.
_______________________________________________
Tutor maillist  -  Tutor at python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

____________________________________________________________
Affordable Wireless Plans
Set up is easy. Get online in minutes.
Starting at only $9.95 per month! 
www.netzero.net?refcd=nzmem0216