lazy - lcs-length and using build-table

[Stephen Rollins]

The requirements for lcs-length say that we must use build-table to perform sub-problems of the subset finding, but I'm confused as to why we need to do this or how to make use of the data gathered in the sub-problems. I understand that this is a lab about laziness, so I expect there will be a way to refer back to previous cells in the still-not-fully-calculated table so that, say, cell (2, 2) can look at the result of cell (2, 1). I haven't given the mechanics of that part much thought yet. I'm too busy being caught up in how exactly I will make use of the data from sub-problems.

What do the sub-problems need to store in the table? An integer representing the length? How is that helpful for calculating the subsequence when you go on to the next cell in the table? If they return the actual subsequence itself, how do we make use of that when performing our next calculations? I know we will not get credit if we repeat any calculations. So what calculations exactly are we trying to avoid repeating?

I hope this all makes sense. If it doesn't, I know that Jay will make the ambiguity very clear in his response. :)

[Jay McCarthy]

On Fri, Dec 6, 2013 at 9:30 PM, Stephen Rollins <enzed....@gmail.com> wrote:
> The requirements for lcs-length say that we must use build-table to perform
> sub-problems of the subset finding,

The problem is about sub-sequences NOT subsets.

> but I'm confused as to why we need to do
> this or how to make use of the data gathered in the sub-problems. I
> understand that this is a lab about laziness, so I expect there will be a
> way to refer back to previous cells in the still-not-fully-calculated table
> so that, say, cell (2, 2) can look at the result of cell (2, 1). I haven't
> given the mechanics of that part much thought yet.

It's trivial, just call vector-ref twice.

> I'm too busy being caught
> up in how exactly I will make use of the data from sub-problems.
>
> What do the sub-problems need to store in the table? An integer representing
> the length?

"the answer for sub-problem made from prefixes of s1 and s2"

So if s1 = {a b c} and s2 = {d e f}, then the entire answer is based
on the answer for {a b} and {d e}. So you just compute the answer for
the sub-problem... meaning for lcs-length. It's the exact computation.

> How is that helpful for calculating the subsequence when you go
> on to the next cell in the table?

Bro, just look it up on Wikipedia. It's trivial and you've already
seen it in 312.

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#LCS_function_defined

> If they return the actual subsequence
> itself, how do we make use of that when performing our next calculations?

You are not finding the actual sub-sequence, you're finding the length.

> I
> know we will not get credit if we repeat any calculations. So what
> calculations exactly are we trying to avoid repeating?

The solution for the sub-problems.

> I hope this all makes sense. If it doesn't, I know that Jay will make the
> ambiguity very clear in his response. :)
>

> --
> You received this message because you are subscribed to the Google Groups
> "byu-cs-330-fall-2013" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to byu-cs-330-fall-...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.



--
Jay McCarthy <j...@cs.byu.edu>
Assistant Professor / Brigham Young University
http://faculty.cs.byu.edu/~jay

"The glory of God is Intelligence" - D&C 93

[Stephen Rollins]

Thank you, that makes much more sense.