Question 1 - Tracing Programs

We are going to trace the following program, i.e. simulate in your head how it would execute on a computer. To help you, a trace table is provided for you to fill. Unlike exam E1, our focus here is not only on keeping track of the values of each variables but also the activation records pushed on the program's execution stack.

Program to Trace

1 #include
2 #include
3
4 int mystery(int v1, int v2){
5 if( (v1 < 1) || (v2 < 1) ) return 0;
6 if( v1 < v2 ) return mystery(v1, v2-1)+1;
7 if( v2 < v1 ) return mystery(v1-1, v2)+1;
8 return mystery(v1-1, v2-1);
9 }
10
11 int main(){
12 int tmp = 0;
13 tmp = mystery(3,2);
14 printf("result is %d\n", tmp);
15 return EXIT_SUCCESS;
16 }

Tests Table to Fill

Feel free to add / remove rows if necessary

Question 2 - Testing Programs

You are going to write tests for the following program.

Its requirements are to
- Take an integer array data of SIZE elements
- Take a positive, non-null, integer value n
- If the value is null or negative, the program should not alter the array
- If it is positive, each element in the array should be shifted right by n positions
- If an element is pushed past the end of the array, we keep pushing it as if the end of the array connected to its start. Our array is a kind of "ring".

Your objective is to write tests which will guarantee
- The program conforms to the requirements; the program below might or might not, your tests need to be able to determine this
- All possible execution paths have been tested
- Your program does not feature any of the novice errors discussed in the textbook / videos / ...

Program to Test
1 // all arrays in this program will have same size
2 #define SIZE 3
3
4 void rotate(int data[], int n){
5 int index = 0;
6 int tmp[SIZE];
7
8 // copying data into tmp array
9 for(index = 0 ; index < SIZE ; index++){
10 tmp[index] = data[index];
11 }
12
13 for(index = 0 ; index < SIZE ; index++){
14 next = (index + n) % SIZE;
15 data[next] = tmp[index];
16 }
17 }

Tests Table to Fill

Feel free to add / remove rows if necessary

Question 3 - Refactoring Programs

Refactor the following code; i.e. improve its quality without modifying its behavior;
- Use meaningful names for variables, parameters & functions
- Provide proper documentation as required in the PAs
- Provide proper indentation & programming style similar to the examples from the textbook, videos & PAs
- Remove useless code
- Simplify program
- Improve performance

You will provide your version in the "Your Modified Version" subsection which is already pre-filled with the original. Then, for each improvement you applied, use the table in the "Summary" subsection to explain what you did & why you did it.
Program to Refactor

1 int mystery(int v1, int v2){
2 if( (v1 < 1) || (v2 < 1) ) return 0;
3 if( v1 < v2 ) return mystery(v1, v2-1)+1;
4 if( v2 < v1 ) return mystery(v1-1, v2)+1;
5 return mystery(v1-1, v2-1);
6 }

What did you modify

Your Improved Version
1 int mystery(int v1, int v2){
2 if( (v1 < 1) || (v2 < 1) ) return 0;
3 if( v1 < v2 ) return mystery(v1, v2-1)+1;
4 if( v2 < v1 ) return mystery(v1-1, v2)+1;
5 return mystery(v1-1, v2-1);
6 }
Summary of Improvements
Feel free to add rows to, or remove rows from, this table as needed;

Question 4 - Debugging Programs

The following function has all sorts of problems in implementing the requirements. We need you to list the errors you found in the table below along with how you would fix them. You will then provide the fixed version of the function. Here is the documentation for the interleave function. You will use this information as requirements;

- Role

Modifies the array result so it contains alternated elements from d1 & d2

Example - if d1 = {1,3,5} & d2 = {2,4,6} then result = {1,2,3,4,5,6}

- Parameters

d1 & d2 arrays of SIZE integers

result array of SIZE*2 integers

No need to pass the size of the arrays, we expect SIZE to have been globally #define'd

- Return Values

n/a

Program to Debug

1 // arrays passed as d1 / d2 have the following size
2 // array passed as result will always be 2*SIZE
3 #define SIZE 3
4
5 void interleave(int d1[], int d2[], int result[]){
6 int n=0;
7 for( ; n <= SIZE ; n++){
8 result[n] = d1[n];
9 result[n+1] = d2[n];
10 }
11 }

Bugs Table

Identify each bug you find & provide the lines # where it happens. In addition, explain what the problem was, then how you fixed it. If the same bug appears at different line, just enter it one time in the table but specify all the lines where it happens.

Your Fixed Version

Apply all the fixes you listed in the table to the code below to make it your fixed version. Please note that if a bug is fixed below but not in the table, or the other way around, you won't get credit for it. You need to have both the bug and its explanations in the table and have it fixed below.

1 // arrays passed as d1 / d2 have the following size
2 #define SIZE 3
3
4 void interleave(int d1[], int d2[], int result[]){
5 int n=0;
6 for( ; n <= SIZE ; n++){
7 result[n] = d1[n];
8 result[n+1] = d2[n];
9 }
10 }