Assignment 9, due Oct 28

On every assignment, write your name legibly as it appears on your University ID card! Homework is due on paper at the start of class on the day indicated (usually Friday). Exceptions will be made only by advance arrangement (excepting "acts of God"). Late work must be turned in to the TA's mailbox (ask the CS receptionist in 14 MLH for help). Never push homework under someone's door!

1. Background: To compute n mod 3, where n is a decimal number, just add up the digits of n and divide that by three. So, 128 mod 3 is the same as 1+2+8 mod 3 which is 11 mod 3 which is 1+1 mod 3 which is 2. This works in decimal because 10 mod 3 equals 1. It also works in any number base b for which b mod 3 equals 1. Using base 4, this gives us the following useful algorithm:

   unsigned int mod3(unsigned int x) {
           while (x > 3) {
                   x = sum of base 4 digits of x
           }
   	if (x == 3) x = 0;
           return x;
   }
   

   A problem: Translate the above to Hawk code. You will have to work out how to do the loop body, perhaps with an inner loop, although there are tricks that may be even faster. (1 point)

2. The display access routines putat() and putchar() implicitly operate on an output window. The Hawk monitor could have been written to support a more general windowing interface if this were made explicit, with a class window and potentially a large number of window objects. If w is a window object, then w.putchar('c') would put the character 'c' in the appropriate place in the window w, and w.putat(0,0) would make the next character output in window w appear in the upper left.

   There's quite a bit missing from the above specification: How do you create new windows? How does an application determine the size of a window? Ignore this, but do assume that there may be multiple output devices, perhaps a character-only device such as the default Hawk display and also a graphic output device more akin to what you expect on a modern computer. This means that the class window is inherently polymorphic.

   a) Give an appropriate interface specification file window.h to be used by SMAL Hawk programs. (0.5 points)

   b) Give code for w.putat(x,y) assuming that w, x and y are all local variables of the calling subroutine. (1.0 points)

3. Exercise from Chapter 11 of the Notes:

   b) (0.5 points).