Week 14 Quiz
Use this quiz to test your knowledge and understanding of this week's lectures.
Question 1
Suppose we have a Monte Carlo algorithm that never gives false negatives, and the probability of a false positive is at most \(p\). By repeating the algorithm a constant number of times (independent of the size of the input), we can ensure the probability of a false positive will be less than \(0.01\), provided
- \( p < 1 \).
- \(p < 1 - c \), for some constant \( c > 0 \).
- \( p < 0.5 \).
- \( p < 0.01 \).
Question 2
A linear-time Las Vegas algorithm should
- always run in linear time, and be correct with high probability on all inputs.
- always run in linear time, and be correct on most inputs.
- run in linear time on most inputs, and be correct on all inputs.
- run in linear time on average for all inputs, and be correct on all inputs.
Question 3
Suppose a Monte Carlo algorithm has no false positives, and the probability of a false negative is at most \(0.05\). If the algorithm returns NO, the probability that the correct answer is NO is
- at least \( 0.95\).
- at most \( 0.05\).
- exactly \( 1.00 \).
- impossible to determine from the given information.
Question 4
In our matrix multiplication verification algorithm, using test vectors in \( \{0,1\}^n \) is preferable to test vectors in \( \{1,2\}^n \) because
- it is easier to implement.
- the probability of a false positive is lower.
- Both of the above.
- Neither of the above.
Question 5
Suppose we wish to check if a degree-two polynomial \( f \in \mathbb{R}[x_1, x_2] \) is the zero polynomial. Finding out that \( f \) is zero on all points of which of the following sets guarantees that \( f = 0 \)?
I. \( \{ (-5,0), (-4,-3), (-4,3), (-3, -4), (-3,4), (0,-5), (0,5), (3,-4), (3,4), (4,-3), (4,3), (5,0) \} \)
II. \( \{ (0,0), (0,1), (0,2), (0,3), (1,0), (1,1), (1,2), (1,3), (1,4) \} \)
III. \( \{ (0,0), (0,1), (0,3), (1,1), (1,2), (2,2), (2,3), (3,0), (3,3) \} \)
- I only
- III only
- II and III
- I, II and III
| Submit | Reset |