Lab X: Choose One OR Bring-Your-Own

This will be the last lab assignment. You are asked to choose ONE out of several assignments described below, OR propose your own mini-project. You will complete the assignment in a little over two weeks (by Dec 1). If you choose to propose your own, the complexity of what you propose should be roughly equivalent to two of the regular lab assignments. You will do the program first in C, then in assembly in MARS.

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 two of your lowest lab scores from amongst Labs 1-9 will be dropped.

Please choose one of these four assignments, or propose your own.


Recursive Quick-Sort or Merge-Sort

Write a recursive implementation of quick-sort or merge-sort (or any other sorting method, but it must be recursive) for integers in increasing order. The input will consist of N, the number of integers to sort, followed by the integers to be sorted, one per line. The output will simply be the sorted list of integers, one per line.

TIP: The number of integers to sort, N, will not be more than 50.

Test Inputs, Due Date and Submission Procedure

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/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 C and assembly programs into a folder on classroom.cs.unc.edu, and then run the selfchecking and submit scripts as follows:

% cd ~/comp411lab/labX
% /home/montek/comp411/bin/selfchecklabX-sort
% /home/montek/comp411/bin/submitlabX-sort

Due Date: Friday, December 1, 11:59 pm.


Towers of Hanoi

Write a recursive implementation of the Towers of Hanoi game. The input will be a small number, N, which represents the number of disks, numbered 0 to N-1. The output will be a series of moves, one per line, which look like, "Move disk 3 from Peg 1 to Peg 2".

TIP: You do not need to maintain arrays or stacks for each of the pegs. My C code for the body of the recursive procedure is a total of 4 lines. As a hint, my implementation has the following declaration of the recursive procedure. Within the body of the procedure, the single disk that is actually moved is disk #N. You can find the algorithm here (see "Recursive solution").

    void hanoi(int N, int A, int B, int C)

Test Inputs, Due Date and Submission Procedure

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/montek/comp411/samples/labX/hanoi. 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 C and assembly programs into a folder on classroom.cs.unc.edu, and then run the selfchecking and submit scripts as follows:

% cd ~/comp411lab/labX
% /home/montek/comp411/bin/selfchecklabX-hanoi
% /home/montek/comp411/bin/submitlabX-hanoi

Due Date: Friday, December 1, 11:59 pm.


Picture Manipulation

Building on the PPM/PGM picture manipulation exercise of Lab 7, you are to implement rotation and blurring of PGM (grayscale only) pictures. Specifically, given an input PGM image on standard input, the output will be a PGM image that has been rotated 90 degrees clockwise, and each pixel has been "blurred" by replacing it with the average of the nine pixels in a 3x3 square centered on that pixel. Pixels that are on the four border lines are left untouched.

TIP: You can assume that the input picture will always be of size 64x64 pixels.

Test Inputs, Due Date and Submission Procedure

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/montek/comp411/samples/labX/pgm. 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 C and assembly programs into a folder on classroom.cs.unc.edu, and then run the selfchecking and submit scripts as follows:

% cd ~/comp411lab/labX
% /home/montek/comp411/bin/selfchecklabX-pgm
% /home/montek/comp411/bin/submitlabX-pgm

Due Date: Friday, December 1, 11:59 pm.


Simple Sort of Structures

In this exercise, you will implement sorting of records. Each record has two fields: a name (string) and an ID (number). Sort them in increasing order, first by name, then by ID number. That is, the records are sorted in increasing order by name, but if two records have the same name, 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 the name on one line and the ID on the next line.

Please use the following type definition for the records:

    typedef struct {
      char Name[20];
      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.Name 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 Names and IDs. Instead, you must use an array of structs, largely as shown below:

    typedef struct {
      char Name[20];
      int ID;
    } record;

    record data[50];

TIP: You may assume that each Name field will fit within the 20 characters provided (including any newlines and null characters). You may also assume that the input will consist of at most 50 records. You are allowed to use standard C string functions (e.g., strcmp(), strcpy(), etc.).

Test Inputs, Due Date and Submission Procedure

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/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 C and assembly programs into a folder on classroom.cs.unc.edu, and then run the selfchecking and submit scripts as follows:

% cd ~/comp411lab/labX
% /home/montek/comp411/bin/selfchecklabX-struct
% /home/montek/comp411/bin/submitlabX-struct

Due Date: Friday, December 1, 11:59 pm.


Propose Your Own

If you would like to do something different, please propose your own problem. But, be sure that it can be completed within the time-frame of two weeks or less! The work involved should be approximately equal to that of two regular lab assignments. If you are thinking of proposing a project that will likely require more than 25 lines of C code and/or more than 100 lines of MIPS assembly, you are strongly encouraged to propose something simpler!

Proposal: Please propose a topic as soon as possible so the instructor/TAs can okay it. The idea is to give you quick feedback on whether or not what you have in mind is acceptable. It should not be too hard (or you won't finish on time) or too easy (or you may not recieve full credit). Please submit your proposal via Sakai (look under Assignments -> LabX Proposal).

Extra Credit: Exceptionally good work on a topic you propose may earn you extra-credit points. When assigning the final letter grades, if your score (without extra credit) is close to a grade boundary, extra-credit points may help bump up your grade. But, there is no penalty if you choose not to propose your own topic.

Due Date and Demo: There is no submit script if you propose your own problem. However, you must show a working demo of your program (both C and MIPS) to the instructor or one of the TAs on or before class on Monday, December 4, 11:15am. Note: No demo is needed if you choose one of the first four assignments. A demo is required only if you propose your own topic.


12 November 2017, Montek Singh, montek@cs.unc.edu