This will be the last lab assignment. You are asked to choose ONE out of several assignments described below. You will complete the assignment in about two and a half weeks (by 11:55pm Tuesday November 26). The complexity of each assignment is roughly equivalent to that of two of the regular lab assignments. You will do the program first in C, then in assembly in MARS. Note that some of the exercises require you to program only in assembly because you have already developed the C program in an earlier lab.
NOTE: Your score on this assignment is worth 5% of the total score for the course. Your score on this assignment will NOT be dropped when computing the final course scores and letter grades. This lab is considered a mini-project, and worth approximately two labs. But one of your lowest lab scores from amongst Labs 1-9 will be dropped.
Extra Credit: You may choose to do more than one exercise from the list below. If so, your highest scoring one will be considered as the mini project, and any additional ones will be scored for extra credit. There is no limit to how many assignments you can submit. Any extra credit awarded will not be directly added to your total score for the course. Instead, extra credit will be subjectively taken into account when letter grades are being finalized. If your total score is very near a letter grade cutoff, the instructor may bump your letter grade up if you have earned sufficient extra credit points.
Honor Code: As with all other assignments in this course, collaboration with another student or copying someone else's code, or copying code from the Internet, or taking or giving unauthorized help with this assignment is not permitted. Trust me, it's not worth it.
Please choose one of these five assignments. You may do extra assignments for extra credit.
In Lab 4 Exercise 1, we developed a C program for sorting strings in ascending order using the bubble sort algorithm. Your task is to write a MIPS assembly program to do the same. Some of the specifications are different though. The input will consist of N, the number of strings to sort, followed by the strings to be sorted, one per line. The output will simply be the sorted list of strings, one per line. Note: Please do not use your C code for Lab 4 Exercise 2 as the starting point; that exercise used C string library functions, but in assembly you will have to write your own functions for string comparison and swapping. The number of strings to sort, N, will not be more than 100, and each string will not be more than 100 characters long (including the newline and the null terminator). It would be best to modify your C program from Lab 4 to conform to these new specifications before beginning coding in assembly.
TIP: In MIPS assembly, use lb (load byte) and sb (store byte) to read and write one character (as opposed to lw/sw, which access one 4-byte integer) at a time. Accordingly, you will simply increment the address by 1 (instead of by 4) to advance to the next character in a string.
You will not submit your C program for this exercise (because it was largely done in Lab 4). Put your entire MIPS program in one file named ex1.asm. While it may be helpful to partition your assembly code into multiple files during code development, please merge them all together into one file before submitting. Sample inputs and corresponding outputs are provided under /home/students/montek/comp411/samples/labX-sort. You should try running your program on the sample input files provided, and make sure the program's output is identical to that in the sample output files.
Put the file ex1.asm on the server under the appropriate folder in your home directory (e.g., comp411lab/labX-sort). Then, run the self-checking script:
% cd ~/comp411lab/labX-sort
% cp /home/students/montek/comp411/samples/labX-sort/* .
% selfchecklabX-sort
How to submit: If the final version of your program was edited on the server, first transfer your work back to your laptop. Next, log in to Sakai in a browser window, and look for the lab under "Assignments" in the left panel. Attach the requested files and submit.
Due Date: Tuesday, November 26, 11:55 pm.
In this exercise, you will implement sorting of records. Each record has several fields: a year, a month and a day to indicate date-of-birth, and an ID (number). Sort them in increasing order, first by date-of-birth, then by ID number. That is, the records are sorted in increasing order by date-of-birth, but if two dates-of-birth are the same, then they are ordered based on the IDs. The first line of the input consists of N (the number of records contained in the input), followed by the records, with each of the fields within each record on separate lines.
Please use the following type definition for the records:
typedef struct {
int year;
int month;
int day;
int ID;
} record;
A struct in C is similar to a public class in Java, except that structs in C do not have methods. Member objects of a struct are publicly accessible using the dot notation, e.g., A.year and A.ID, where A is of type record defined above. You may use any sorting algorithm of your choice, whether recursive or simply iterative.
Your C code must define and use the struct definition of record as described above. You may NOT use separate arrays for individual fields. Instead, you must declare an array of structs, as shown below:
record data[50];
The output should be sorted in increasing order, and consist of one line per record, with all the fields listed separated by a space, e.g.:
2018 8 7 645239
where the date-of-birth is Aug 7, 2018, and the ID is 645239.
TIP: You may assume that the input will consist of at most 50 records.
Put your entire C program in one file named ex1.c. Put your entire MIPS program in one file named ex1.asm. While it may be helpful to partition your assembly code into multiple files during code development, please merge them all together into one file before submitting. Sample inputs and corresponding outputs are provided under /home/students/montek/comp411/samples/labX-struct. You should try running your program on the sample input files provided, and make sure the program's output is identical to that in the sample output files.
Put the files ex1.c and ex1.asm on the server under the appropriate folder in your home directory (e.g., comp411lab/labX-struct). Then, run the self-checking script:
% cd ~/comp411lab/labX-struct
% cp /home/students/montek/comp411/samples/labX-struct/* .
% selfchecklabX-struct
How to submit: If the final version of your program was edited on the server, first transfer your work back to your laptop. Next, log in to Sakai in a browser window, and look for the lab under "Assignments" in the left panel. Attach the requested files and submit.
Due Date: Tuesday, November 26, 11:55 pm.
In this exercise you will write a simple interpreter (or calculator) that takes in inputs in Postfix Notation. Postfix is a less ambiguous way to express arithmetic operations than the traditional "infix" syntax, without needing parentheses.
Specifically, you will be given input files with multiple lines of postfix expressions. For each line of input, you will calculate the result and output a single line with this number. For example, if the input is:
1 2 3 + + 4 2 - 3 4 * 9 4 / 0
The output should be:
6 2 12 2
You can make the following assumptions about the input:
In particular, we recommend the Left-to-right algorithm for evaluating postfix. This does require a simple stack data structure (not the same stack pointed to by $sp) to track numbers seen.
Put your entire C program in one file named ex1.c. Put your entire MIPS program in one file named ex1.asm. While it may be helpful to partition your assembly code into multiple files during code development, please merge them all together into one file before submitting. Sample inputs and corresponding outputs are provided under /home/students/montek/comp411/samples/labX-postfix. You should try running your program on the sample input files provided, and make sure the program's output is identical to that in the sample output files.
Put the files ex1.c and ex1.asm on the server under the appropriate folder in your home directory (e.g., comp411lab/labX-postfix). Then, run the self-checking script:
% cd ~/comp411lab/labX-postfix
% cp /home/students/montek/comp411/samples/labX-postfix/* .
% selfchecklabX-postfix
How to submit: If the final version of your program was edited on the server, first transfer your work back to your laptop. Next, log in to Sakai in a browser window, and look for the lab under "Assignments" in the left panel. Attach the requested files and submit.
Due Date: Tuesday, November 26, 11:55 pm.
In Lab 5 Exercise 3, we wrote a C program that takes a sequence of words and spins them into a story. In this exercise, you will convert that to a MIPS assembly program. Your assembly implementation need not be recursive. If you prefer, you can write an iterative implementation. But, in any case, make sure you have a correct corresponding C version of your code before you start on the assembly version.
TIP: All of the other instructions from Lab 5 apply. In particular, the number of animal-lyrics pairs will be determined at runtime, not to exceed 20 pairs. Each animal name will not exceed 15 characters (including terminator), and each lyrics line will not exceed 60 characters. The input ends when END is encountered when trying to read the next animal name.
You will not submit your C program for this exercise (because it was already done in Lab 5). Put your entire MIPS program in one file named ex1.asm. While it may be helpful to partition your assembly code into multiple files during code development, please merge them all together into one file before submitting. Sample inputs and corresponding outputs are provided under /home/students/montek/comp411/samples/labX-rhyme. You should try running your program on the sample input files provided, and make sure the program's output is identical to that in the sample output files.
Put the file ex1.asm on the server under the appropriate folder in your home directory (e.g., comp411lab/labX-rhyme). Then, run the self-checking script:
% cd ~/comp411lab/labX-rhyme
% cp /home/students/montek/comp411/samples/labX-rhyme/* .
% selfchecklabX-rhyme
How to submit: If the final version of your program was edited on the server, first transfer your work back to your laptop. Next, log in to Sakai in a browser window, and look for the lab under "Assignments" in the left panel. Attach the requested files and submit.
Due Date: Tuesday, November 26, 11:55 pm.
In Lab 5 Exercise 1, we wrote a recursive C program that solves a maze. In this exercise, you will convert that to a MIPS assembly program. Your assembly implementation must be recursive; otherwise no credit will be given.
TIP: You can assume that the maze size will not be larger than 25x25. Other than that, all of the instructions from Lab 5 apply.
You will not submit your C program for this exercise (because it was already done in Lab 5). Put your entire MIPS program in one file named ex1.asm. While it may be helpful to partition your assembly code into multiple files during code development, please merge them all together into one file before submitting. Sample inputs and corresponding outputs are provided under /home/students/montek/comp411/samples/labX-maze. You should try running your program on the sample input files provided, and make sure the program's output is identical to that in the sample output files.
Put the file ex1.asm on the server under the appropriate folder in your home directory (e.g., comp411lab/labX-maze). Then, run the self-checking script:
% cd ~/comp411lab/labX-maze
% cp /home/students/montek/comp411/samples/labX-maze/* .
% selfchecklabX-maze
How to submit: If the final version of your program was edited on the server, first transfer your work back to your laptop. Next, log in to Sakai in a browser window, and look for the lab under "Assignments" in the left panel. Attach the requested files and submit.
Due Date: Tuesday, November 26, 11:55 pm.