CS 4349 — Advanced Algorithm Design and Analysis, Homework 4

Download PDF

Question 1

We must show that for

We show this by induction.

Before we begin, not that and . Proof. Basis:

Inductive Hypothesis:

Inductive Step

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 .