$30.00
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

The wellknown 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.

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

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).

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.

Divide and conquer for the Tromino Puzzle.
Use divide and conquer to design an algorithm/strategy to ll up any 2^{n} 2^{n} 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/ puzzle8by8/ ). You can play with it to get some idea. (Hint: assuming that you can solve the problem of 2^{n} ^{1} 2^{n} ^{1} with an arbitrary cell removed, how can you use that to solve the problem of 2^{n} 2^{n} size?)