Assignment 5, due Sep 26

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: Study machine problem 2.

   a) Write a C declaration for the struct representing one vertex in a binary tree containing the same information as is used in MP2. The code in Chapter 6 is similar to what is required, but not identical. (0.5 points)

   b) Write a traverse() routine in C that uses the struct type from part a) to do the traversal required by MP2. If you use it to traverse the tree in part c), it should output This is a small tree. (0.5 points)

   c) Write code to initialize a small tree where the strings are as follows. (0.5 points)

   • "This " – left child
   • "is a " – root
   • "small " – left child of right child
   • "tree." – right child

   Note: You are welcome to test it, but we won't run your code, we just want the code fragments requested.

2. Background: First-generation computers designed in the 1950s rarely had a call or jump-to-subroutine instruction. Machine instructions that both saved a return address and jumped to a subroutine were only added to the CPUs of computers after programmers began writing subroutines using the available instructions.

   Assignment: Write a calling sequence equivalent to JSR R1,ROUTINE that uses only JUMP ROUTINE plus explicit code to load the return address. There are several ways to do this. (0.5 points)

3. A quick question: In Chapter 6, all the examles define RETAD. Is the symbol RETAD used in any of example subroutines? If so, where? If not, why not? (0.5 points)

4. Background: Suppose the Hawk architecture did not sign-extend the displacement field used in the machine's memory reference instructins, so that all displacements were interpreted as positive numbers.

   A question: What optomizations done in Chapter 6 would no-longer work?