CS1010 AY23/24 Sem 1 National University of Singapore Final Assessment PDF

Final Assessment CS1010 AY23/24 Sem 1 NATIONAL UNIVERSITY OF SINGAPORE SCHOOL OF COMPUTING FINAL ASSESSMENT FOR...

Final Assessment CS1010 AY23/24 Sem 1 NATIONAL UNIVERSITY OF SINGAPORE SCHOOL OF COMPUTING FINAL ASSESSMENT FOR Semester 1 AY2023/2024 CS1010 Programming Methodology December 2023 Time Allowed 2 Hours INSTRUCTIONS TO CANDIDATES 1. This assessment paper contains 16 questions and comprises 10 printed pages, including this page. 2. Write or shade your answers in the answer sheet provided. 3. Please write and shade your student number in the corresponding box in the answer sheet. 4. The total marks for this assessment is 80. Answer ALL questions. 5. This is an OPEN BOOK assessment. 6. You can assume that in all the code given: (i) no overflow nor underflow will occur during ex- ecution; (ii) all given inputs are valid and fits within the specified variable type; (iii) compile without syntax errors; and (iv) all the required header files are already included. Final Assessment CS1010 AY23/24 Sem 1 Part I Multiple Choice Questions (36 points) For each of the questions below, shade your answer on the answer sheet. Each question is worth 3 points. If multiple answers are equally appropriate, pick one and shade the chosen answer on the answer sheet. Do NOT shade more than one answer per question. If none of the answers is appropriate, shade X on the answer sheet. 1. (3 points) Consider a boolean function whose return value depends on three boolean variables, x , y , and z. The only three combinations that cause the function to return true are listed in the table below: x y z true true true true false true false true true Which of the following return statement correctly implements the boolean function? A. return x || y || z; B. return x && y && z; C. return (x || y) && z; D. return (x && y) || z; E. return z; Shade X on the answer sheet if none of the choices above is correct. Solution: C. z must be true for the expression to return true. On the other hand, either one of x and y must be true for the expression to return true. The correct logical expression that represents the table is therefore (x || y) && z. Almost all students (302/313) got this question correct. 2. (3 points) Consider the function below: long ash(long m, long n) { long count = 0; while (m < n) { count++; m++; n--; } return count; } Suppose that m < n. Which of the expressions below best describes what the function computes? Page 2 Final Assessment CS1010 AY23/24 Sem 1 A. (n - m) / 2 B. (n - m) / 2 - 1 C. (n - m) / 2 + 1 D. (n - m + 1) / 2 E. (n - m - 1) / 2 Shade X on the answer sheet if none of the choices above is correct. Solution: D. If n - m is odd, the function returns (n - m) / 2 + 1 ; else (n - m) / 2. The expression (n - m + 1) / 2 correctly captures both cases. This is a relatively straightforward question that assesses the students’ ability to trace a loop and the understanding of the / operator. 73% of students got this question correct. Page 3 Final Assessment CS1010 AY23/24 Sem 1 3. (3 points) Consider the function below: void eng(long m, long n) { do { m = do_something(m); n = do_something(n); } while (m != 0 && n > 0); if (m != 0 && n > 1) { m = 1; // Line W } else if (m == 0) { n = 1; // Line X } else if (n log (n/2) + log (n/2) +... + log (n/2) + log (n/2) = n/2 log (n/2) n We have 2 log n2 < log(n!) < n log n. Hence, O(log(n!)) = O(n log n). Page 10 Final Assessment CS1010 AY23/24 Sem 1 11. (3 points) The final marks of the students in CS1010 are floating point numbers represented as double between 0 and 100. The marks were initially sorted in increasing order. Due to regrade requests from students, a small number of students have their marks adjusted and thus, the marks are no longer correctly sorted. The teaching team wants to re-sort the marks again in increasing order. Which of the following algorithms is the most appropriate for re-sorting the final marks after the regrade request? A. Counting sort B. Insertion sort C. Bubble sort D. Selection sort E. Radix sort Shade X on the answer sheet if none of the choices above is correct. Solution: B. This is meant as a give-away question but, surprisingly, only slightly less than half of the students got it correct. Insertion sort is fast when it comes to sorting an almost- sorted list. 12. (3 points) Consider the implementation of the bubble sort and selection sort algorithms in class. Suppose we are given an array of size n that is inversely sorted, how many swaps are needed by each of the sorting algorithms? Bubble sort Selection sort A. O(n2 ) O(n2 ) B. O(n2 ) O(n) C. O(n) O(n2 ) D. O(n) O(n) E. O(1) O(n) Shade X on the answer sheet if none of the choices above is correct. Solution: B. This is another give-away question but only 25% of the students got it right. For bubble sort, the first pass makes n − 1 swaps, the second pass makes n − 2 swaps, etc. To sort an inversely sorted array, O(n2 ) swaps are needed. For selection sort, each pass only makes one swap (to swap the largest element to its position). So O(n) swaps are needed. Page 11 Final Assessment CS1010 AY23/24 Sem 1 Part II Short Questions (44 points) Answer all questions in the space provided on the answer sheet. Be succinct and write neatly. 13. (6 points) Consider the function below, which calculates the number of digits in a positive integer n. long ndigits(long n) { if (n < 10) { return 1; } return 1 + ndigits(n / 10); } Through formulating a recurrence relation, express the running time of the function using the Big-O notation as a function of n. Show your workings. Solution: The recurrence relation is the following: T (n) = T (n/10) + 1 (1 mark) T (1) = 1 (1 mark) Expanding and observing the pattern, we have T (n) = T (n/10k ) + k (2 marks). n When 10k = 1, k = log n (1 mark). So T (n) = T (1) + log n = O(log n) (1 mark). 14. (10 points) Consider the program below. void foo(long a[], long **p) { *p = a; (*p) += 1; // Line N } int main() { long a = {34, 56}; long *ptr; foo(a, &ptr); cs1010_println_long(*ptr); } (a) (8 points) Draw the content of the call stack when the execution reaches Line N using the notations similar to what has been used in CS1010. Label all your stack frames, variables, and values on the call stack. You may use arrows to denote pointers, instead of using the actual memory address. Page 12 Final Assessment CS1010 AY23/24 Sem 1 foo p a main ptr a 34 56 Solution: Marking scheme: 1 mark for the stack frames with correct function names 1 mark for drawing the stack vertically in the correct order 1 mark for a in main 1 mark for a in main 1 mark for a in foo correctly pointing to a 1 mark for p in foo correctly pointing to ptr 2 marks for ptr in main correctly pointing to a (b) (2 points) What would the program print to the standard output? Solution: 56 Page 13 Final Assessment CS1010 AY23/24 Sem 1 15. (22 points) Consider the following function separate , which takes an array of integer a with n+1 ( n > 0) elements as input. void swap(long *a, long i, long j) { long temp = a[i]; a[i] = a[j]; a[j] = temp; } long separate(long *a, long n) { long i = -1; long j = n + 1; long x = a; while (true) { // Line B do { i += 1; } while (a[i] < x); // Line C do { j -= 1; } while (a[j] > x); // Line D if (i < j) { swap(a, i, j); // Line E } else { // Line F return j; } } } Denote a[i..j] to be the set { a[i] , a[i+1] ,... a[j] }. If j < i then the set is empty. We extend the comparison operations < , > , = to set of elements. For example, we write a[i..j] < x if every element in the set a[i..j] is less than x. We write a[i..j]