Advanced Algorithms Quiz 2: 6 August 2023 (May 2023 term)

For the following sets of timings of dance classes, figure out what is the largest number of classes that you can attend in a conflict-free fashion:

The number of classes is N = 9. The timings of the classes are given by:

1. [1 - 5]
2. [6 - 10]
3. [11- 15]
4. [16 - 20]
5. [2 - 8]
6. [3 - 8]
7. [2 - 7]
8. [9 - 12]
9. [13 - 17]

Consider 4 sets as follows: $W = \{w_1, w_2, w_3\}$, $X = \{x_1, x_2\}$, $Y = \{y_1, y_2, y_3\}$ and $Z = \{z_1, z_2\}$.

Given capacity constraints are as follows:

$c(w_2) = c(y_1) = c(y_3) = 1,$

$c(w_1) = c(w_3) = c(x_2) = c(y_2) = c(z_1) = 2,$

$c(x_1) = c(z_2) = 3$

$c(w_i, x_i) = 1, \text{ for all } w_i \in W \text{ and all } x_i \in X,$

$c(y_i, z_i) = 1, \text{ for all } y_i \in Y \text{ and all } z_i \in Z$

$c(x_1, y_1) = 1, c(x_1, y_2) = 2, c(x_1, y_3) = 1$

$c(x_2, y_1) = 0, c(x_2, y_2) = 2, c(x_2, y_3) = 1.$

Identify the size of a largest collection of 4-tuples from the sets $W, X, Y$ and $Z$ satisfying the given constraints

Let $G$ be a simple, undirected, unweighted graph.

We use $V(G)$ to denote the vertex set of $G$ and $E(G)$ to denote the edge set of $G$.

Recall that if we have an empty graph (i.e, a graph where $V(G) = E(G) = \emptyset$), then by convention it (vacuously) satisfies the properties suggested in the given subquestions

Consider the set system $(U, \mathcal{F})$ defined as follows.

• The universe $U$ is $V(G)$.
• A subset of vertices $S \subseteq V(G)$ belongs to $\mathcal{F}$ if the subgraph induced by $S$ has maximum degree three.

Which of the following properties is/are NOT satisfied by $\mathcal{F}$?