1 ECE 190 Midterm Exam 3 Spring 2011 Practice Exam Notes: This exam will consist entirely of five programming problems. Each problem will be graded separately. We will provide skeleton codes for each problem. Problem 1 (5 points): Warm-up. In this assignment, you are asked to implement a function to compute the dot product between two n-dimensional vectors. The function accepts two vectors, vec1 and vec2, and number of dimensions, num_dims, and returns the dot product: float dot_product(float vec1[], float vec2[], int num_dims); Example run: float vec1[] = { 1, 2, 3, 4, 5 }; float vec2[] = { 5, 4, 3, 2, 1 }; float dp = dot_product(vec1, vec2, 5); After this code executes, dp should be set to 35.2 Problem 2 (20 points): C to LC-3 assembly conversion. In this assignment, you are asked to rewrite a function for computing factorial written in C into LC-3 assembly language. int factorial(int n) { int fn; if (n > 1) fn = n * factorial(n-1); else fn = 1; return fn; } The function call should be implemented using the run-time stack. Assume caller’s save R0-R3. (in other words, you do not need to save/restore them, the calling function with do this for you.) As a reminder, the factorial function's activation record is provided below: Fn caller’s frame pointer caller’s return address return value n To get you started, we provide a skeleton LC-3 assembly code that should give you some structure and hints to what we expect you to write: FACTORIAL: ; push callee’s bookkeeping info onto the run-time stack ; allocate space in the run-time stack for return value __________________ ; one or more LC-3 instructions ; store caller’s return address and frame pointer __________________ ; one or more LC-3 instructions ; allocate memory for local variable fn __________________ ; one or more LC-3 instructions ; if (n>1) LDR R1, R5, #4 ADD R2, R1, #-1 BRnz ELSE ; compute fn = n * factorial(n-1) ; caller-built stack for factorial(n-1) function call ; push n-1 onto run-time stack __________________ ; one or more LC-3 instructions3 ; call factorial subroutine JSR FACTORIAL ; pop return value from run-time stack (to R0) __________________ ; one or more LC-3 instructions ; pop function argument from the run-time stack __________________ ; one or more LC-3 instructions ; multiply n by the return value (already in R0) LDR R1, R5, #4 MUL R0, R0, R1 ; R0 <- n * factorial(n-1) ; LC-3 ISA does not have MUL instruction, but let’s pretend it does ; store result in memory for fn __________________ ; one or more LC-3 instructions ; done with this branch BRnzp RETURN ELSE: ; store value of 1 in memory for fn __________________ ; one or more LC-3 instructions ; tear down the run-time stack and return RETURN: ; write return value to the return entry __________________ ; one or more LC-3 instructions ; pop local variable(s) from the run-time stack __________________ ; one or more LC-3 instructions ; restore caller’s frame pointer and return address __________________ ; one or more LC-3 instructions ; return control to the caller function RET4 Problem 3 (10 points): Debugging. In this assignment, you are asked to find and fix errors and bugs in the code below: #include <stdio.h> void min_max_average(int list[], int n, int *min, int *max, int *mean); int main() { int list[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int min, max, mean; min_max_average(list, 10, &min, &max, &mean); printf("%d %d %d\n", min, max, mean); return 0; } void min_mav_average(int list[], int n, int *min, int *max, int mean) { *min = list[0]; for (i = 0; i <= n; i++) { *min = (list[i] < *min) ? *min = list[i] : *min; *max = (list[i] < *max) ? *max = list[i] : *max; *mean += list[i]; } *mean /= n; } Hint: all the errors/bugs are in the min_max_average function.5 Problem 4 (15 points): File I/O. In this assignment, you are asked to implement a function to read an image from disk stored in a plain PPM image format and to implement a function to store the image back to disk in the same format. Each plain PPM image file consists of the following: - A "magic number" for identifying the file type, followed by a newline. A ppm image's magic number in this case is the two characters "P3". - A width, formatted as ASCII characters in decimal, followed by a white space followed by a height, again in ASCII decimal, followed by a new line character. - The maximum color value (Maxval), again in ASCII decimal. Must be less than 65536 and more than zero. A new line character follows. - A raster of Height rows, in order from top to bottom. Each row consists of Width pixels, in order from left to right. Each pixel is a triplet of red, green, and blue samples, in that order. Each sample is formatted as ASCII characters in decimal. Example PPM file (test.ppm): P3 4 4 15 0 0 0 0 0 0 0 0 0 9 0 9 0 0 0 0 9 7 0 0 0 0 0 0 0 0 0 0 0 0 0 9 7 0 0 0 9 0 9 0 0 0 0 0 0 0 0 0 The image load/save function prototypes are: int load_ppm(char *name, int *height, int *width, *maxval, int r[], int g[], int b[]); int save_ppm(char *name, int height, int width, maxval, int r[], int g[], int b[]); where name is the file name, height and width are image size, maxval is the maximum color value, and arrays r, g, and b are used to store red, green, and blue color channels. The functions should return 1 if success, otherwise they should return 0; Example run int R[100], G[100], B[100]; int h, w, m; if (load_ppm(“test.ppm”, &h, &w, &m, R, G, B)) save_ppm(“test1.ppm”, h, w, m, R, G, B); After this code is executed, there should be a new file, test1.ppm, created on disk with the exact data as in the original test.ppm file. The functions will be tested separately.6 Problem 5 (20 points): Problem solving. In this assignment, you will implement Gaussian elimination algorithm for solving systems of linear equations. The algorithm consists of two parts: 1) forward elimination step reduces a given system to upper triangular form, and 2) back substitution step to find the actual solution of the system of equations. Your will be required to write two functions, each implementing one step of the algorithm. Formal problem statement Find solution of a system of n equations with n unknowns { In the matrix form, this equation