CIS330 Name: Spring 2019 Midterm 5/1/2019, 10:00AM to 11:20AM Time Limit: 80 Minutes This exam contains 13 pages (including this cover page and extra sheets) and 9 questions. Total number of points is 100, excluding extra credit. This exam is printed on both sides. You are not allowed use any books, notes, calculators, or electronic devices of any kind. Write your answers carefully and legibly. Partial answers are better than no answers. Feel free to skip around and go back to an earlier question later. You may find it helpful to skim over the entire exam first and start with the easier ones, then move on to the more difficult ones. Good luck! Grade Table (for instructor use only) Question Points Score 1 3 2 11 3 2 4 6 5 10 6 5 7 3 8 10 9 50 Total: 100 CIS330 Midterm – Page 2 of 13 5/1/2019, 10:00AM to 11:20AM 1. (3 points) Permissions Given the following file describe its file permissions. -rw-rw-r– jeec jeec 238 Oct 15 09:09 exam.tex Read and write access to owner. Read and write access to group. Read access to others. 2. (11 points) Write the complete Linux command(s) to do the following: (a) (1 point) Display the manual page for the ls command. man ls (b) (1 point) Create a new empty file named newfile.txt touch newfile.txt (c) (1 point) Remove the file newfile.txt. rm newfile.txt (d) (1 point) Rename the file newfile.txt to oldfile.txt. mv newfile.txt oldfile.txt (e) (3 points) Using all of the commands cat, head, tail, and piping (|), print lines 2 through 8 (including lines 2 and 8) for the file newfile.txt cat newfile.txt | head -8 | tail -7 (f) (2 points) Use grep to search the file myfile.txt for lines that begin with 3 digits, followed by one or more occurrences of the characters x, y, or z. grep “^[0-9][0-9][0-9][xyz]\+” myfile.txt (g) (2 points) Given the tarball exam.tar, how would you extract its files while printing information (i.e., verbose mode) tar -xvf exam.tar 3. (2 points) Assuming your project is being revision controlled using git on a remote server (e.g., Bitbucket), how would you make sure a new file, timer.c, will be visible to other users. Assume these users already have read/write access to your repository. Write the required commands below. git add timer.c git commit -m “added timer.c” git push origin master 4. (6 points) For the following questions, choose the corret answer. (a) (1 point) Given the following C code: #include #include int main(int argc, char **argv) { argc–; for(int i = 0; i < argc; i++) { printf("%s ", argv[i]); CIS330 Midterm - Page 3 of 13 5/1/2019, 10:00AM to 11:20AM } return 0; } Which output will be displayed if executed as follows: ./a.out Doctor Who? A. Doctor Who? B. Doctor C. a.out Doctor D. ./a.out Doctor argc-- makes it print everything but the last token E. ./a.out Doctor Who? F. None of the above CIS330 Midterm - Page 4 of 13 5/1/2019, 10:00AM to 11:20AM (b) (1 point) What would be the output of the following piece of C code? Assume that the rest of the code is valid (i.e., proper headers have been included, variables have already been properly declared, and the code compiles, etc.) i = 3; j = 4; i = (i == j) ? 5: 7; printf("i is now %d\n", i); A. i is now 1 B. i is now 3 C. i is now 4 D. i is now 5 E. i is now 7 ternary expression evalutes to i = 7 F. None of the above. (c) (2 points) Which of the following answers are correct? #include #include #define calcCircleArea(r) 3.14 * r * r int main() { int r1 = 2; int r2 = 3; float area = calcCircleArea(r1 + r2); printf("Area is %f\n", area); return 0; } A. The compiler will throw an error because 3.14 * r * r is not enclosed in parentheses (i.e., ( )) B. We cannot predict what will be printed because calcCircleArea is defined ambiguously. C. We cannot predict what will be printed because we are using integers for r1 and r2 but assigning the result to a float. D. “Area is 78.500000” will be printed. E. “Area is 15.280000” will be printed. #define does text replacement. Thus, float area = 3.14 * r1 + r2 * r1 + r2 = 3.14 * 2 + 3 * 2 + 3 = 15.28 F. None of the above. CIS330 Midterm - Page 5 of 13 5/1/2019, 10:00AM to 11:20AM (d) (1 point) Which of the following are control flow statements in C. Choose all cor- rect answers. A. if-else B. switch C. for loop D. while loop E. do-while loop F. None of the above. (e) (1 point) What is the output of the following piece of code, assuming the rest of the code is valid. int i = 1; printf("%d ", ++i); printf("%d ", i); printf("%d ", i++); A. 2 2 2. ++i increments i first, then prints 2. Prints 2. Then, i is printed first (2), then incremented. B. 1 2 3 C. 2 2 3 D. 1 2 2 E. None of the above. CIS330 Midterm - Page 6 of 13 5/1/2019, 10:00AM to 11:20AM 5. (10 points) Write a function that does the following: • Takes in a single char pointer (i.e., char*) as input. • Has no return value. • Makes a copy of the input string to a new heap memory location. • Flips the string (i.e., Hello → olleH) in-place in this new memory location. • Copy the flipped string back to the original memory location pointed to by the input char pointer. Make sure to include the function name and its input parameters in your code. void myfunc(char *in) { int len = strlen(in); // Don’t forget the null character char *out = (char*) malloc(sizeof(char) * (len + 1)); // You can use strcpy here instead for(int i = 0; i < len + 1; i++) { out[i] = in[i]; } // Flip for(int i = 0; i < len / 2; i++) { // Swap char x = out[len - 1 - i]; out[len - i] = out[i]; out[i] = x; } // You can use strcpy here instead for(int i = 0; i < len + 1; i++) { in[i] = out[i]; } free(out); } 6. (5 points) Given the following Makefile and two C source files – main.c and add.c – write down the exact bash commands that would be executed when you type “make run”. sources = $(wildcard *.c) objects = $(addsuffix .o, $(basename $(sources))) flags = -g -W -Wall target = run $(target) : $(objects) gcc -o $(target) $(objects) CIS330 Midterm - Page 7 of 13 5/1/2019, 10:00AM to 11:20AM %.o : %.c gcc -c $(flags) $< -o [email protected] gcc -c -g -W -Wall add.c -o add.o gcc -c -g -W -Wall main.c -o main.o gcc -o run add.o main.o 7. (3 points) Describe the four stages of compilng a C program. Include a description of the input and output formats for each stage. 1) Preprocessing - Includes header files and expands #defines in the source code to create a larger source code. 2) Compiling - Compiles the preprocessed source code to generate assembly language version of the source code. Still in text format and somewhat ‘‘readable.’’ 3) Assembling - Assembler takes the compiled assembly code and generates a binary file object files that computers can read. 4) LInking - Links all the object files to generate the final executable binary file. CIS330 Midterm - Page 8 of 13 5/1/2019, 10:00AM to 11:20AM 8. (10 points) Consider the following C code that uses dynamically allocated 2D array of integers to store a matrix. Find at least 5 problems that would result in a compile-time problem (warning or error), or runtime problems (crahes or undefined values). Describe each problem briefly and feel free to draw arrows to relevant parts of the code. Do not include code style issues such as variable naming choices or indentation. #include #include void init2DArray(int **arr, int rows, int cols) { int **tmpArr = NULL; for(int i = 0; i < cols; i++) { tmpArr[i] = (int*) malloc( sizeof(int) * cols); } int cnt = 0; for(int i = 0; i < rows; i++) { for(int j = 0; j < cols; j++) { *(*(tmpArr + i) + j) = cnt; ++cnt; } } *arr = tmpArr; } int freeArray(int **arr) { free(arr); } int main(int argc, char **argv) { int **2DArray = NULL; printf("Number of rows? "); scanf("%d", rows); init2DArray(&2DArray, rows, 10); freeArray(2DArray); return 0; } 1) 2DArray is illegal - variables should not begin with a number. 2) & 3) rows is not declared (int rows) and rows should be &rows. Alternatively, you could say rows is not declared (int *rows), and rows should be malloc’d. 4) int **arr should be int ***arr. You are passing (by reference) in a pointer to a int** which is necessary to store the new address generated by malloc to tmpA rr. 5) tmpArr = (int**) malloc(sizeof(int*) * rows) is missing (i.e., tmpArr has no memory allocated to it) 6) i 7) in freeArray, arr is deallocated before the individual rows are deallocated. 8) no return value in int freeArray() CIS330 Midterm - Page 9 of 13 5/1/2019, 10:00AM to 11:20AM Figure 1: a) 2-D (5 point) and b) 3-D (7 point) stencils 9. (50 points) Write a program to calculate the 7-point stencil. How the 7-point stencil works: given a 3-D array, • For each element in position (i,j,k), calculate the average between its neighbors, including itself, as shown in Figure 1b. • If v(i,j,k) is the value of the array at index (i, j, k), your code should calculate a new value x(i,j,k) x(i, j, k) = (v(i, j, k) + v(i− 1, j, k) + v(i + 1, j, k) + v(i, j − 1, k) + v(i, j + 1, k) + v(i, j, k − 1) + v(i, j, k + 1))/7 (1) and store it back in the same position (i, j, k) • For elements on the edge of the array, average only the values that are avail- able. For example, v[0][0][0] only has neighbors at v[1][0][0], v[0][1][0], v[0][0][1]. Therefore, v[0][0][0] = (v[0][0][0] + v[1][0][0] + v[0][1][0] + v[0][0][1])/4 The following code has been provided to start. Do not change the provided code. Your job is to: (a) (10 points) Implement the function init 3d array. Given a pointer to a 3-D array, arr, it should allocate a 3D array of size imax x jmax x kmax. If rnd is set to 0, the array should be initialized to all 0; otherwise, it should be initialized to some random number from 0 to 29. (b) (10 points) Implement the function free 3d array. Given a pointer to a 3-D array of size imax x jmax x kmax, deallocates its memory. (c) (30 points) Implement the function stencil. This function takes in a 3-D array as input, whose size is imax x jmax x kmax, and calculates the 3-D 7 point stencil. When the function finishes executing, the 3-D array, arr, should have the new values calculated from the 7 point stencil. (d) (5 points) EXTRA CREDIT: Modularize (i.e., put it in another function) the operations inside the inner-most loop of the stencil computation. See the function calc average() (e) (5 points) EXTRA CREDIT: Describe how you would 1) change the code to enable OpenMP parallelization (be specific as to where these change should be CIS330 Midterm - Page 10 of 13 5/1/2019, 10:00AM to 11:20AM made), and 2) what command would you use to compile this code with OpenMP. 1a) Add #pragma omp parallel for to the outermost loop in stencil(), since each point can be calculated in parallel. 1b) Include omp.h. 2) Compile with -fopenmp flag. (f) (5 points) EXTRA CREDIT: How you would use valgrind on this code to debug it? Be specific about everything you would need to do, including changes to the code, compile options, and what command you would type to begin valgrind. 1) Compile the code -g flag 2) Use the command “valgrind ” (or a.out) Hints: • When calculating the stencil, an intermediate data structure will be useful, since if you calculate x[1][1][1] and store it in v[1][1][1] before you calculate x[1][2][1] (which will require v[1][1][1]), you will not get the correct answer. You may be able to reuse init 3d array and free 3d array. #include #include void init_3d_array(int**** arr, int imax, int jmax, int kmax, int rnd); void free_3d_array(int*** arr, int imax, int jmax); void stencil(int ***arr, int imax, int jmax, int kmax); int main(int argc, char **argv) { // imax,jmax,kmax contains the dimension sizes of the 3D array int imax, jmax, kmax; if(argc != 4) { printf("Error - not enough inputs\n"); return EXIT_FAILURE; } imax = atoi(argv[1]); jmax = atoi(argv[2]); kmax = atoi(argv[3]); // This is where the 3D array will be stored int ***d3_array = NULL; // if rand = 1, initialize the 3D array with a random value // if rand = 0, initialiez the 3D array with 0 int rnd = 1; init_3d_array(&d3_array, imax, jmax , kmax, rnd); CIS330 Midterm - Page 11 of 13 5/1/2019, 10:00AM to 11:20AM stencil(d3_array, imax, jmax, kmax); free_3d_array(d3_array, imax, jmax); } BEGIN init 3d array() void init_3d_array(int**** arr, int imax, int jmax, int kmax, int rnd) { // create a temporary int*** array and allocate memory for a 3D array // create imax pointers to int** for the first dimension int ***arr_ = (int***) malloc(sizeof(int**) * imax); for(int i = 0; i < imax; i++) { // for each element in arr_ create jmax int* pointers for 2nd dim arr_[i] = (int**) malloc(sizeof(int*) * jmax); for(int j = 0; j < jmax; j++) { // for the last dim allocate memory for kmax integers // now you have (imax * jmax * kmax) integers arr_[i][j] = (int*) malloc(sizeof(int) * kmax); for(int k = 0; k < kmax; k++) { // for each element k, initialize with a rand between 0-29 or 0 if(rnd == 1) { arr_[i][j][k] = rand() % 30; } else { arr_[i][j][k] = 0; } } } } // Store this memory address to arr // arr was passed in as the "address to int***" // by dereferencing it, you are storing the address to int*** in arr *arr = arr_; } END init 3d array() BEGIN free 3d array() void free_3d_array(int*** arr, int imax, int jmax) { for(int i = 0; i < imax; i++) { for(int j = 0; j < jmax; j++) { free(arr[i][j]); } free(arr[i]); } CIS330 Midterm - Page 12 of 13 5/1/2019, 10:00AM to 11:20AM free(arr); } END free 3d array() BEGIN stencil() void calc_average(int*** arr, int*** tmp3darr, int i, int j, int k, int imax, int jmax, int kmax) { int cnt = 1; tmp3darr[i][j][k] = arr[i][j][k]; // arr[i + 1][j][k] if(i + 1 < imax) { tmp3darr[i][j][k] += arr[i + 1][j][k]; cnt++; } // arr[i - 1][j][k] if(i - 1 >= 0) { tmp3darr[i][j][k] += arr[i – 1][j][k]; cnt++; } // arr[i][j + 1][k] if(j + 1 < jmax) { tmp3darr[i][j][k] += arr[i][j + 1][k]; cnt++; } // arr[i][j - 1][k] if(j - 1 >= 0) { tmp3darr[i][j][k] += arr[i][j – 1][k]; cnt++; } // arr[i][j][k + 1] if(k + 1 < kmax) { tmp3darr[i][j][k] += arr[i][j][k + 1]; cnt++; } // arr[i][j][k - 1] if(k - 1 >= 0) { tmp3darr[i][j][k] += arr[i][j][k – 1]; cnt++; } CIS330 Midterm – Page 13 of 13 5/1/2019, 10:00AM to 11:20AM tmp3darr[i][j][k] = tmp3darr[i][j][k] / cnt; } void stencil(int ***arr, int imax, int jmax, int kmax) { // Temporary structure to calculate the stencil. // In-place computation is not possible since it will change the output. int ***tmp3darr = NULL; // Initialize the 3D array init_3d_array(&tmp3darr, imax, jmax, kmax, 0); // Calculate the stencil for each point for(int i = 0; i < imax; i++) { for(int j = 0; j < jmax; j++) { for(int k = 0; k < kmax; k++) { calc_average(arr, tmp3darr, i, j, k, imax, jmax, kmax); } } } // copy tmp3darr to arr for(int i = 0; i < imax; i++) { for(int j = 0; j < jmax; j++) { for(int k = 0; k < kmax; k++) { arr[i][j][k] = tmp3darr[i][j][k]; } } } // free the temporary memory free_3d_array(tmp3darr, imax, jmax); } END stencil() 欢迎咨询51作业君
