Assignment 2 Solution

Question 1.    [10 marks]

In the following let A = fa1; :::; ang be a set of n items where item ai has value vi and capacity ci. Suppose you have a bag with maximum capacity C. We will develop a recurrence relation to nd the maximum value obtained by a subset of A whose capacity does not exceed C. Note: this is the classic Knapsack Problem. Many solutions on-line use linear programming or dynamic programming, but this is not what we are asking you to do here; you do not need anything other than the material you learned in class to answer this question.

Part (1)    [2 marks]

Let T (i; c) be the maximum value obtained after considering the rst i items with total capacity c. Come up with an equation for T (0; c) and T (1; c) i.e. what is the maximum value obtained if we considered none of the items? Only consider the rst item?

Part (2)    [3 marks]

Suppose we know T (i; c), the maximum value obtained after considering the rst i items with total capacity c. Find an equation for T (i + 1; c) in-terms of the values T (i; 0); T (i; 1); : : : ; T (i; c). Use this equation along with part one to come up with a general recurrence relation for T (k; c). How would we nd the maximum value obtained by a subset of A whose capacity does not exceed C?

Part (3)    [5 marks]

Suppose we have two bags with capacities C1 and C2 respectively. Let the total pro t be the sum of the values of all items in both bags. Find the maximum total pro t subject to the capacity constraints as we did for the one bag case above.



Question 2.    [11 marks]

In the following, consider an m n grid as shown in Figure 1. The bottom left point and top right points are p1;1 and pm;n respectively. All other points are indexed in the standard way.

N


 PM;N




M




P1;1

Figure 1: The grid of points we will consider for this problem.



1
CSC 236: Introduction to the Theory of Computation    Due 



Part (1)    [6 marks]

Find a recurrence relation for the number of axis aligned rectangles in an m n grid. See Figure 2 for an example where m = 3 and n = 3. Explain your process.













Figure 2: Example with m = n = 3. There are nine possible axis aligned rectangles possible.

Part (2)    [1 mark]

Hypothesize a closed form for your recurrence relation. Hint: check to see if your closed form is correct in the special case when m = n using the on-line encyclopedia of integer sequences.

Part (3)    [4 marks]

Prove your closed form using induction.



Question 3.    [10 marks]

An array is said to be rotated by one space if all its elements are moved ahead circularly, that is every element is moved to the next position and the last element is moved to the rst position. For instance the array [1; 2; 3; 4; 5] rotated by one space gives [5; 1; 2; 3; 4]. Rotating an array by r spaces simply means rotating it by one space r times. So the array [1; 2; 3; 4; 5] rotated 2 spaces will give [4; 5; 1; 2; 3] and rotated 5 spaces will give [1; 2; 3; 4; 5] back again.

The input is an array A of n distinct elements which is sorted in ascending order and then rotated a certain number of spaces. (The number of spaces the array is rotated may be zero as well.) You have to devise an algorithm minimum, which nds the minimum element of the array.

Part (1)    [2 marks]

Devise an O(n) brute-force algorithm for minimum in Python notation. Give an informal expla-nation of why the time complexity is O(n).
Part (2)    [3 marks]

Devise a divide-and-conquer algorithm for minimum which performs better than the brute-force version. (Be careful of the edge and base cases.)

Part (3)    [1 mark]

Give recurrence relation T (n) for the worst-case time complexity for the divide-and-conquer algo-rithm.



2
CSC 236: Introduction to the Theory of Computation    Due 



Part (4)    [4 marks]

Use repeated substitution to get the closed form for T (n). Prove using induction that the closed form indeed satis es the recurrence relation.



Question 4.    [9 marks]

Apply the Master Theorem to derive an asymptotic upper bound for each of the following recur-rences.

Part (1)
[3 marks]
(4  T ( n=2 ) + n2


T (n) =

+ 8n  n > 1



4




n = 1




b
c

Part (2)
[3 marks]


(2  T ( n=4 ) + 1  n > 1

T (n) =






1


n = 1







b  c

Part (3)
[3 marks]
(
9  T (bn=3c) + n3


T (n) =


log n  n > 1



10



n = 1




































3