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 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.
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).
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; A; :::; 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 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?)