Assignment 8, due Oct 24

On every assignment, write your name legibly as it appears on your University ID card! Homework is due on paper in discussion section on Thursday. Some parts of assignments may be submitted on-line and completed in discussion section. 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: Look at machine problem 4. It asks you to write a SMAL Hawk version of Quicksort. You won't find that in a textbook or a web search, but you can find plenty of implementations of Quicksort written in C. Most of those sort arrays of integers, not arrays of strings. Look at several of them, find one with code you are comfortable with -- aim for simplicity here, because you will end up having to make it work!

   a) Give valid C code for a version of Quicksort that sorts an array of pointers to strings, using strcmp to compare strings. (0.5 points)

   b) Write a main program to test it on an array of pointers to strings, printing out all the strings with puts after it is sorted. (0.5 points)

   Note: You are advised to run the code to make sure it works, but we just want it on paper. The purpose of this assignment is to set you up for MP4.

2. Background: Chapter 14 of the Hawk manual gives optimal Hawk code for multiplying by constants up to 38.

   a) Write the best Hawk code you can to multiply by 73. (0.5 points)

   b) Write C code equivalent to your answer to part a); a good compiler might replace the expression i*73 with this on a machine like the Intel Pentium where the multiply instruction is at least 10 times slower than an add. (0.5 points)

3. Background: The code for DIVIDEU given in Chapter 9 divides a 32-bit divisor into a 32-bit dividend, proucing a 32-bit quotient and a 32-bit remainder. In fact, division is well defined for a 32-bit divisor dividing into a 64-bit remainder, so that, for example, 1,000,000,000,000 divided by 1,000,000 gives 1,000,000. The dividend, in this example, can be represented in 40 bits.

   Problem: Give SMAL Hawk code for an unsigned divide routine allowing a 64-bit dividend. Hint: The code is a surprisingly simple variation on code given in the Hawk manual and the notes. (1 point)