formula留学生辅导、讲解Python/Java程序设计、辅导Java，c/c++语言

3 Homework 2

Problem 27. (Difficulty 3) Ancient Babylonians employed the following clever formula to

reduce multiplication to squaring:

x · y = (x2 + y2 (x y)2)/2.

Millennia have passed, but you may still find it useful.

(1) Describe an algorithm that given a 3-digit number in a base W, squares the number

using a constant number of additions but only 6 squarings of single digits, and no other

multiplication. You are allowed to multiply by W (because this isn’t really a multiplication

as it can be implemented by shifting digits).

(2) Using (1), describe an algorithm to square any n-digit number in base 10. Analyze

the running time of your algorithm. Is your runtime better or worse than computing x2 by

running Karatsuba algorithm to multiply any two integers x and y? To answer this question

you can use a calculator to compute logarithms.

(3) Suppose instead in (1) you could only use 5 squarings. (This actually can be done,

but you are not asked to do it.) What would the runtime be and how would that compare

with Karatsuba. To answer this question you can use a calculator to compute logarithms.

Problem 28. (Difficulty 3) A farmer lined up n pumpkins and n watermelons arbitrarily

on a shelf. He wants to rearrange the fruits so that all the pumpkins appear before the

watermelons. Since the shelf has no extra space, he can only do so by flipping the order of

any contiguous group of fruits. Assume that it costs time t to flip the order of any contiguous

group of t fruits. Describe an algorithm for the farmer to rearrange the fruits in O(n log n)

time.

For example, suppose each of the pumpkins and watermelons is represented by P and W

respectively. When n = 5 and the initial ordering of the 10 fruits is PWPPWPPWWW. He can

place the pumpkins before the watermelons by first flipping the 3rd through 5th fruits to get

PWWPPPPWWW, and then flipping the 2nd through 7th fruits to get PPPPPWWWWW. In this way

the farmer would spend time 3 + 6 = 9 to rearrange the fruits.