Opening the paper…
Advanced Algorithms, End Term
Recall the Dance Class problem:
Problem Definition
Dance Classes
Input: A collection of intervals given by their left and right endpoints , where for all .
Question: What is the size of the largest collection of mutually pairwise non-overlapping intervals?
On which of the following instances will this algorithm produce a suboptimal answer?
Instance 1:
The number of classes is N = 4
The timings of the classes are given by:
1 - 5
3 - 7
6 - 9
8 - 10
Instance 2:
The number of classes is N = 4
The timings of the classes are given by:
2 - 5
6 - 10
11 - 15
1 - 10
Instance 3:
The number of classes is N = 4
The timings of the classes are given by:
1 - 5
6 - 8
9 - 11
12 - 15
Recall the Dance Class problem: Problem Definition **Dance Classes** Input: A collection of $n$ intervals given by their left and right endpoints $(s_1, f_1), \ldots, (s_n, f_n)$, where $s_i < f_i$ for all $1 \leqslant i \leqslant n$. Question: What is the size of the largest collection of mutually pairwise non-overlapping intervals? On which of the following instances will this algorithm produce a suboptimal answer? **Instance 1:** The number of classes is N = 4\ The timings of the classes are given by:\ 1 - 5\ 3 - 7\ 6 - 9\ 8 - 10 **Instance 2:** The number of classes is N = 4\ The timings of the classes are given by:\ 2 - 5\ 6 - 10\ 11 - 15\ 1 - 10 **Instance 3:** The number of classes is N = 4\ The timings of the classes are given by:\ 1 - 5\ 6 - 8\ 9 - 11\ 12 - 15 Figure from the original question paper True or false? Figure from the original question paper