Assignment 2, due Feb 3

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list!

Homework

Do problems 4 (1.5), 6 (2.0), and 8 (0.5) at the end of chapter 2 of the notes. You may write code in the language of your choice, and although we want readable code free of obvious errors, you need not turn it in in machine readable form.

Machine Problem 1

Due February 7

Create an empty directory called mp1 on any Unix compatable machine connected to the Math Science server, using your CS departmental account, and download into this directory a copy of this file:

http://homepage.cs.uiowa.edu/~dwjones/syssoft/hw/mp1.txt

This file contains 1552 lines of text. Rename the file mp1.shar since the contents is a Unix shell archive, and the extension .shar is traditional for that type of file. Then follow the instructions in the first few lines of mp1.shar for un-archiving the file. You will end up with a directory holding a C program that has been written fairly carefully in terms of the style guidelines found in:

http://homepage.cs.uiowa.edu/~dwjones/syssoft/style.html

Then, follow the instructions in the file README that was produced by the previous step. This will make a program called eal because it is an assembler for our example assembly language. Verify that it works by running it with the command eal -help; if it works, it will respond with a brief help message.

Edit the file Makefile so that the eal -help output indicates that the program is Version V1.0 and that it is written by you, and add a line to the revision history indicating that V1.0 is yours. Make the application again (with the Unix make command) and verify that the help message has changed to include your extensions.

Now, do the following:

Write a "program" in our example assembly language, with an appropriate comment at the start that claims it as your solution to MP1; this program (which is not really a program) should build a binary search tree in memory, using the following structure for each node:

	struct node {
		struct node * left;  /* pointer to left child */
		struct node * right; /* pointer to right child */
		int key;             /* the key value stored in this node */
	};

This structure is given in C; your job is to show 8 instances of this structure, in memory, that represent the following tree, shown in pictoral format:

       ROOT
           \
            4
           / \
          2   5
         / \   \
        1   3   7
               / \
              6   8

Assume that all integers and pointers are 16 bits, two bytes. The root pointer should have the symbolic name ROOT (very creative), and the root pointer should be stored at location zero. Null pointers should be represented by the value zero. The entire structure should be created using our example assembly language's B and W directives, along with symbolic labels, numeric operand field values, and symbolic operand field values. No machine code is involved! You are using the assembly language to directly create a data structure in memory.

Your assembly code must begin with a comment claiming ownership of the result, giving your name and the date, along with a statement that this is a solution to machine problem 1. Save the code in a file named mp1.a in your mp1 directory.

You should assemble your code with your version of the eal assembler, and you should turn in a paper copy of the assembly listing the assembler produces when it assembles this file.

Once you have produced your listing, DO NOT MAKE ANY CHANGES TO FILES IN YOUR mp1 DIRECTORY! We reserve the right to check the on-line copy of your work or to grade your work entirely on the basis of the on-line copy. Your on-line copy and the date-of-last-modification information for each file are insurance against lost or stolen paper copies, and the on-line date-stamp will be inspected if there is any suspicion of academic misconduct.