Program #2
In this program you will design and implement and test three versions of the
Longest Common Subsequence (LCS) problem. Your program will read one sequence
of n integers from a file (n can be specified by the user), and produce at
least one longest INCREASING subsequence (think about what the second sequence
will be that will generate an increasing subsequence). The three versions of
the program are described below.
1. Implement the brute force version of the algorithm, which examines all
possible subsequences. This algorithm will run in time exponential in n.
You can implement a recursive algorithm for this step using equation 16.5
in the textbook.
2. Implement a bottom-up dynamic programming solution to this problem,
based on the solution given in chapter 16 of the textbook. This
algorithm should run in time O(n^2).
3. Design and implement a memoized version of the dynamic programming
solution that runs in time O(n^2).
Test the three algorithms on inputs of increasing size (size 10, 100, 1000,
10,000, and larger, until you run out of memory or the program runs longer than
15 minutes). Plot the run times of the three algorithms on the input sizes
(alternatively, you can list the run times in a table). Do the dynamic
programming solutions outperform the brute force solution in terms of run time?
(
geocities.com/Vienna/7079/src) (
geocities.com/Vienna/7079) (
geocities.com/Vienna)