Assignment #5

Purpose:    Become familiar with the MIPS Instruction Set, and the MIPS standard calling

convention, and basic recursion.
Points:    75


Assignment:

Write a MIPS assembly language program to determine maximum value that can be obtained from cutting a titanium rod into sections in order to maximize the total revenue.

The cost of various length rods are not linear. For example, assume that a 1 inch rod of titanium is 1 cost unit, a 2 inch titanium rod is 5 cost units, a 3 inch rod is 8 cost units and a 4 inch rod is 9 cost units.

For example, a four inch rod could be cut in a number of different ways.

















Given the following cost schedule:

lengths
1
2
3
4
5
6
7
8
9










prices
1
5
8
9
10
17
17
20
24











The goal is to find the maximum revenue possible given the rod length and the price schedule. For example, a three inch and a one inch would generate revenue of 9 (8 + 1). However, two, two inch sections would generate revenue of 10 (5 + 5).
Using the provided main, write the following MIPS assembly language functions:

    • MIPS assembly language function, showPrices(), to display a formatted price schedule. The output should include the count of prices and the formatted prices. For example, the output should include the lengths and the prices shown in formatted boxes. Since the system call does not support right-justified formatting, for digits between 0 and 9, and extra space will need to be explicitly printed. All lengths and prices will be between 1 and 99 (inclusive). The various formatting strings are predefined (i.e., the starts, dashes, and some leading spaces). You will need to use them at the appropriate times.

**********************************************************
Prices (max):
8

Lengths |
----
---- ---- ---- ---- ---- ---- ----

1 |
2 |
3| 4| 5| 6| 7| 8|
Prices |
----
---- ---- ---- ---- ---- ---- ----

1 |
5 |
8| 9|10|17|17|20|

----
---- ---- ---- ---- ---- ---- ----

Note, this will likely be the longest (most code) function. Refer to the example output for formatting.

    • MIPS assembly language function, displayResults(), to display the final result in a formatted manner. Refer to the example output for formatting.

    • MIPS assembly language recursive function, cutRod(), to determine the best price given the prices list and the rod length. The function should return the maximum price. The general recurrence relation is:

cutRod ( prices [ ] , len) =
{
0

if len=0


max
(maxTmp , prices[ i ] + cutRod ( prices[ ] , len−i −1))
if len> 0







0≤i < len



    • MIPS assembly language function, askPrompt(), to prompt the user with a passed string. The routine the should read a 'y' or 'n' from the user. If invalid input is provided, display an error message and re-prompt. Note, you only need to check for a lower case response.



Submission:

    • All source files must assemble and execute with QtSpim/SPIM MIPS simulator.

    • Submit source file
        ◦ Submit a copy of the program source file via the on-line submission

    • Once you submit, the system will score the project and provide feedback.
        ◦ If you do not get full score, you can (and should) correct and resubmit.
        ◦ You can re-submit an unlimited number of times before the due date/time.

    • Late submissions will be accepted for a period of 24 hours after the due date/time for any given lab. Late submissions will be subject to a ~2% reduction in points per an hour late. If you submit 1 minute - 1 hour late -2%, 1-2 hours late -4%, … , 23-24 hours late -50%. This means after 24 hours late submissions will receive an automatic 0.
Program Header Block

All source files must include your name, section number, assignment, NSHE number, and program description. The required format is as follows:

    • Name: <your name>
    • NSHE ID: <your id>
    • Section: <section>
    • Assignment: <assignment number>
    • Description: <short description of program goes here>

Failure to include your name in this format will result in a reduction of points.


Scoring Rubric

Scoring will include functionality, code quality, and documentation. Below is a summary of the scoring rubric for this assignment.

Criteria
Weight
Summary
Assemble
-
Failure to assemble will result in a score


of 0.



Program Header
3%
Must include header block in the


required format (see above).



General Comments
7%
Must include an appropriate level of


program documentation.



Program Functionality
90%
Program must meet the functional
(and on-time)

requirements as outlined in the


assignment. Must be submitted on time


for full score.



Example Output:

The following are an example session:


MIPS Assignment #5

Value Program



Titanium Rod Cut Maximum




**********************************************************
Prices (max): 8


---- ---- ---- ---- ----
Lengths |
---- ---- ----


1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
Prices |
---- ---- ----
---- ---- ---- ---- ----

1 |
5 |
8| 9|10|17|17|20|

---- ---- ----
---- ---- ---- ---- ----
Enter rod length (1-8): 4
is: 10




Maximum obtainable value





Enter another length (y/n)?
y




Enter rod length (1-8): 8
is: 22




Maximum obtainable value





Enter another length (y/n)?
y




Enter rod length (1-8): 6
is: 17




Maximum obtainable value





Enter another length (y/n)?
n




**********************************************************
Prices (max): 10


---- ---- ---- ---- ---- ---- ----
Lengths |
---- ---- ----


1 |
2 |
3 |
4 |
5 |
6 |
7 |
8| 9|10|
Prices |
---- ---- ----
---- ---- ---- ---- ---- ---- ----

3 |
5 |
8| 9|10|17|17|20|24|30|

---- ---- ----
---- ---- ---- ---- ---- ---- ----
Enter rod length (1-10):
4





Maximum obtainable value
is: 12




Enter another length (y/n)?
y




Enter rod length (1-10):
19





Error, invalid length. Please re-enter.



Enter rod length (1-10):
10





Maximum obtainable value
is: 30




Enter another length (y/n)?
y




Enter rod length (1-10):
2





Maximum obtainable value
is: 6




Enter another length (y/n)?
n





You have reached recursive nirvana.

Program Terminated.