PE2 (AY20/21)

Problems

Questions:

94KB

pe2-2021-s1.pdf

PDF

Open

Questions

Official Answers:

158KB

pe2-2021-s1-with-comments.pdf

PDF

Open

Official Answers

1. Tic Tac Toe

An easy probelm, just break this problem into several small problems and solve it.

2. Sun

The whole idea is to find the max num (index) that provides the biggest "triangle" number smaller than the input n. And then we start from that triangle number to find its corresponding prime partner. (Cuz the probelms says triangle num should be in decreasing order)

for (max = 0; tri <= n; max += 1)
{
  tri = max * (max + 1) / 2;
}
for (long x = max - 2; x >= 0; x -= 1)
{
  tri = x * (x + 1) / 2;
  if (is_prime(n - tri))
  {
    cs1010_print_long(n - tri);
    cs1010_print_string(" ");
    cs1010_println_long(tri);
  }
}

But the overall run time of $O(N)$ is a bit tricky. Here our first loop is actually $O(\sqrt{N})$ and our second loop is actually one $O(\sqrt{N})$ loop inside another $O(\sqrt{N})$ loop, so the overal timing is $O(N)+O(\sqrt{N})$, which is $O(N)$

3. Replace*

The official answer

The idea of replacing the redundant chars in the target string with white spaces and then ignore them in the final print is awesome.

Substitute.c

void substitute(char *word, size_t i, size_t target_len, char *replace_with) {
    size_t replace_len = strlen(replace_with);
    size_t j = 0;
    while (j < replace_len) {
        word[i + j] = replace_with[j];
        j += 1;
    }
    while (j < target_len) {
        word[i + j] = ' ';
        j += 1;
    }
}

There is an awesome idea here! The use of i to indicate the start position in the source string we want to search for deals with the moving problem of the string successfully.

Here it is assumed that the length of the target string is longer than or equal to the length of the replace string.

Compact.c

void compact(char *word)
{
    size_t src = 0;
    size_t dst = 0;
    size_t word_len = strlen(word);
    while (src < word_len) {
        if (word[src] != ' ') {
            word[dst] = word[src];
            dst += 1;
        }
        src += 1;
    }
    word[dst] = 0;
}

Based on the same assumption above, our dst is always smaller than or equal to src

Replace.c

void replace(char *word, char *search_for, char *replace_with)
{
    size_t word_len = strlen(word);
    size_t search_len = strlen(search_for);
    for (size_t i = 0; i < word_len; i += 1) {
        if (is_match(word, i, search_for)) {
            substitute(word, i, search_len, replace_with);
            i += search_len ­- 1;
        }
    }
    compact(word);
}

My Recursive solution

Refer to the idea of doing recursion on strings from past year final paper (AY21/22 Q19) I implement a recursive solution as follows:

void search_and_replace(char *tar, char *rep, long tar_len, long rep_len, char *res, char *source)
{
  long len_res = 0;
  long len_src = 0;
  if (*source == '\0')
  {
    return;
  }
  long start_pos = find_pos(tar, source);
  if (start_pos != -1)
  {
    for (long i = 0; i < start_pos; i += 1)
    {
      res[i] = source[i];
    }
    len_res += start_pos; 
    for(long i = 0; i < rep_len; i += 1)
    {
      res[i+len_res] = rep[i];
    }
    len_res += rep_len;
    len_src = start_pos + tar_len;
  }
  else
  {
    char *temp = source;
    while (*temp != '\0')
    {
      res[len_src] = source[len_src];
      len_src += 1;
      temp += 1;
    }
    len_res = len_src;
   }
  search_and_replace(tar, rep, tar_len, rep_len, res+len_res, source+len_src);
}

Note that this function will need some tedious memory management in the main() function, where we need to read several target strings and replacement strings.

4. Soil

Prof summarises this problem to be a pattern recognition problem. The soul of this problem is the narrow your "searching area". That is, we can start from top-right (a[0][n-1])

1. If a[0][n-1] is bigger than q, that means q cannot exist in the last column, so we narrow our search area by excluding the last column.

2. If a[0][n-1] is smaller than q, that means q cannot exist in the first row, so we narrow our search area by excluding the first row.

5. Substring*

This is actually a variant of 3. Group* from PE2 (AY22/23)

This question also utilizes the awesome use of "move string" when pass it in recursion. The use of each parameter in the fucntion are documented in the code below:

/**
 * @param src  The source string
 * @param len  The length of source string
 * @param k    The length of the remaining characters
 * @param curr The position / Number of characters we have appended
 * @param sub  The substring
 */
void print_sub(char *src, size_t len, size_t k, size_t curr, char *sub)
{
  // No more remaining characters
  if (k == 0)
  {
    sub[curr] = '\0';
    cs1010_println_string(sub);
    return;
  }
  // Iterate through all the possible characters we can choose
  for (size_t i = 0; i <= len - k; i += 1)
  {
    sub[curr] = src[i];
    print_sub(src + i + 1, len - i - 1, k - 1, curr + 1, sub);
  }
}

So, for this question, during every iteration, the possible characters we can choose are from 0 to len-k in the current src string! And once we have added a character to our sub string, we move our src string to the remaining string behind that character.

Whne you allocate the memory for char *sub, remember to add 1 to k since a string must end with \0. That is also why you need to add \0 in the base case in the code above.

Tips

1. Somtimes changing the loop condition will change the obvious time complexity, pay attention to the "hidden" time complexity and sometimes this kind of change can be utilised to make your code more effificient.

2. When you want to improve the complexity of searching/sorting problems, try thinking about how to narrow your "searching area". This will be very useful!

3. Include my solution and prof's solution to 5. Substring* in PE2 Review.