# PE2 (AY18/19)

## Problems

Questions:

{% file src="/files/K7PxLqoNUJO9rzr1xrMC" %}
Questions
{% endfile %}

Official Answers:

{% file src="/files/M7IRZPc1oQntJYHkxne8" %}
Official Answers
{% endfile %}

### 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 [PE1 Review](/cs1010-notes/past-year-exam/pe1-review.md#sliding-window) technique.

#### Recursive Solution

```c
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);
}
```

{% hint style="info" %}
Notice that this recursive solution cannot pass two cases since it will cause a **stack overflow.**
{% endhint %}

#### Iterative solution

```c
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;
}
```

{% hint style="info" %}
This iterative can pass all the test cases and it uses the sliding window technique to move the boundaries.
{% endhint %}

### 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**.

<figure><picture><source srcset="/files/UhICORTtX8keKykX5Xzp" media="(prefers-color-scheme: dark)"><img src="/files/xdzaYJY5NDQaPMmTp3kv" alt=""></picture><figcaption><p>Example</p></figcaption></figure>

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:

{% code lineNumbers="true" %}

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

{% endcode %}

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

{% code lineNumbers="true" %}

```c
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);
}
```

{% endcode %}

### 4. Marnell

> A question that combines the `is_prime()` in [/pages/SFzPqZbjJTII1WqqTeKW#id-3.-goldbach](https://wenbo-notes.gitbook.io/cs1010-notes/past-year-exam/pe2-review/pages/SFzPqZbjJTII1WqqTeKW#id-3.-goldbach "mention"), and the way to count all the prime factors of a num in [/pages/oHoyQF5Y7ZvqfpGfOMNu#id-4.-unique](https://wenbo-notes.gitbook.io/cs1010-notes/past-year-exam/pe2-review/pages/oHoyQF5Y7ZvqfpGfOMNu#id-4.-unique "mention").

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.

{% code lineNumbers="true" %}

```c
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;
}
```

{% endcode %}

### 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 [#id-2.-palindrome](#id-2.-palindrome "mention"), 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.

<pre class="language-c" data-line-numbers><code class="lang-c">long consume_valid(char *string, int begin) {
    if (string[begin] == '\0') {
        return begin;
    }
    if (!is_open(string[begin])) {
        return begin;
    }
<strong>    long end = consume_valid(string, begin+1);
</strong>    if (is_matching_close(string[begin], string[end])) {
        return consume_valid(string, end + 1);
    }
    return begin;
}
</code></pre>

{% hint style="info" %}
The tricky point is that in Line 8, you try to consume open bracket in the current function call.
{% endhint %}

The call in `main()` should be

{% code lineNumbers="true" %}

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

{% endcode %}

## Tips

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wenbo-notes.gitbook.io/cs1010-notes/past-year-exam/pe2-review/pe2-ay18-19.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.