> For the complete documentation index, see [llms.txt](https://wenbo-notes.gitbook.io/cs1010-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wenbo-notes.gitbook.io/cs1010-notes/past-year-exam/pe2-review/pe2-ay22-23.md).

# PE2 (AY22/23)

## Problems

Questions:

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

Official Answers:

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

### 1. Search

This is just a give-away question. Follow the instructions strictly will let you pass!

### 2. Missing

This can also be regarded as a give-away question. It just uses **counting sort!**

### **3. Group\***

> This question is a variant of [/pages/zk7HQNIW4AKGnZ3gqjIx#id-5.-stone](https://wenbo-notes.gitbook.io/cs1010-notes/past-year-exam/pe2-review/pages/zk7HQNIW4AKGnZ3gqjIx#id-5.-stone "mention"), but the given solution provides a genius way to print out the result using array

The key idea to solve this question is to draw a "tree", more details are discussed in [Lab 09 - Backtracking](/cs1010-notes/lec-tut-lab-exes/lab/lab-09-backtracking.md).

But let's see how genius the answer is:

{% code lineNumbers="true" %}

```c
void group(size_t current, size_t num_groups, size_t students[], size_t n)
{
  if (current == n)
  {
    print(students, n);
    return;
  }
  // put current student in one of the exisitng groups
  for (size_t i = 1; i <= num_groups; i += 1)
  {
    students[current] = i;
    group(current + 1, num_groups, students, n);
  }
  // or start new group
  students[current] = num_groups + 1;
  group(current + 1, num_groups + 1, students, n);
}
```

{% endcode %}

By overwriting the value of `students[current]`, we are actually doing our "back-tracking"! And once we have reached the end element, we print out the whole array. And our main should look like below:

{% code lineNumbers="true" %}

```c
int main()
{
  size_t n = cs1010_read_size_t();
  size_t *students = calloc(n, sizeof(size_t));
  if (students == NULL)
  {
    return 1;
  }
  // start with num_groups 0
  group(0, 0, students, n);
  free(students);
}
```

{% endcode %}

### 4. Cluster\*

> This question seems to be a variant of [PE1 Review](/cs1010-notes/past-year-exam/pe1-review.md#ex5-q6-social), but actually it is a problem that tests your recursive thinking.

The idea of this problem you iterate through each pair in the network, if they are in contact, remove all their "cluster" contact by iterating through from 0 to n recursively.

```c
#define CONTACT '1'
#define NO_CONTACT '0'

bool is_contact(char **network, size_t i, size_t j)
{
  if (j < i)
  {
    return network[i][j] == CONTACT;
  }
  return network[j][i] == CONTACT;
}

void remove_contact(char **network, size_t i, size_t j)
{
  if (j < i)
  {
    network[i][j] = NO_CONTACT;
  }
  else
  {
    network[j][i] = NO_CONTACT;
  }
}

void remove_cluster(char **network, size_t n, size_t i)
{
  for (size_t k = 0; k < n; k += 1)
  {
    if (is_contact(network, i, k))
    {
      remove_contact(network, i, k);
      remove_cluster(network, n, k);
    }
  }
}

long count_cluster(char **network, size_t n)
{
  long count = 0;
  for (size_t i = 0; i < n; i += 1)
  {
    for (size_t j = 0; j <= i; j += 1)
    {
      if (is_contact(network, i, j))
      {
        count += 1;
        remove_contact(network, i, j);
        remove_cluster(network, n, i);
        remove_cluster(network, n, j);
      }
    }
  }
  return count;
}
```

## Tips

1. Refer back to [Lab 09 - Backtracking](/cs1010-notes/lec-tut-lab-exes/lab/lab-09-backtracking.md) when doing the backtracking problems! Usually, an easier way to help you understand is to **draw a "tree"**.