Practice question set #2 Solution

Description

This set of practice questions help you review the following concepts:

Designing divide and conquer algorithms and characterize its run time using recurrence relations. More proof by induction, particularly using it to prove correctness of recursive algorithms

1. The well-known mathematician George Polya posed the following false \proof” showing through mathematical induction that actually, all horses are of the same color.

Base case: If there’s only one horse, there’s only one color, so of course its the same color as itself.

Inductive case: Suppose within any set of n horses, there is only one color. Now look at any set of n + 1

horses. Number them: 1; 2; 3; : : : ; n; n + 1. Consider the sets f1; 2; 3; :::; ng and f2; 3; 4; :::; n + 1g. Each is a set of only n horses, therefore within each there is only one color. But the two sets overlap, so there must be only one color among all n + 1 horses.

Identify what is wrong with this proof.

2. DPV 2.17. You need to 1) describe the algorithm in clear pseudo-code; 2) prove its correctness (via induction) and 3) show that its run time is O(log n).

3. Given two sorted arrays a[1; :::; n] and b[1; :::; n], given an O(log n) algorithm to nd the median of their combined 2n elements. (Hint: use divide and conquer).

4. Given an array A of n distinct numbers whose values A[1]; A[2]; :::; A[n] is unimodel: that is, for some index

p 2 [1; n], the values in the array rst increases up to position p, then decrease the remainder of the way. For example [1; 2; 5; 9; 7; 3] is one such array with p = 4. Please design an O(log n) algorithm to nd the peak p given such an array A.

5. Divide and conquer for the Tromino Puzzle.

Use divide and conquer to design an algorithm/strategy to ll up any 2n 2n board with one square removed using tromino tiles. A tromino tile is a piece formed by three adjacent squares in the shape of an L and it can be

rotated to t the board. See the gure below for an example solution for a 8 8 board with cell (4; 5) removed. The following page contains an interactive version of this puzzle (https://www3.amherst.edu/~nstarr/trom/ puzzle-8by8/ ). You can play with it to get some idea. (Hint: assuming that you can solve the problem of 2n 1 2n 1 with an arbitrary cell removed, how can you use that to solve the problem of 2n 2n size?)