CS 110: Elements of Computing. Instructor: Jim Aspnes

Homework Five Solutions

Due Friday, October 25th, 2002, at 5:00pm.

Your task

Do problems 29, 44, and 45 from pages 200-202 of Brookshear.

Submitting your solution

Write up an email message containing your full name and the answer to these problems in plain text format (this means no HTML or Microsoft word documents), and send it to aspnes+110-02-5@cs.yale.edu. (Note: this is not the same email address as for previous homework.)

Solution:

Problem 29

Test1 prints the numbers 1, 2, 3, 4. Test2 prints 4, 3, 2, 1.

Problem 44

For addition: If you don't count the carries as a separate addition, adding two n-digit numbers takes exactly n one-digit additions. If you do count the carries, you may have as many as 2n one-digit additions. In either case the asymptotic cost is Theta(n).

For multiplication: In the usual multiplication algorithm, every digit in the first number is multiplied by every digit in the second number, for a total of n² = Theta(n²) digit multiplications (plus some additions, but the problem doesn't ask about those.)

Problem 45

Maximizing difference: make one of the groups empty. Total cost: Theta(1) (or Theta(n) if you actually have to copy the input to the output).

Minimizing difference: Try all 2ⁿ possible splits, pick the best one. Checking a split costs Theta(n) work (to add up the ages in each group). Total cost: Theta(2ⁿ n).