PE2 (AY18/19)

Problems

Questions:

94KB

pe2-1819-s1.pdf

pdf

Questions

Official Answers:

137KB

pe2-1819-s1-with-comments.pdf

pdf

Official Answers

1. Transpose

This question is a give-away question, the most important part is that m2[j][i] = m1[i][j].

2. Palindrome

A problem that uses Sliding Window technique.

Recursive Solution

bool palidrome(long start, long end, char *str)
{
  if (start >= end)
  {
    return true;
  }
  if (isalpha(str[start]) && isalpha(str[end]))
  {
    return (tolower(str[start]) == tolower(str[end])) && palidrome(start + 1, end - 1, str);
  }
  if (!isalpha(str[start]))
  {
    return palidrome(start + 1, end, str);
  }
  if (!isalpha(str[end]))
  {
    return palidrome(start, end - 1, str);
  }
  return palidrome(start + 1, end - 1, str);
}

Notice that this recursive solution cannot pass two cases since it will cause a stack overflow.

Iterative solution

bool palidrome_loop(long start, long end, char *str)
{
  while (start < end)
  {
    if (isalpha(str[start]) && isalpha(str[end]))
    {
      if (tolower(str[start]) != tolower(str[end]))
      {
        return false;
      }
      start += 1;
      end -= 1;
    }
    else if (!isalpha(str[start]))
    {
      start += 1;
    }
    else if (!isalpha(str[end]))
    {
      end -= 1;
    }
    else
    {
      start += 1;
      end -= 1;
    }
  }
  return true;
}

This iterative can pass all the test cases and it uses the sliding window technique to move the boundaries.

3. Rotate*

An awesome variant question of Binary Search

Instead of using the method in the comments, I used the idea of mapping. Before that, since we already know Binary Search needs the list to be sorted. In this question, the list is sorted but in a another way -- "rotated". For example, in the list below, the actual input position is shown in red, while the sorted position should be in blue.

Example

The way to treat the list as sorted is to use the idea of offset. We still search from the middle, but the actual middle is not the red 3, but the blue 3. Suppose we want to search for number 4 (pos 6), we compare it with the actual middle number, which is 1 in pos 0(not 4 in pos 3). Then we find it is bigger, so we can be sure number 4 is at right of actual middle number 1.

One thing we can notice is that the offset is related to how many bits we have right rotated. The logic is below:

long within_range(long index, long rotate, size_t len)
{
  if ((index + rotate) >= (long)len)
  {
    return index + rotate - (long)len;
  }
  return index + rotate;
}

After knowing this, we can modify our Binary Search slightly to pass this question

long search(long *a, long i, long j, long q, size_t len)
{
  if (i > j)
  {
    return -1;
  }
  long rotate = rotate_pos(a, len);
  long mid = (i + j) / 2;
  long mid_rotated_pos = within_range(mid, rotate, len);
  if (a[mid_rotated_pos] == q)
  {
    return mid_rotated_pos;
  }
  if (a[mid_rotated_pos] > q)
  {
    return search(a, i, mid - 1, q, len);
  }
  return search(a, mid + 1, j, q, len);
}

4. Marnell

A question that combines the is_prime() in 3. Goldbach*, and the way to count all the prime factors of a num in 4. Unique*.

The idea given in the comments are pretty awesome! That is to combine the is_prime and is_semiprime together. This is done by if i is a factor of n and i is a prime, then if n/i is also a prime, then n is a semiprime.

long is_prime_or_semiprime(long n) {
    if (n <= 1) {
        return NEITHER;
    }
    for (long i = 2; i*i <= n; i += 1) {
        if (n % i == 0) {
            if (is_prime_or_semiprime(i) == PRIME && is_prime_or_semiprime(n/i) == PRIME) {
                return SEMIPRIME;
            }
            return NEITHER;
        }
    }
    return PRIME;
}

5. Bracket*

An awesome and hard problem about bracket matching. It is obvious to use stack to solve it. But here recursion is required, making it harder to think.

Instead of using the sliding window technique in 2. Palindrome, we mimic the idea of using stack to solve this problem, that is whether the "bracket" is consumed or not. Thus, the recursive function will return the index of the first unconsumed character.

The first two return blocks both returns the position that cannot be consumed. The Line 10 will return the solution for the subproblem, which is the string begins from end+1. The Line 12 will return the begin position if it cannot be consumed in the current function call.

long consume_valid(char *string, int begin) {
    if (string[begin] == '\0') {
        return begin;
    }
    if (!is_open(string[begin])) {
        return begin;
    }
    long end = consume_valid(string, begin+1);
    if (is_matching_close(string[begin], string[end])) {
        return consume_valid(string, end + 1);
    }
    return begin;
}

The tricky point is that in Line 8, you try to consume open bracket in the current function call.

The call in main() should be

long end = is_valid(str, 0);
if (str[end] == '\0') {
    cs1010_println_string("yes");
} else {
    cs1010_println_string("no");
}

Tips

1. Include the is_prime() and count_factors() into the cheatsheet