Write a program called knapsack that solves knapsack problem

Reference no: EM13973021

Names of Files to Submit: matmult.s, knapsack.s, combs.s ReadMe.txt

• If you are working in a group ALL members must submit the assignment

• All programs should compile with no warnings when compiled with the -Wall option

• All prompts for input and all output must match my prompts/output. We use a program to grade your work and tiny differences can cause your work to be marked as a 0.

? The best way to avoid being deducted points is to copy the prompt/unchanging portion of the outputs into your code. Make sure to get the spaces as well.

• You must also submit a file called ReadMe.txt. Include the names of all partners and any trouble you had on the assignment

• An example ReadMe.txt has been included with this assignment

• The input in the examples has been underlined to help you figure out what is input and what is output

• Submit your work on Smartsite by uploading each file separately. Do not upload any folders or compressed files such as .rar, .tar, .targz, .zip etc.

• If you have any questions please post them to Piazza

• RESTRICTIONS:

? For all programs in this homework you

? May not have a data section. If you need extra space you must use the stack.

? Not call any C functions that you write. You may make use of any of the library functions.

1. 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.

2. 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

3. 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.

Attachment:- Attachments.rar

Reference no: EM13973021

Questions Cloud

Can equilibrium be established when price equal 3 : Discuss a change in demand resulted in a change in the market price. Provide an example of how a change in supply resulted in a change in the market price. How does the price mechanism work to keep markets in equilibrium?

Difference between mechanical and substantive editing : What's the main difference between mechanical and substantive editing? When an editor is obliged by his or her place of employment to apply certain preset conventions to the text and layout of a document, the editor is said to be working according ..

What is the income elasticity given the information : Assume that the current market wage is $40 and the price of the related product (Po) is$10 per unit. Solve for the equilibrium price and quantity.

Create an implementation class. : Your code must compile using the jGrasp IDE. If your code does not compile using jGrasp (for any reason), a grade of 0 will be earned. No exceptions!

Write a program called knapsack that solves knapsack problem : 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.

Provide a detailed overview of the hbm : HBM Overview - Provide a detailed overview of the HBM. Make sure to briefly address the six constructs of this model

How does globalization increase the company business risk : For instance, how does the globalization increase the company's business risk (in terms of demand or supply? Or cost?)? What are strategies that the company can adopt to protect its interests? Provide tables or graphs to illustrate your point.

What are the factors that lead to shifts in supply : What are the market inefficiencies the price controls measures such as price ceilings and price floors create? Why do price ceilings and price floors lead to productive and allocative (marketing) inefficiency?

Develop everything at the nurses and doctors fingertips : The emergency room is a place where there needs to be more room that everything is easily accessible in case of emergency. The emergency room is a place that needs to develop everything at the nurses and doctors fingertips

User Account

All Pages