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?
Consider the greedy approach to the problem where we repeat the following until there are no intervals left:
select the shortest interval, eliminating ties arbitrarily, add it to our solution and eliminate all 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 - 2
3 - 4
5 - 6
7 - 8
Instance 2:
The number of classes is N = 4
The timings of the classes are given by:
4 - 5
3 - 6
2 - 7
1 - 8
Instance 3:
The number of classes is N = 4
The timings of the classes are given by:
1 - 7
8 - 15
6 - 9
16 - 20
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? Consider the greedy approach to the problem where we repeat the following until there are no intervals left: > select the shortest interval, eliminating ties arbitrarily, add it to our solution and eliminate all 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 - 2\ 3 - 4\ 5 - 6\ 7 - 8 **Instance 2:** The number of classes is N = 4\ The timings of the classes are given by:\ 4 - 5\ 3 - 6\ 2 - 7\ 1 - 8 **Instance 3:** The number of classes is N = 4\ The timings of the classes are given by:\ 1 - 7\ 8 - 15\ 6 - 9\ 16 - 20 Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true? True or false?\ It is possible that Independent-Set is in P and the problem of checking a graph has a Hamiltonian Path is not in P.