Description

Recursion, Floating Point Numbers, Linked Lists
Lab Location: EA-Z04

Purpose: More experience with MIPS assembly language programming using recursion, and linked lists. Gaining experience in MIPS program analysis by adding more to the utilities of an existing program. Floating point numbers problem solving.

Summary
Part 1 (30 points): Learning the principles of recursive programming and the implementation of dynamic link list data structure by program analysis in MIPS assembly language. Floating point number representation.

Part 2 (70 points): More experience with linked lists and recursive programming.

Refer to the linked list program given in the folder that contains this document. It can be used for creating and printing a linked list. Extend that program as suggested below.

No late submission will be accepted.

At the conclusion of the demo for getting your grade, you will upload your lab (only lab) program work to the Unilica Assignment, for similarity testing by MOSS. See Part 3 below for details.

Part 1. Preliminary Work / Preliminary Design Report (30 points)
You have to provide a neat presentation prepared by Word or a word processor with similar output quality such as Latex as you were asked in Lab 1. At the top of the paper on left provide the following information and staple all papers. In this part provide the program listings with proper identification (please make sure that this info is there for proper grading of your work, otherwise some points will be taken off).
CS224
Your Full Name/Bilkent ID

For the linked list programs only upload the utilities that you have implemented do not upload the program segments provided to you.

OK.

2. (10 points) multiplyDigits: Write a recursive MIPS subprogram that finds the multiplication of the digits of a positive integer. For example for 127 it returns 14.

3. Delete_x (10 points): Study the linked list program provided and the linked list explanation provided below in Part 2. Delete all elements from the linked list with the value x: the pointer to the linked list is passed in $a0, and the integer value of the element to be deleted is given in $a1. Return the number of counted nodes in $v0. Return the list head pointer in $v1. Are you able to return the deleted node(s) back to the heap? If not include a comment in the program to explain why.

4. Floating Point Numbers Problem Solving (0 points, Optional):
For each show your work briefly.

a. Convert the following negative number – 125.25 to IEEE 754 standard Single precision representation:
Double precision representation:

b. Convert the above decimal number to another floating point representation. In this representation For single precision use bias of 125:
For double precision it use bias of 1021:

c. Consider the following 32 bit hexadecimal number 0xc2030000. Assuming that it is a
Floating point number give its decimal equivalent:
Integer number give its decimal equivalent:

Part 2. MIPS: Creating Linked List Utility Routines (70 points)
In this part, you will write the utility functions defined below for linked lists in MIPS assembly language. Your utilities will be combined with other utility programs such as create_list and display_list, and called by a main program. [Any code other than the you are asked to write in this lab will be provided (see the Unilica folder)—you don’t need to write it]
In memory, the linked lists your utilities will work with are implemented as follows: each element consists of 2 parts: pointerToNext, and value. Each part is a 32-bit MIPS word in memory. The two parts are located in successive word addresses, with the pointerToNext being first. For example, if the byte address of the pointerToNext is 100, then the byte address of the value will be 104. Remember, MIPS memory is byte addressable.
In the last element of the linked list, the pointerToNext has value 0, in other words it is the null pointer. This means that there is not any next element. Do not forget that the last element still has a value.
Write the following linked list utility routines. Follow MIPS programming conventions in terms of using the stack and registers. Ignore the other methods not implemented. Modify the menu to include the following utilities.

1. Insert_n (10 points): Insert an element to the linked list as the nth element (n > 1): the pointer to the linked list is passed in $a0, and the integer value of the new element to be inserted is given in $a1. The register $a2 contains the value of n. The first element is in position 1, the second element in position 2, etc. If there is no nth element it is inserted to the end of the linked list. This utility will request space in memory from the system with syscall 9 and use it to create a new element, then insert the new element correctly into the linked list. The pointer to the head of the linked list should be the same as it was before the call. If the original linked list is empty no insertion is done. Return value in $v0= 0 if successful if the insertion is done, -1 otherwise.
3. SwapNodes (10 points): Swap two consecutive nodes. Note that this is not swapping values, it is swapping nodes. The node number of the initial node is given as the input of the utility. Return value in $v0 =0 if successful if the insertion is done, -1 otherwise.
4. CountCommonValues (10 points): Find the number of common values in two sorted linked lists. For example, for the lists <1, 3, 4, 8, 9> and <0, 3, 5, 9, 17, 19> it returns 2, since the common values are 3 and 9.
5. Delete_n (15 points): Delete an element from the linked list at position n: the pointer to the linked list is passed in $a0, and the position of the element to be deleted is given in $a1. If there is no nth character it must delete the LAST element of the linked list. Return value in $v0 =0 if successful, -1 if not (this happens if the linked list is empty). In either case, the return value in $v1 contains the pointer to the head of the linked list.
6. FindSumInRange (15 points): Find the summation of the linked list elements within a value range by writing a recursive program. For example, if the value range is [5, 10] for the following linked list <1, 7, 5, 2, 10, 2> this utility returns 22.
Part 3. Submit your code for MOSS similarity testing
1. Submit your MIPS codes for similarity testing to the Unilica > Assignment specific for your section.
2. You will upload one file and only the LAB work. Use filename StudentID_FirstName_LastName_SecNo_LAB_LabNo.txt
3. Upload only the programs.
4. Only a NOTEPAD FILE (txt file) is accepted.
5. Be sure that the file contains exactly and only the codes which are specifically detailed in Part 2, only the lab work. Check the specifications! Even if you didn’t finish, or didn’t get the MIPS codes working, you must submit your code to the Unilica Assignment for similarity checking.

Part 4. Cleanup
1. After saving any files that you might want to have in the future to your own storage device, erase all the files you created from the computer in the lab.
2. When applicable put back all the hardware, boards, wires, tools, etc where they came from.
3. Clean up your lab desk, to leave it completely clean and ready for the next group who will come.

Part 5. Lab Policies
1. You can do the lab only in your section. Missing your section time and doing in another day is not allowed.
4. You must be in lab, working on the lab, from the time lab starts until your work is finished and you leave.
5. No cell phone usage during lab.
6. Internet usage is permitted only to lab-related technical sites.
7. For labs that involve hardware for design you will always use the same board provided to you by the lab engineer.

2