Week 2 Quiz
Use this quiz to test your knowledge and understanding of this week's lectures.
Question 1
Consider a graph \(G\) on vertex set \( [5] \), where the weight \( w_{i,j} \) on the edge from \( i \) to \(j \), if present, is given in the matrix below. How many edges are on the lightest path from vertex \(2 \) to vertex \(5 \)?
\( W = ( w_{i,j} )_{i,j} = \begin{pmatrix} - & 5 & 2 & - & 6 \\ 5 & - & 4 & 2 & - \\ 2 & 4 & - & 1 & 7 \\ - & 2 & 1 & - & 9 \\ 6 & - & 7 & 9 & - \end{pmatrix} \).
- 1
- 2
- 3
- 4
Question 2
If we modify Dijkstra's algorithm to keep track of all lightest paths, then, compared to recording a single lightest path, we need
- exactly the same number of steps and memory.
- the same number of steps, but more memory to store the paths.
- more steps of the algorithm, but the same amount of memory.
- more steps of the algorithm, and more memory to store the paths.
Question 3
A decision problem in \( NP \) might not have a polynomial-time algorithm because
- \(NP\) is by definition the set of problems without a polynomial-time algorithm.
- we can give a correct 'YES' answer in polynomial time, but might need longer for a 'NO' answer.
- our current computers run too slowly.
- we can verify the 'YES' certificates in polynomial time, but are not guaranteed to find such a certificate quickly.
Question 4
In order to show that a decision problem \( Q \) is \(NP\)-hard, it suffices to
- reduce some other \(NP\)-hard problem to \(Q\).
- reduce \(Q\) to some other \(NP\)-hard problem.
- show that every problem in \(P\) reduces to \(Q\).
- show that \(Q\) does not reduce to any problem in \(P\).
Question 5
Suppose we use an \(\alpha\)-approximation algorithm to solve a minimisation problem, and get some result \(R\). What is the narrowest interval in which we can deduce the true minimum \(MIN\) lies?
- \( [R - \alpha, R + \alpha] \)
- \( [ \frac{1}{\alpha} R, R] \)
- \( [ R, \alpha R ] \)
- \( [ \frac{1}{\alpha} R, \alpha R ] \)
| Submit | Reset |