Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP202

HALF TERM EXAM:  CLASS TEST 2019/20

Complexity of Algorithms

Part A: THIS PART IS NOT INCLUDED

 

Part B:

1. We consider the following problem:  Given a sorted array of n distinct integers A[1, ..., n] (where “sorted” means in the increasing order), you want to find out whether there is an index i for which Ai ] = i.

(a) [5 marks] Design a divide-and-conquer algorithm that solves this problem in time O(log n).

(b) [5 marks] Give an argument that your algorithm indeed has running time O(log n) by for- mulating an appropriate recurrence equation and solving it.

(c) [3 marks] Give an argument that your algorithm is correct.

Solution:

(a) We will first define a procedure FindIndex(A[i..j]) for any two integer indices i,j such that 1 < i < j < n.

The procedure FindIndex(A[i..j]) first checks if i = j and if indeed it is the case then if A[i] = i then it returns “yes”; and if A[i i then it returns “no”.

If i < j then FindIndex(A[i..j]) checks if A[|(i + j)/2|] =  |(i + j)/2|, and if yes then it returns “yes”.

Otherwise, if A[|(i + j)/2|] > |(i + j)/2|, then it calls recursively FindIndex(A[i..|(i + j)/2| - 1]). Finally, if A[|(i + j)/2|] < |(i + j)/2|, then it calls recursively FindIndex(A[|(i + j)/2| + 1..j]).     The final algorithm then just calls FindIndex(A[1..n]).

(b) If T(n) denotes the running time of the algorithm FindIndex(A[1..n]), then we have that T(n) = T(n/2)+c, where c is a fixed constant. By the Master Method, we see that a = 1, b = 2, so nlogb a  = n0  = 1, and f(n) = c. This means that f(n) e 9(nlogba logk n) for k = 0. Therefore, we are in case 2 of the Master Method, which implies that T(n) = 9(logk+1 n) = 9(log n).

(c) First note that the numbers in the array are only integers.  If FindIndex(A[i..j]) has A[|(i + j)/2|] = |(i + j)/2|, then of course the outcome “yes” is correct.

Otherwise, if A[|(i + j)/2|] > |(i + j)/2|, then we know that the integer A[|(i + j)/2|] is larger than the index |(i + j)/2| by at least 1. Now, because integers in array A are all distinct and sorted in the increasing order, the next integer in AA[|(i + j)/2| + 1], is strictly larger than its index |(i + j)/2| + 1, that is, A[|(i + j)/2| + 1] > |(i + j)/2| + 1. We can continue this reasoning showing that A[|(i + j)/2| + 2] > |(i + j)/2| + 2, A[|(i + j)/2| + 3] > |(i + j)/2| + 3, and so on. This means that in the right half of the array A[|(i + j)/2|..j] there cannot exist any solution to the problem. Indeed, the algorithm in this case looks for a possible solution in the left half by recursively calling FindIndex(A[i..|(i + j)/2| - 1]).

The argument in the final case if A[|(i + j)/2|] < |(i + j)/2| is analogous and we skip it.

2. We consider the following tiling problem: We are given a rectangular grid of squares of size 2 × n, for any integer n 2 1. That is, this grid can be viewed as an array consisting of two rows of n identical squares each, or n columns of 2 identical squares each. This grid is naturally ordered from left to right, where the left-most column has number 1 and the right-most column has number n.

We will refer to the left-most upper square as s1,1 , to the left-most lower square as s2,1  (they both form the first column). The second column has s1,2  as the upper square and s2,2  as the

lower square, and so on. Thus the last, right-most, column has s1,n  as the upper square and

s2,n  as the lower square. Here is an example of the grid for n = 7:

We are now given a collection of n identical, non-transparent, domino tiles, each of size 1 × 2, where its two identical squares have the same size as the squares in the grid.  Each such domino tile can be placed on the grid horizontally or vertically, where the two squares of the domino tile are placed on two adjacent squares of the grid, perfectly covering these two adjacent squares of the grid. We call a tiling of the grid perfect if all n domino tiles are used and each square of the grid is covered by exactly one of the squares of some domino tile.     Let t(n) denote the number of all distinct perfect tilings of the whole grid with all n domino tiles, for any integer n 2 1. For instance t(4) = 5.

(a) [5 marks] What are the values t(1), t(2), t(3)? Provide arguments to your answer in each case, and, in addition provide an argument that t(4) = 5.

(b) [5 marks] Derive a recurrence relation for t(n) in terms of t(n - 1) and t(n - 2), for each integer n 2 3. Give an argument justifying your derivation.

(c) [3 marks] Give an argument showing that t(n)  2 2n/2  for any n  2 2.  You may prove this fact using your recurrence from (b), either by induction on n, or by using a substitution method.

Solution:

(a) t(1) = 1, because the only possible tiling is l; t(2) = 2, because the two tilings are ll and =; t(3) = 3, because all tilings are l =, = l and lll; for t(4) = 5 all tilings are: ll =, ==, = ll, l = l, and llll.

(b) Given any n 2 3, we observe that if the left-most column is covered with a vertical tile l, that is squares s1,1  and s2,1  are covered, then the remainder of the problem is the number of covering a 2 × (n - 1) grid with n - 1 domino tiles and this number is exactly t(n - 1).  On the other hand if any of the left-most squares, say s1,1 , is covered by a horizontal domino tile, then this tile also covers square s1,2 .  Then, we observe that the second left-most square, s2,1 , must also be covered by a horizontal domino tile, and these two tiles must be perfectly aligned. Therefore, these two horizontal tiles cover the first two left-most columns, or, in other words, they cover the following squares: s1,1  and s1,2  (covered by the first horizontal tile), and s2,1  and s2,2  (covered by the second horizontal tile). This defines now the sub-problem of the number of perfect tilings of the remaining grid of size 2 × (n - 2) with n - 2 remaining domino tiles and this number is exactly t(n - 2). To summarise, we obtain that t(n) = t(n - 1)+t(n - 2).

(c) Induction base: t(2) = 2 2 22/2 , t(3) = 3 2 23/2  s 2.829.

Induction step:  By the recurrence and by the induction hypothesis for n - 1 and n - 2, we have that t(n) = t(n - 1) + t(n - 2) 2 2(n − 1)/2 + 2(n −2)/2  > 2 . 2(n −2)/2  = 2n/2, which proves the induction step.

The substitution method can be used by observing that t(n - 1) 2 t(n - 2) and then by the recurrence we obtain that t(n) = t(n - 1)+t(n - 2) 2 2 . f(n - 2), and by repeating the inequality t(n) 2 2 . f(n - 2) succesively i = (n - 2)/2 times, and by the fact that t(2) = 2, we obtain that t(n) 2 2i  . t(n - i . 2) = 2n/2 .