Final (AY22/23)

Problems

Question paper without answers:

145KB

final-2223-s1-sheet.pdf

pdf

Question without Answers

Question paper with answers:

127KB

final-2223-s1-with-comments.pdf

pdf

Question with Answers

5. Recursion

In this question, every time we need to make two recursive calls. So, we need to think both cases to decide how we can modify to make the recursion finite!

6. Memory Leak

Whenever you call a malloc(), always be careful not to point the pointer to else where. This will cause memory leak!

7. Multi-dimensional Array Decay

See Array Name Decay (Multidimensional Array) for more detail information. But this statement is pretty useful:

Since an array in C consists only of a contiguous region of memory that stores the elements of the array, the address of an array is the same as the address of the first of the array.

With this information, image + 1, first, use the knowledge of Pointer Arithmetic, the pointer image points to an array of long *, so +1 will move it to the second row. So, it has the type as the second row (an array) and its value is the address of the first long in the row.

However, &image[1][0], &image[0][1], &image[1][1] all have the type as a long, which is not an array. For image[0] + 1, it has the , and its value is the second long in the first row! Wrong also.

For the correct answer &image[1], firstly, image[1] is of type long, but add & operator will change it to type "array". So, now it is of type array (second array) and has value of the address of the first element in the second row.

8. Illegal Memory Access

This is a trickly question in the final paper. Illegal Memory Access needs to satisfy two requirements:

1. the memory address is Illegal (NULL and the examples in 9. Illegal Memory Access which appears in Final (AY20/21))
2. you try to the memory address

In this the code below:

list[0] = calloc(ncols * nrows, sizeof(long));
for (size_t i = 1; i < nrows; i += 1)
{
    list[i] = list[i - 1] + ncols;
}

If list[0] is NULL, as long as we don't access its memory address (read/write), we are not doing anything illegal. (See this question)

We are allowed to have pointers pointing to arbitrary region in memory, but as long as we don’t those memory, we are not doing anything illegal.

15. Recursion

The official solution for this problem is awesome!

bool can_sum_to (long a[], size_t i , size_t n, long q)
{
  if (q == a[i])
  {
    return true;
  }
  if (i >= n - 1)
  {
    return false;
  }
  return can_sum_to(a, i + 1, n, q) || can_sum_to(a, i + 1, n , q - a[i])
}

For the recursion part, it utilises the idea that we can narrow our list range by either using the a[i] to try forming our sum or not using the a[i] to form our sum.

For the base case, every time we check whether our "updated" q is equal to the first element or not, if it is, means we can find one such combination that sums to q in the list. Otherwise, if the range of the list is 0 or negative, means that we cannot find such a combination.

The recurrence relation is $T(n)=2T(n-1)+1$. And use the basic knowledge of geometric sequence, we can get $T(n)=O(2^n)$.

16. Call Stack Diagram

The quesition is to draw the stack diagram for the following code:

void qux(long **ptrptr, long *numptr2)
{
  long *numptr1 = numptr2;
  *ptrptr = numptr2;
  *numptr1 = 57;
  // Line X
}

void baz(long **ptrptr, long *numptr)
{
  qux(ptrptr, numptr);
}

int main()
{
  long *ptr;
  long num = 1;

  baz(&ptr, &num);
}

The answer should be:

Stack Diagram with Pointer & Double Pointers

The most important thing to note is inside baz() to call qux(), we are actually passing the address of the num and ptr in the main()! So the pointer should point to these two variables in the main(), instead of pointing to the temp variable in the baz()!

Tips

1. Include the five Array Name Decay (Multidimensional Array) examples in the cheatsheet and include the small observation behind the examples into the cheatsheet also.