CS241 — Spring 2018 — Assignment 1

Assignments for CS 241
Assignment 1 Assignment 2 →
Monday, May 14 at 5:00pm Tuesday, May 22 at 5:00pm
P1P2P3P4P5P6P7

In this assignment, you will begin writing very simple programs in MIPS machine language on the CSCF Linux environment.

You must prepare and test your solutions using tools available on the CSCF Student Linux Computing Environment. You must submit your solutions to the Marmoset automatic grading system available at https://marmoset.student.cs.uwaterloo.ca/, which will run them on a number of test inputs and grade them automatically. You may submit your solutions as many times as you wish prior to the submission deadline (though the number of test runs is limited; see below). Your mark is determined by the set of test inputs for which your best submission generates the correct answer, and by possible hand-marking which may be done on all, none, or some subset of the problems.

You must test your submissions prior to submitting them to marmoset. You should not rely on marmoset as a means of submission testing.

Marmoset will test your assignment using two kinds of tests: public and release tests. For each problem, there is one public test input, which is included as an example in this document at the end of each problem (except Problem 7). Once your code passes the public test, you may ask marmoset to display your mark on the remaining (release) tests. Marmoset will show you how many release tests you passed, and for most problems it will show you some of the input. You can use this information to fix your code and resubmit. For some problems, the input to the test is only partially released, or is not released at all. Course staff will not reveal this input under any circumstances.

To encourage you to start the assignment early, the number of release test runs that you may request for each problem is limited to three in every 12-hour period. Marmoset gives you three release tokens for each roblem. Each test run uses up one token. The token is returned to you 12 hours later. Your mark on a question is that of your best submission, not your most recent one.

Part I. Programming Review and Tree Processing

Problem 1 — 25% (traverse.cc or traverse.rkt)

Write a C++ or Racket program that reads a pre-order traversal of a non-empty tree from standard input and prints the corresponding post-order traversal for that tree. Each line of both the input and output will consist of two non-negative integers:

<NODE-VALUE> <NUMBER-OF-CHILDREN>

for example the following input:

1 3
2 2
5 0
6 0
3 1
7 0
4 4
8 0
9 0
10 0
11 1
12 0

corresponds to this tree, and the output of the program given the above input would be:

5 0
6 0
2 2
7 0
3 1
8 0
9 0
10 0
12 0
11 1
4 4
1 3

Be sure to test your program with a variety of different input.

You must solve this problem by constructing a tree from the given pre-order traversal, and then performing a post-order traversal on this tree. We reserve the right to hand-check that you have done this.

Submit a file called traverse.cc or traverse.rkt containing the C++ or Racket source code for your program.

Click here to return to the top of the page.

Part II. Creating binary files with cs241.wordasm

We have provided the tool cs241.wordasm that may be used to create a file whose binary content is specified using hexadecimal notation. cs241.wordasm reads the hexadecimal representation of several 32-bit words on standard input, and outputs the corresponding bytes on standard output. Any characters after a semicolon on each line are assume to be comments and are ignored.

$ cat > input
.word 0x43533234 ; C(43) S(53) 2(32) 4(34)
.word 0x3120726f ; 1(31) space(20) r(72) o(6f)
.word 0x636b730a ; c(63) k(6b) s(73) newline(0a)
$ cs241.wordasm < input
CS241 rocks
$ cs241.wordasm < input > output
$ xxd output
00000000: 4353 3234 3120 726f            CS241 ro
00000010: 636b 730a                      cks.

Note that the xxd Linux command shows the contents of the file both as hexadecimal numbers and ASCII characters. Any unprintable characters are represented by a dot.

Problem 2 — 13% (helloworld.hex)

Write a hexadecimal representation (using .word notation) of a file with contents:

Hello
from Linux!!!

You may find it useful to use the Linux command man ascii to get an ASCII code chart. Before submitting to marmoset, run the cs241.wordasm tool with your solution in standard input to check that your output is correct.

Click here to return to the top of the page.

Part III. MIPS Machine Language Programming

The mips.twoints tool loads a MIPS machine language program from a file into memory starting at location 0. It then reads two integers, stores them in registers 1 and 2, runs your program, and, when your program returns to the instruction whose address is stored in register 31, prints the values of all registers and exits. Run this tool using the command:

mips.twoints mycode.mips

replacing mycode.mips with your .mips file. Since MIPS machine language is encoded in binary, not text, you cannot create it directly using an editor like vim. You must specify your machine language program in hexadecimal and use cs241.wordasm to translate it to (binary) machine language.

For each of the following problems, create a hexadecimal representation of a MIPS machine language program that solves the problem. Test your program using cs241.wordasm and mips.twoints as follows:

$ vi mycode.hex
$ cs241.wordasm < mycode.hex > mycode.mips
$ mips.twoints mycode.mips
Enter value for register 1: 1
Enter value for register 2: 2
Running MIPS program.
...

Each problem specifies a file name for the file you are required to submit. You must use the specified file name for marmoset to recognize your submission.

You may change the value of any registers you want as long as your program exits successfully with the right answer in the designated register(s).

Problem 3 — 13% (a1p3.hex)

Write the hexadecimal notation for a MIPS machine language program that returns to the address saved in register 31. This is the only thing your program should do.

Example:

Enter value for register 1: 1
Enter value for register 2: 2
Running MIPS program.
MIPS program completed normally.
...

Click here to return to the top of the page.

Problem 4 — 13% (a1p4.hex)

Write the hexadecimal notation for a MIPS machine language program that copies the value in register 1 to register 3, then adds the values in register 1 and 3, places the result in register 4, and returns.

Example:

Enter value for register 1: 2
Enter value for register 2: 3
Running MIPS program.
MIPS program completed normally.
$01 = 0x00000002   $02 = 0x00000003   $03 = 0x00000002   $04 = 0x00000004
...

Click here to return to the top of the page.

Problem 5 — 13% (a1p5.hex)

Write the hexadecimal notation for a MIPS machine language program that determines the minimum of the values in registers 1 and 2 interpreted as two's complement integers, places the result in register 3, and returns.

Example:

Enter value for register 1: 3
Enter value for register 2: 5
Running MIPS program.
MIPS program completed normally.
$01 = 0x00000003   $02 = 0x00000005   $03 = 0x00000003   $04 = 0x00000001
...

Click here to return to the top of the page.

Problem 6 — 12% (a1p6.hex)

Write the hexadecimal notation for a MIPS machine language program that adds 42 to the value in register 2, placing the result in register 3, and returns.

Example:

Enter value for register 1: 2
Enter value for register 2: 3
Running MIPS program.
MIPS program completed normally.
$01 = 0x00000002   $02 = 0x00000003   $03 = 0x0000002D ...

Click here to return to the top of the page.

Problem 7 — 11% (a1p7.hex)

Write the hexadecimal notation for a MIPS machine language program that interprets the value in register 1 as the address of a word in memory, places the address of the following word in memory in register 3, and returns.

Click here to return to the top of the page.