PE2 (AY22/23)

Problems

Questions:

136KB

pe2-2223-s1.pdf

PDF

Open

Questions

Official Answers:

118KB

pe2-2223-s1-with-comments.pdf

PDF

Open

Official Answers

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 5. Stone, 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.

But let's see how genius the answer is:

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

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:

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

4. Cluster*

This question seems to be a variant of 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.

#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 when doing the backtracking problems! Usually, an easier way to help you understand is to draw a "tree".