Description
Names of Files to Submit: matmult.s, knapsack.s, combs.s ReadMe.txt
1. (Time: 3.5 hours. Lines of Code 257) Write a program called matmult.s that implements matrix
multiplication in assembly. If you don’t know how to do matrix multiplication your can find a
tutorial here.
1. This program should be callable from C and have the following signature:
1. int** matMult(int **a, int num_rows_a, int num_cols_a,
int** b, int num_rows_b, int num_cols_b);
2. This function should multiply matrices a and b together and return the result
3. You must allocate space for this new matrix by calling malloc
2. You have been given a C file called main.c that accepts as command line arguments the
names of two files that contain the matrices to be multiplied. main.c will read in these
matrices, call your function, and then display the result. After it has displayed the result it
will then free the space that has been malloced.
1. Your function must be callable by this file
3. You have also been given a makefile that should compile your program. Your program
MUST be able to be compiled by this makefile. For those of you running 64 bit versions of
Linux you may need to install the 32 bit binaries. I was able to do this on my machine by
installing multilib for gcc. To do this I clicked on the Ubuntu Software App and then
searched for multilib. I selected the one for gcc, installed it, and everything was good to go.
If that doesn’t work for you, you might find this this post helpful. If neither solution works
for you please Google and see what you can find. If you find a solution that works for you
please post it to Piazza.
Example:
cat mata/0-test.txt
3
3
470 -192 -539
235 -814 -538
-503 -418 541
cat matb/0-test.txt
3
3
313 531 802
26 860 -767
543 870 822
./matmult.out mata/0-test.txt matb/0-test.txt
-150559 -384480 81146
-239743 -1043315 370572
125456 -155903 361902
2. (Time 1.5 hours) Write a program called knapsack.s that solves the 0-1 knapsack problem
recursively. In the knapsack problem you have a knapsack that can hold W weight. You also
have a collection of items that each have their own weight wi
and value vi
. The goal is
find the set of items that maximizes the amount of value in the knapsack but whose weight does
not exceed W.
1. This program should be callable from C and have the following signature
1. unsigned int knapsack(int* weights, unsigned int* values,
unsigned int num_items, int capacity, unsigned int
cur_value)
2. This function should calculate and return the maximum value knapsack
3. This function must be implemented recursively
4. Pay very careful attention to the types in this function as it will affect which machine
instructions you should use. Hint: it will affect the jump instructions you use
5. You have been provided with a C file called knapsack.c that implements this function
and should give you a good starting point
1. If you want an extra challenge try solving the problem without looking at knapsack.c
as this problem boils down to just finding the optimal combination of items
6. You will find the leal instruction very helpful for this problem
2. You have also been given a file called main.c that will take as a command line argument the
name of a file containing a knapsack problem.
1. Please see the comments in main.c to see how these files are structured
2. Your function must be callable from this file
3. You have also been given a makefile that will compile the assignment for you as well as
create a version of the executable using only the given C files.
1. Your program must be able to be complied by this makefile
4. Example:
1. cat Tests/0-test.txt
100
4
43 43
3 38
5 17
18 25
./knapsack.out Tests/0-test.txt
123
3. (Time 1.5 Hours) Write a program called combs.s that generates all the possible combinations
of a set of items of a given size.
1. Your program should be callable from C and have the following signature
1. int** get_combs(int* items, int k, int len)
2. This function should generate all possible combinations of items taken k at a time and return
a 2-D array where each row contains one combination
1. The combinations should be added to the 2-D array in their natural order
2. This 2-D array should be dynamically allocated
3. As a hint you will probably need to develop a helper function that actually computes the
combinations
3. You have been given a file called main.c that will get the inputs and call your function
1. Your function must be callable from this file
2. You will also find some helpful functions in main.c that you can call from your program
4. You have also been given a makefile to compile your program.
1. Your program must be compilable by this makefile.
4. Examples
1. How many items do you have: 5
Enter your items: 1 2 3 4 5
Enter k: 3
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
2. How many items do you have: 5
Enter your items: 1 2 3 4 5
Enter k: 4
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5
