Introduction to the Theory of Computation Assignment 2

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