Algorithms Tick 2*

Algorithms Tick 2*: dynamic programming continued

1. Recursive Top-Down Memoised LCS

The bottom-up approach used to solve the LCS problem in tick 2 involves filling in the entire solution table. We often find that some of this was wasted effort: some cells simply contribute nothing to the solution. It is thus desirable to have a solution that only computes the cell values that it needs to get the answer.

To do this requires a top-down solution, and the easiest way to implement it is using recursion. If implemented naively, however, the recursion will compute some cells multiple times. To avoid this we use memoisation, which is a fancy way of saying we save our previous subproblem results and always check whether we’ve already solved a particular subproblem before we go ahead and try to compute it.

As we said, the benefit of the top-down approach is that it will only compute the table values that it needs. For the “ABBA” and “CACA” example, the final table should contain at least six uncomputed cells, marked here with NA.

\(j=0\) (C) \(j=1\) (CA) \(j=2\) (CAC) \(j=3\) (CACA)
\(i=0\) (A) 0 1 1 NA
\(i=1\) (AB) 0 1 1 NA
\(i=2\) (ABB) 0 1 1 NA
\(i=3\) (ABBA) NA NA NA 2

This table results from a straightforward exploration of the LCS length table. There are further optimisations that can be made that will involve even fewer computations for some problems. For the tick you do not need to implement such optimisations, although you might like to try!

2. Non-Recursive Top-Down Memoised LCS

While the recursive solution avoids unnecessary cell computations, it does make heavy use of the call stack (as all recursive functions must). The constant creation, addition and deletion of stack frames can be a bottleneck, however, and it may be beneficial to implement a non-recursive top-down solution.

For the second part of this tick you should implement a solution that produces identical results to those from your recursive solution from part 1, but without the use of recursion.

Hint: you should use some form of storage that supports the Stack abstract data type.


You may submit your answer on Moodle in either Python or Java.

Submission (Python)

Submission filename: lcs.py (The Moodle tester has space to upload two files, to accommodate Java, but for Python you only need to upload a single file.)

Please submit a source file lcs.py that implements four functions:

# replacements for the table function from tick 2
table_topdown_recursive(s1, s2)
table_topdown_nonrecursive(s1, s2)

# unchanged from tick 2
match_length(tbl)
match_string(s1, s2, tbl)

You should indicate cells that have not been computed with the value None.

Submission (Java)

Submission filenames: LCSTopDownRecursive.java, LCSTopDownNonRecursive.java

The first task in this tick is to implement a class LCSTopDownRecursive that inherits from LCSFinder. The getLCSLength() method should solve the LCS length problem top-down recursively and with memoisation. You should indicate cells that have not been computed with the value -1 within mTable. It is therefore sensible to initialise your mTable array to have -1 in all cells.

The second task is to create a class LCSTopDownNonRecursive that again inherits from LCSFinder and performs a top-down solution, but without recursion. The results should be identical to those produced by LCSTopDownRecursive.