This chapter discusses dynamic programming algorithms in comparison to recursions.
This section discusses recursive, iterative, and dynamic programming ways of generating the Fibonacci sequence.
The is a sequence of numbers generated as follows:
where
Let us create the interface that contains one abstract method:
L2
: returns the 'th Fibonacci number.
The followings demonstrate how to generate the Fibonacci sequence using recursion:
What is the worst-case complexity of this recursive algorithm?
The followings demonstrate how to generate the Fibonacci sequence using dynamic programming:
Let us create the FibonacciDynamic
class inheriting Fibonacci
:
L16
: returns the value in the dynamic table if exists.
L17
: fills in the dynamic table using recursion.
What is the worst-case complexity of this dynamic programming algorithm?
The followings show performance comparisons:
Let us create the class inheriting Fibonacci
:
L7
: creates a dynamic table represented by an array where the 'th dimension is to be filled with the 'th Fibonacci number.
For this particular task, the efficiency can be further enhanced using iteration. Let us create the class inheriting Fibonacci
:
This section discusses recursive and dynamic programming ways of solving the Tower of Hanoi problem.
The followings demonstrate the Tower of Hanoi problem:
Let us create the abstract class Hanoi
:
L9
: returns a list of movements to solve the given problem.
n
: the total number of rings.
source
: the ID of the source tower.
intermediate
: the ID of the intermediate tower.
destination
: the ID of the destination tower.
L11
: returns the string representation of a movement.
Let us create the HanoiRecursive
class inheriting Hanoi
:
Let us create the HanoiDynamic
class inheriting Hanoi
:
The followings show performance comparison:
This section discusses recursive and dynamic programming ways of finding longest common subsequence.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Given a string "ABCDE"
Substring: {"A", "BC", "CDE", ...}
Subsequence: {all substrings, "AC", "ACE", ...}
Not subsequence: {"BA", "DAB", ...}
Longest common subsequence
The longest subsequence commonly shared by multiple strings.
e.g., “baal” is a LCS of “bilabial” and “balaclava”.
Can there be more than one longest common subsequence?
Application
Find the longest common subsequence in DNA (e.g., GAATGTCCTTTCTCTAAGTCCTAAG
).
Let us create the abstract class :
L4
: no character is left to compare for either string.
L5
: when two characters match, move onto c[:i-1]
and d[:j-1]
.
L7
: gets the longest common subsequence between c[:i-1]
and d[:j]
.
L8
: gets the longest common subsequence between c[:i]
and d[:j-1]
.
L9
: returns the longest subsequence.
The followings demonstrate a recursive way of finding a LCS between two strings:
L4
: creates a dynamic table and passes it to the solver.
L12
: the dynamic table is pre-populated before any recursive calls.
The following show the dynamic table populated by the previous example:
Let us define the solve()
method:
L2
: no character is left to compare for either string.
L3
: when two characters match, move onto c[:i-1]
and d[:j-1]
.
L5
: gets the longest common subsequence between c[:i]
and d[:j-1]
.
L6
: gets the longest common subsequence between c[:i-1]
and d[:j]
.
L9
: returns the longest subsequence by looking up the values in the dynamic table.
The followings demonstrate how to find a LCS using the dynamic table:
This section provides exercises for better understanding in dynamic programming.
Write a report quiz9.pdf
that includes answers to the followings.
As n
increases from 1
to 10
, how many times does the auxiliary solve()
method get called recursively in and ?
Is there clear patterns between n
and the number of the method calls made by these classes? Explain the patterns if exist.
Include answers to the followings in quiz9.pdf
:
Explain what the values of the dynamic table mean in the class.
LCSDynamic
pre-populates the dynamic table before making any recursive calls. Is it possible to find a LCS with dynamic programming by populating the dynamic table while making recursive class.
You may need a different type of a dynamic table to populate it while making recursive calls.
Create the class under the package.
Update the solveAll()
that returns all longest common subsequences between two strings.
Let us create the inheriting LCS
:
Let us create the class inheriting LCS
.