Assignment 3 - OpenMP Knapsack

Introduction

The objective of this PA is to write two OpenMP programs for the knapsack problem using the dynamic programming approach: an unblocked and a blocked version,

Check the Dynamic Programming lecture, in particular the parts on (blocking) the knapsack.

In both cases first write and debug a sequential version before you work on any parallelization.

Work in a step wise fashion for debuggig purposes. Run your codes on a quiet veggie machine.

PA3A: knapSeq and knap
Start from the code skeleton knap.c provided in PA3.tar to create a sequential knapsack solver.
Inputs are in kxx.txt files, where xx represents N, the number of objects.
The file format is described in the knap.c code:
```
   //  first line:  # of objects, knapsack capacity, 
   //  next lines:   weight and profit  of next object (1 object per line)
 
```
The following input file, k50.txt has the following solution k50.res.
You can also use the simpler case, k10.txt to debug your codes: k10.txt contains and knapSeq k10.txt should produce:
```
platte 69 # ty k10.txt
10 25
9 10
2 200
7 100
6 20
4 15
3 190
7 159
8 125 
6 29
4 200  
platte 70 # knapSeq k10.txt 
The number of objects is 10, and the capacity is 25.
The optimal profit is 874 Time taken : 0.000003.
Solution vector is: 
 --> 0 1 0 0 0 1 1 1 0 1 
```
Parallelize the loop that goes through all capacities for one object, and other easy parallizable loops (intiaiizations).
Record times for the part of your code that computes the table, and speedups for 1,2,3,4,5,6,7, 8 threads.
Write down your observations:
- how does the parallel code compare to the sequential?
- for which number of threads does speedup end?
- what is your max speedup?
Submit your sequential and parallel code, your time and speedup statistics, and observations in a README file in PA3A.tar.
PA3B: Blocked knapBSeq and knapB

Note that blocks on a diagonal can be processed in parallel, and that in a diagonal the sum of the row and column indices is constant.

E.g., for a 4 by 4 blocked table we have:

diagonal 0: (0,0)
diagonal 1: (0,1) and (1,0)
diagonal 2: (0,2), (1,1) and (2.0)
diagonal 3: (0,3), (1,2), (2,1) and (3.0)
diagonal 4: (1,3), (2,2) and (3,1)
diagonal 5: (2,3) and (3,2)
diagonal 6: (3,3)

Record times for the part of your code that computes the table, and speedups for 1,2,3,4,5,6,7, 8 threads.

Write down your observations:

is your blocked sequential code faster than your unblocked sequential code?
how does the parallel code compare to the sequential?
for which number of threads does speedup end?
what is your max speedup?

Submit your sequential and parallel blocked code, your time and speedup statistics, and observations in a README file in PA3B.tar.