BBM408 - Algorithm Analysis

Final Exam - 26 May 2022

Questions

Question 1

Show that $T(n)$ is $O(n\lg n)$ using recursion tree where $T(n) = 2T(n/4)+T(n/2)+n$.

Question 2

Solve the recurrence:

$T(n) = c + \sum_{i=1}^{n-1}{T(i)}$

where $c$ is a constant and $T(1)$ is $O(1)$.

Question 3

In the 0-1 Knapsack problem we are given a set of items whose values are given as $v$ and weights are given as $w$, and we are asked to stash in a knapsack of capacity $W$ a maximum value subset of these items. For example, given

$$v=[20, 5, 10, 40, 15, 25]\\ w=[1, 2, 3, 8, 7, 4]\\ W=10$$

the optimal solution is 60, where we pick item 1 with weight 1 and value 20, and item 4 with weight 8 and value 40. Therefore, the total weight we pick is 9 and the total value is 60. No other selection under or equal to a weight of 10 can exceed this value.

Show that, this problem satisfies the two tenets of dynamic programming:

• optimal substructure
• overlapping subproblems

Question 4

Write the pseudocode of the dynamic algorithm for the 0-1 Knapsack problem. Discuss its time complexity and space complexity.

Answers

Question 1

$T(n) = 2T(n/4)+T(n/2)+n$

       ______________n_____________        ----> n
      |              |             |
     n/4            n/4           n/2      ----> n
  /   |   \      /   |   \     /   |   \
n/16 n/16 n/8  n/16 n/16 n/8  n/8 n/8  n/4 ----> n
                    ...

The longest path to a leaf on this tree is the rightmost path where the depth is $\lg n$. Therefore, $T(n)=O(n\lg n)$

Question 2

$T(n) = c + T(n-1) + T(n-2) + T(n-3) + ... + T(2) + T(1)$

$T(n) = T(n-1) + (c + T(n-2) + T(n-3) + ... + T(2) + T(1))$

$T(n) = T(n-1) + T(n-1) = 2T(n-1)$

This can be simply induced to $T(n)=2^{n-1}T(1)=O(2^n)$

However, this induction oversees the fact that $T(2) \neq 2T(1)$. Indeed, $T(2)=T(1) + c$. Therefore, a better induction is

$T(n)=2^{n-2}(T(1)+c)=2^{n-2}c_2=O(2^n)$

Question 3

Let's start with optimal substructure. We can code each instance of the problem with the items we have in hand and the capacity of the knapsack. Therefore, a problem instance can be represented with $(n,W)$ where $n$ represents the number of items we can consider from the beginning. For example, if given $(3,5)$, we can use the first 3 items to fill in a capacity of 5.

At this point we can see that the optimal solution to $(n,W)$ is

$max((n-1,W),(n-1, W-w[n]))$

In other words, there are two subproblems: we either include item n or exclude it in the solution. Based on the inclusion of the last item, the capacity also changes. Hence, the optimal solution contains optimal solutions to subproblems.

Now, if we look at the overlapping subproblems case, we can clearly see that subproblems can be reused in multiple larger problems. This is because in our previous decisions we may have included or excluded items in different ways such that their total weight are the same. For example, in the given example $(2,3)$ can be reached by both previously including only the fifth item with weight 7, or previously including the third and sixth items with weights 3 and 4. Therefore, the overlapping subproblems tenet also holds.

Question 4

Algorithm knapsack(v,w,n,W):

• if n == 0 or W == 0
  • return 0
• if memo[(n,w)] exists
  • return memo[(n,W)]
• if w[n-1] > W:
  • memo[(n,W)] = knapsack(v,w,n-1,W)
• else
  • memo[(n,W)] = max of
    • v[n-1]+knapsack(v,w,n-1,W-w[n-1])
    • knapsack(v,w,n-1,W))
• return memo[(n,W)]

We use memo table for memoization which requires an auxilary space of $O(k*W)$ where k is the size of v (and w). The recursion only runs if memo is found to be empty, therefore each cell is computed only once and the time complexity is $O(k*W)$.