CS 4349 — Advanced Algorithm Design and Analysis, Homework 4
Question 1
We must show that for
We show this by induction.
Before we begin, not that and . Proof. Basis:
- We must show that
Inductive Hypothesis:
- Assume that for
Inductive Step
- We must show that
By our assumption,
By the inductive hypothesis, this means that
Question 2
Determine all of the longest common subsequences of the sequences {a, b, b, a, b, a, b, a}, which we call sequence and {b, a, b, a, a, b, a, a, b}, which we call sequence .
The DP solution to LCS is applicable here. We modify this to maintain a set at every single element of the dp in addition to the length. If we add a new element (i.e. ), then we also concatenate to each element in the set as well. Otherwise, if , we copy the same set from the dp table which we choose from.
The subsequences are
abbaab
ababab
bbabaa
ababaa
bababa
bbabab
abaaba
bbaaba
Question 3
a
Design recursive and bottom-up dynamic programming algorithms for Tribonacci numbers.
Recursive approach Define table dp let s.t. We set . Take , otherwise, compute using the recursive formula above and set Bottom Up Approach The bottom up approach is defined as follows: Define table which we call “dp” let s.t. Converting this into pseudocode:
b
Explain the running time of each algorithm. Recursive Approach The recursive approach takes . Once the table is filled, the algorithm will not recurse further than a single recursive call. Additionally, the table contains only elements, so the algorithm takes
Bottom Up Approach The bottom up approach takes . Filling each entry of the table takes , and there are entries in the table. Additionally, every element of the table must be enumerated to produce the correct output.
Question 4
Take the recurrence , with and .
The naive recursive solution can be implemented as follows:
This solution is clearly exponential in , as we must compute the results at every single recursive call, leading to a full tree of recursive calls being generated. The height of this tree is at most , so the number of nodes (i.e. the number of recursive calls) is .
Compare this to the bottom-up dynamic programming algorithm for computing the Fibonacci sequence presented below:
Because the dp table contains elements, so the algorithm takes .