Assignment 8
posted: 23.07.2021 due: midnight 29.07.2021
You can work in groups of up to three people. One group member should submit a copy of the solu-
tions on Brightspace, with all members’ names and banner numbers on it; the other group members
should submit text files with all members’ names and banner numbers (otherwise Brightspace won’t
let us assign them marks!). You may consult with other people but each group should understand
the solutions: after discussions with people outside the groups, discard any notes and do something
unrelated for an hour before writing up your solutions; it’s a problem if no one in a group can ex-
plain one of their answers. For programming questions you should submit your code, which should
compile and run correctly to receive full marks.
1. Consider the map from Assignment 1, shown below. Suppose you and lots of your friends
have decided to celebrate the end (?) of the pandemic with trips from Dal to Eastern Europe.
To maintain the feeling that the world is big and wide, you don’t want to travel in big groups,
nor keep running into each other while you’re travelling.
You’ve decided to stay spread out with the following rule: on any particular day, if region
A is labelled with the number x and region B is labelled with the number y, then at most
min(x, y) people can travel from A to B, and at most min(x, y) can travel from B to A. (You
can assume movements are synchronous.)
The first few days may be a little chaotic, but then things should stabilize for a while, with
the same number of people leaving each region as entering, until the last people are leaving
Dal and eventually making their way to Eastern Europe. During this intermediate period of
stability, how many people are leaving Dal each day (or, equivalently, how many are arriving
in Eastern Europe)?
(Hint: can you find a matching cut?)
2. Suppose you’re organizing a dinner at an event with n students from k universities and trying
to choose a seating plan. Eight people can sit at each table and you don’t want more than
1
three people from the same university sitting at the same table. How can you efficiently find
the minimum number of tables you’ll need? The input is the number of people from each
university, n1, . . . , nk with n1 + · · · + nk = n, and the output is the number of tables.
(Hint: to test if t tables are enough, create a graph Gt with a source, a sink, a vertex for each
university, and a vertex for each of t tables.)
3. We saw in the Lecture 19 that if we assume there’s a C routine P that, given any string S,
returns the length in characters of the shortest C program that outputs S and then stops,
then we reach a contradiction.
Specifically, if the code for P looks like
int P (char *S) {
…SOME CODE GOES HERE…
}
(with the code to compute P replacing …SOME CODE GOES HERE…), then we can write a
program Q that has P as a subroutine and loops through all possible strings in increasing
order by length until it finds one that P says requires a program much longer than Q, at
which point Q stops and outputs that string. (P must eventually say some string requires a
program much longer than Q, by counting arguments.) An example of such a program Q is
shown below.
#include
#include
#include
typedef struct node {
char *string;
struct node *next;
} node;
char *stringP = “int P (char *S) {\n …SOME CODE GOES HERE…\n}”;
int lenP = strlen(stringP);
int P (char *S) {
…SOME CODE GOES HERE…
}
int main() {
node *head = (node *) malloc(sizeof(node));
node *tail = head;
tail -> string = (char *) malloc(1);
sprintf(tail -> string, “”);
tail -> next = NULL;
2
while (1) {
if (P(head -> string) > 2 * lenP + 1000000) {
// Notice P appears twice in this program:
// once as a string and once as a subroutine.
// The number 1000000 only has to be more than
// the length of the rest of the program.
printf(“%s”, head -> string);
return(0);
} else {
for (int c = 0; c < 256; c++) { tail -> next = (node *) malloc(sizeof(node));
tail = tail -> next;
tail -> string = (char *) malloc(strlen(head -> string) + 2);
sprintf(tail -> string, “%s%c”, head -> string, (char) c);
tail -> next = NULL;
}
head = head -> next;
}
}
}
Adapt that argument to show it’s not possible even to approximate within a factor of 10 the
length of the shortest C program that output S and then stops. How does the code for Q
above change?
3
Assignment 8