CP2003 Assignment One - Assembly Language

Due Date - 5PM, Friday September 4

Weighting - 15%

This assignment provides a gentle introduction to the agony and ecstasy of Assembly Language programming. It is worth 15% of your CP2003 grade, so should be taken seriously. Check the assignment one web page as often as practical for any updates to the assignment (notices of these will also be placed on the main CP2003 page and stated in lectures).

This is not a simple assignment, so it is advised that you get started as soon as possible. A large part of the problem involves familiarising yourself with assembly language. The sooner you get started, the easier you will make it on yourself.

Using SPIM

Following is a very brief outline on how to execute your program using spim on your barra account.

write your assembly language program into single text file using your favourite editor (pico, vi, emacs, etc.); refer to example programs in the lecture notes for guidelines on how to write a complete program
in order to run your programming using spim, at the barra command line type the command:
```
  spim -file filename
```
where filename is the name of the file containing the assembly code
more information on the ins and outs of spim can be found in the man pages, by executing the command man spim or man xspim at the command line
it is also possible to download spim for use on PC. The URL for this is:
```
  http://www.cs.utah.edu/~cs363/software.html
```
note, however, that your assembly language program must execute on barra when the program is tested by the marker - that is, the excuse ``but it worked fine at home'' will not be accepted if the program does not run on barra. It is the students responsibility to make sure their program successfully ported to barra.

Marking

The assignment will be marked for good programming style (indentation, spacing and appropriate comments), as well as clean execution (the programs should work!). Don't underestimate the importance of comments - poorly commented code will result in the usual loss of marks. It is important to be concise and complete in your commenting (make sure you add comments, but don't go overboard).

The mark for the assignment will be out of 100, with the marks to be awarded for each question presented below with the problem description.

Question One - A Case Converter (20 marks)

The problem here is to first prompt the user for input and then read in a stream of characters (possibly consisting of lower case or upper case letters, numbers, spaces or arbitrary punctuation). The next step is to traverse that stream changing the case of lower case letters only - all other characters should remain unchanged.

So, for example, your program should produce something like this:

Give Input String: 
AcDwa? @#kjKh  hlbLq;|b;kjeok!h@KJIhjk#kI(a90E
ACDWA? @#KJKH  HLBLQ;|B;KJEOK!H@KJIHJK#KI(A90E

Where the first and third lines are output from your program and the middle line is input from the user.

You can also assume a maximum of fifty characters of input.

Question Two - A Letter and Word Counter (30 marks)

The problem in this question is to read in a sentence from the user and count the number of characters in each word and the number of words in the sentence. Some things to note here:

the sentence can be up to 50 characters in length
the sentence is always ended with a . character
can assume that only one line of input is provided by the user

An example of what your program should look like when executing correctly:

Enter Input Sentence:
RAM disk is not an installation procedure.
Length of each word 
3
4
2
3
2
12
9
Number of words - 7

Where the second line is the sentence input by the user and all other lines are output of the program.

Question Three - Binary Tree Implementation (60 marks - 10 bonus)

The problem here involves building an almost complete binary tree (i.e. a tree built left to right, level by level) given a series of inputs from the user. Specifically, the user must initially be prompted for the desired height of the tree and this value must be read by the program. The next step involves looping and asking the user to enter the appropriate number of keys to fill up the tree, and insert these these keys so as to form a binary tree (not a binary search tree).

Additionally, the user can decide to end input at any time by enterring a zero. Your program should then stop prompting for input and print out the tree.

Now, it would be very complicated to represent a tree in memory using assembly language, so we use an array to simulate a tree. A tree can be simulated by an array using the following principles:

  If the nodes of a complete tree are numbered from 1 to n, level
  by level, from left to right, then the following relations hold for node
  p:

    if p is the i'th element in the array, then
    p's left child is at position 2i and p's right
    child is at position 2i + 1.

You can assume that the user will always enter valid integer and that none of the integers enterred are of the same value (for example, the value 2 can only be enterred in the tree once). In order to show that you are inserting into the tree correctly you must print a ``level-order traversal'' of the tree after all the keys have been read in. Bonus marks will be awarded for providing other traversals (5 marks for inorder traversal and 5 more marks for doing both preorder and postorder traversals).

Examples of what your program should look like when executing correctly:

Give height of the tree: 
2
Give keys (0 to end):
input an integer> 5
input an integer> 2
input an integer> 1
input an integer> 3
input an integer> 7
input an integer> 6
input an integer> 8

Level-order traversal: 
5 2 1 3 7 6 8 

In-order traversal:
3 2 7 5 6 1 8

Pre-order traversal:
5 2 3 7 1 6 8

Post-order traversal:
3 7 2 6 8 1 5

Example 2:

Give height of the tree: 
2
Give keys (0 to end): 
input an integer> 1
input an integer> 3
input an integer> 0

Level-order traversal: 
1 3 0 0 0 0 0 

In-order traversal:
0 3 0 1 0 0 0

Pre-order traversal:
1 3 0 0 0 0 0

Post-order traversal:
0 0 3 0 0 0 1

Getting Help

Students are encouraged to discuss the problems with each other but in NO circumstances are students to work together (see the note below of plagiarism). For other assistance, consult your tutor who may provide you with limited guidance on how to attack a particular problem. Tutorials will be the best time to discuss problems with your tutor.

Submission Information

The solutions for the three questions must be coded in three different files. By the due date you must submit (via email) the three different files to your lecturer. This can be done via elm on your barra account as follows:

  elm alan@cs.jcu.edu.au < question1.s
  elm alan@cs.jcu.edu.au < question2.s
  elm alan@cs.jcu.edu.au < question3.s

where questionx.s is the file containing the solution to question x.

Assignments submitted after the due date will be subject to a ten percent per day penalty. Extensions of the due date will be granted if supporting documentary evidence is supplied (e.g. a doctor's certificate). Applications for an extension must be made to the lecturer before the due date.

Plagiarism is considered a serious offence. Plagiarism will result in a severe loss of marks for all guilty students involved, also punitive marks and possible expulsion from the subject/JCU will be considered (especially for repeat offenders). Students are not allowed to work in groups for this assignment and if obvious similarities are found in large amounts of code, this will constitute plagiarism and will not be tolerated.