-
[Full correct] Of the following dynamic programming algorithms covered in lecture, which ones always perform $\mathcal{O}(1)$ work per subproblem? [Check all that apply.]
- [ ] The dynamic programming algorithm for the optimal binary search tree problem
- [x] The dynamic programming algorithm for the knapsack problem
- [x] The Floyd-Warshall all-pairs shortest path problem
- [x] The dynamic programming algorithm for sequence alignment problem
- [ ] The Bellman-Ford shortest-path algorithm
-
[Full correct] Assume that $P \neq NP$. Which of the following problems can be solved in polynomial time? Check all that apply.
- [ ] Given a directed graph with nonnegative edge lengths, compute the length of a longest cycle-free path between of any pair of vertices (i.e. $\max_{P \in \mathcal{P}{uv}}\sum{e \in \mathcal{P}}c_e$, where $\mathcal{P}_{uv}$ denotes the set of cycle-free $u-v$ pairs).
- [x] Given a directed acyclic graph with real-valued edge lengths, compute the length of a longest path between any pair of vertices.
- [ ] Given a directed graph with real-valued edge lengths, compute the length of a longest cycle-free path between of any pair of vertices (i.e. $\max_{P \in \mathcal{P}{uv}}\sum{e \in \mathcal{P}}c_e$, where $\mathcal{P}_{uv}$ denotes the set of cycle-free $u-v$ pairs).
- [x] Given a directed graph with nonnegative edge lengths, compute the length of a maximum-length shortest path between of any pair of vertices (i.e. $\max_{u, v\in V}d(u, v)$, where $d(u, v)$ denotes the shortest-path distance between $u$ and $v$).
-
[Full correct] Recall the all-pairs shortest-paths problem. Which of the following algorithms are guaranteed to be correct on instances with negative edge lengths that don’t have any negative-cost cycles? [Check all that apply]
- [x] Run the Bellman-Ford algorithm $n$ times, once for each choice of a source vertex.
- [ ] Run Dijkstra’s algorithm $n$ times, once for each choice of a source vertex.
- [x] Johnson’s reweighting algorithm.
- [x] The Floyd-Warshall algorithm
-
[Full correct] Suppose a computational problem $\Pi$ that you care about is NP-complete. Which of the following is true? [Check all that apply]
- [x] You should not try to design an algorithm to solve $\Pi$ correctly and in polynomial time for every possible instance (unless you’re trying to prove that $P = NP$).
- [ ] Since the dynamic programming design paradigm is only useful for designing exact algorithms, there’s no point in trying to apply it to the problem $\Pi$.
- [ ] NP-completeness is a “death sentence”; you should not even try to solve the instances of $\Pi$ that are relevant for your application.
- [x] If your boss criticizes you for failing to find a polynomial-time algorithm for $\Pi$, you can legitimately claim that thousands of other scientists (including Turing Award winners, etc.) have likewise tried and failed to solve $\Pi$.
-
Which of the following statements are logically consistent with our current state of knowledge (i.e. with the mathematical statements that have been formally proved?) [Check all that apply.]
- [x] There is no NP-complete problem that can be solved in $\mathcal{O}(n^{\log{n}})$ time, where $n$ is the size of the input.
- [ ] Some NP-complete problems are polynomial-time solvable, and some NP-complete problems are not polynomial-time solvable.
- [x] There is an NP-complete problem that can be solved in $\mathcal{O}(n^{\log{n}})$ time, where $n$ is the size of input.
- [x] There is an NP-complete problem that is polynomial-time solvable.
-
[Full correct] Of the following problems, which can be solved in polynomial-time by directly applying algorithmic ideas that were discussed in lecture and/or the homeworks? [Check all that apply]
- [x] Given an undirected graph $G$ and a constant value of $k$ (i.e. $k \in \mathcal{O}(1)$, independent of the size of $G$), does $G$ have a vertex cover of size at most $k$?
- [x] Given an undirected graph $G$ and a constant value of $k$ such that $k \in \mathcal{\Theta}(\log{n})$, where $n$ is the number of vertices of $G$, does $G$ have a vertex cover of size at most $k$?
- [x] Given an undirected graph $G$ and a constant value of $k$ (i.e. $k \in \mathcal{O}(1)$, independent of the size of $G$), does $G$ have an independent set of size at most $k$?
- [ ] Given an undirected graph $G$ and a constant value of $k$ such that $k \in \mathcal{\Theta}(\log{n})$, where $n$ is the number of vertices of $G$, does $G$ have an independent set of size at most $k$?
-
[Full correct] In lecture we gave a dynamic programming algorithm for the traveling salesman problem. Does this algorithm imply that $P = NP$? [Check all that apply.]
- [ ] Yes, it does.
- [ ] No. Since we sometimes perform a super-polynomial amount of work computing the solution of a single problem, the algorithm does not run in polynomial time.
- [ ] No. Since we perform a super-polynomial amount of work extracting the final TSP solution from the solutions of all subproblems, the algorithm does not run in polynomial time.
- [ ] No. A polynomial-time algorithm for TSP does not necessarily imply that $P = NP$
- [x] No. Since there are an exponential number of subproblems in our DP formulation, the algorithm does not run in polynomial time.
-
[Full correct] Consider the Knapsack problem and the following greedy algorithm: (1) sort the items in nonincreasing order of value over size (i.e., the ratio $\frac{v_i}{w_i}$); (2) return the maximal prefix of items that fits in the Knapsack (i.e., the $k$ items with the largest ratios, where $k$ is as large as possible subject to the sum of the item sizes being at most the knapsack capacity $W$). Which of the following are true? [Check all that apply.]
- [x] If the size of every item is at most 20% of the Knapsack’s capacity (i.e. $w_i \leq \frac{W}{5}\ \forall i$), then this algorithm is guaranteed to output a feasible solution with total value at least 80% times that of an optimal solution.
- [x] If all items have the same size, then this algorithms always outputs an optimal solution (no matter how ties are broken).
- [x] If all items have the same value, then this algorithms always outputs an optimal solution (no matter how ties are broken).
- [ ] This algorithm always output a feasible solution with total value at least 50% times that of an optimal solution.
- [ ] If all items have the same value/size ratio, then this algorithm always outputs an optimal solution (no matter how ties are broken).
-
[Full correct] Which of the following statements are true about the generic local search algorithm? [Check all that apply.]
- [ ] The generic local search algorithm is guaranteed to be terminate in a polynomial number of iterations.
- [x] The output of the generic local search algorithm generally depends on the choice of the starting point.
- [x] The output of the generic local search algorithm generally depends on the choice of the superior neighboring solution to move to next (in an iteration where there are multiple such solutions).
- [ ] The generic local search algorithm is guaranteed to eventually converge to an optimal solution.
-
[Full correct] Which of the following statements are true about the tractability of the Knapsack problem? [Check all that apply.]
- [x] Assume that $P \neq NP$. The special case of the Knapsack problem in which all item values are positive integers less than or equal to $n^5$, where $n$ is the number of items, can be solved in polynomial time.
- [ ] Assume that $P \neq NP$. The special case of the Knapsack problem in which all item values, item sizes and the knapsack capacity are positive integers, can be solved in polynomial time.
- [x] Assume that $P \neq NP$. The special case of the Knapsack problem in which all item sizes are positive integers less than or equal to $n^5$, where $n$ is the number of items, can be solved in polynomial time.
- [x] If there is a polynomial-time algorithm for the Knapsack problem in general, then $P = NP$.