P2 (15pt): Most graphics hardware includes support for a low-level operation called blit, or block transfer, which quickly copies a rectangular chunk of a pixel map (a two-dimensional array of pixel values) from one location to another. This is a two-dimensional version of the standard C library function memcpy(). Suppose we want to rotate an n x n pixel map 90 clockwise. One way to do this, at least when n is a power of two, is to split the pixel map into four x blocks, move each block to its proper position using a sequence of five blits, and then recursively rotate each block. (Why five? For the same reason the Tower of Hanoi puzzle needs a third peg.) Alternately, we could first recursive rotate the blocks and then blit them into place.

Please answer all parts from a-e.

For part a, give the pseudocode to show the correctness of both methods

DDD AB CD 5 blits | DB recurse AB C D recurse 5 blito D Figure 1. Two algorithms to rotate pixel map. (a) Prove that both versions of the algorithm are correct when n is a power of 2. (b) Exactly how many blits does the algorithm perform when n is a power of 2? (c) Describe how to modify the algorithm so that it works for arbitrary n, not just powers of 2. How many blits does your modified algorithm perform? (d) What is your algorithm's running time if a kxk blit takes (ka) time? (e) What if a k x k blit takes only O(k) time? DDD AB CD 5 blits | DB recurse AB C D recurse 5 blito D Figure 1. Two algorithms to rotate pixel map. (a) Prove that both versions of the algorithm are correct when n is a power of 2. (b) Exactly how many blits does the algorithm perform when n is a power of 2? (c) Describe how to modify the algorithm so that it works for arbitrary n, not just powers of 2. How many blits does your modified algorithm perform? (d) What is your algorithm's running time if a kxk blit takes (ka) time? (e) What if a k x k blit takes only O(k) time