CSC 236: Introduction to the Theory of Computation

Assignment 2

Question 1. [10 marks]

In the following let A = {a1, …, an} 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

find 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 first 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 first item?

Part (2) [3 marks]

Suppose we know T(i, c), the maximum value obtained after considering the first 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 find 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 profit be the sum

of the values of all items in both bags. Find the maximum total profit 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.

pm;n

p1;1

m

n

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

1

CSC 236: Introduction to the Theory of Computation Due: July 4, 2018

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 first 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 finds 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 explanation 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 algorithm.

2

CSC 236: Introduction to the Theory of Computation Due: July 4, 2018

Part (4) [4 marks]

Use repeated substitution to get the closed form for T(n). Prove using induction that the closed

form indeed satisfies the recurrence relation.

Question 4. [9 marks]

Apply the Master Theorem to derive an asymptotic upper bound for each of the following recurrences.

Part (1) [3 marks]

T(n) = (

4 n = 1

4 · T(bn/2c) + n

2 + 8n n > 1

Part (2) [3 marks]

T(n) = (

1 n = 1

2 · T(bn/4c) + 1 n > 1

Part (3) [3 marks]

T(n) = (

10 n = 1

9 · T(bn/3c) + n

3

· log n n > 1

3

Sale!

# Theory of Computation Assignment 2

$30.00

## Reviews

There are no reviews yet.