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


---

# 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-ay22-23.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.