CS MIPS Assembly Language with Program as Data, Recursion, Linked Lists Solution

Part 1 & 2. Preliminary Work (40 points)

You have to provide a neat presentation prepared in txt form. Provide following five lines at the top of

your submission for preliminary and lab work (make sure that you include the course no. CS224,

important for ABET documentation).

CS224

Lab No.

Section No.

Your Full Name

Bilkent ID

Make sure that you identify what is what at the beginning of each program by using proper comments.

Important Notes

    1. Assume that all Inputs are Correct. In all lab works, if it is not explicitly stated, you may assume that program inputs are correct.

    2. Provide simple text messages to help our TAs to understand and validate your program. Make sure that your program can be validated by text output you provide in your programs. This is mandatory.

    3. In the subprograms you are not allowed to use $t registers. Instead of $t registers use $s registers and make sure that you push $s registers you use to the stack. Before returning to the caller make sure that you restore the values of the $s registers from the stack.

    4. A linked list construction and listing program is provided. Use it for any case you find appropriate. See the related Moodle folder.

Part 1.

instructionCount (20 Points): Write a non recursive subprogram that counts the number add (e.g., "add $t0, $t1, $t2") and lw (load word) instructions and returns these counts as its results. The address of the first instruction to be considered in counting is given in $a0, and the address of the last instruction to be considered in counting is given in $a1. Your main program should invoke this subprogram twice: first for the main (itself), and for the second time for the subprogram.




3

As you see, in this program your main program becomes an input data and in the second call the subprogram becomes its own data (like an MD operator operating itself). Provide meaningful output in main so that you and your TA can validate the correctness of your program.

Note that, in our practice to simplify things, we write MIPS programs in a single source file; therefore, all labels are at the global scale. For example, if you label the first instruction of your subprogram with the label L1, and its last instruction with the label L2, you can pass these addresses to the subprogram with load address instructions in main (la $a0, L1; la $a1, L2).

Part 2.

RecursiveDivision (20 points): Write a recursive MIPS subprograms that finds the division of a positive number by another positive number by successive subtractions. Your main program must provide a user interface: It should get a pair of numbers from the user provide the answer, and should ask the user if the user wants to continue, if so it should ask the next pair of numbers, etc.

Part 3 & 4 & 5. Lab Work (60 points)

In the following parts first construct a linked list that contains ten numbers (1, 2, 3, .... 10 in this order).

For the linked list construction use the program provided to you (modify it as needed). Display the linked list again with the program you are given to make sure that the linked list is constructed properly. After that do what you were asked in each part below. You must provide simple easy to follow program output with proper messages for the user (your TA).

Implement each part in a separate source program for easy grading and to prevent confusion during grading.

Part 3.

DisplayReverseOrderRecursively (20 points): Write a recursive program to display the elements of a linked list in reverse order (10, 9, ... 1). The list head is passed in $a0. Provide a simple user interface.

Part 4.

DuplicateListIterative (20 points): Write a non recursive subprogram to duplicate a linked list. When called $a0 points to the original list. It returns the new list head in $v0. Provide a simple user interface.

Part 5.

DuplicateListRecursive (20 points):

Write a recursive subprogram to duplicate a linked list. When called $a0 points to the original list. It returns the new list head in $v0. Provide a simple user interface.


Aim to complete lab part at home before coming to the online lab.


4
Part 6. Submit Your Code for MOSS Similarity Testing

    1. Submit your Lab Work MIPS codes for similarity testing to Moodle.

    2. You will upload one file. Use filename StudentID_FirstName_LastName_SecNo_LAB_LabNo.txt

    3. Only a NOTEPAD FILE (txt file) is accepted. No txt file upload means you get 0 from the lab. Please note that we have several students and efficiency is important.

    4. Even if you didn’t finish, or didn’t get the MIPS codes working, you must submit your code to the

Moodle Assignment for similarity checking.

    5. Your codes will be compared against all the other codes in the class, by the MOSS program, to determine how similar it is (as an indication of plagiarism). So be sure that the code you submit is code that you actually wrote yourself !

Part 7. Lab Policies (Reminder)

    1. As indicated in Lab1: Attendance is mandatory and the preliminary work is graded only if you submit your lab work with the observation/permission of your TA.

    2. You can do the lab only in your section. Missing your section time and doing in another day is not allowed.

    3. The questions asked by the TA will have an effect on your lab score.

    4. Lab score will be reduced to 0 if the code is not submitted for similarity testing, or if it is plagiarized. MOSS-testing will be done, to determine similarity rates. Trivial changes to code will not hide plagiarism from MOSS—the algorithm is quite sophisticated and powerful. Please also note that obviously you should not use any program available on the web, or in a book, etc. since MOSS will find it. The use of the ideas we discussed in the classroom is not a problem.

    5. Your lab attendance is tracked by the Zoom system. Please also see lab policies no. 1 item.



























5