10/5/21, 6:06 PM Quiz: Mid-term 1, Part 1
https://psu.instructure.com/courses/2136575/quizzes/4348784/take?preview=1 1/2
Mid-term 1, Part 1
Started: Oct 5 at 6:05pm
Quiz Instructions
3 ptsQuestion 1
All other 3 choices are not true
Let , , , and be 4 strings over alphabet . Let be the edit distance defined in class. We use to denote
the concatenation of and . Which one of the following is true?
3 ptsQuestion 2
If for all , then must not contain negative cycle reachable from .
If contains negative cycles reachable from , then .
, no matter contains negative cycle or not.
If , then must contain negative cycle reachable from .
Let be a directed graph possibly with negative cycles. Assume that has 10 vertices, and and are two of them.
Define as the length of the shortest path from to using at most edges. Which one of the following is true?
3 ptsQuestion 3
Which of the following is the asymptotic solution of recurrence ?
10/5/21, 6:06 PM Quiz: Mid-term 1, Part 1
https://psu.instructure.com/courses/2136575/quizzes/4348784/take?preview=1 2/2
Quiz saved at 6:06pm
3 ptsQuestion 4
dual 2
dual 4
dual 3
dual 1
For the two points and and three lines , and on the primal plane, which one gives their correct dual points and
dual lines?
3 ptsQuestion 5
Let be an array with distinct integers. Similar to the selection algorithm introduced in class, we partition into
sub-arrays, each of which contains 17 numbers. Let be the median of the medians of the sub-arrays. How many
numbers in are guaranteed larger than ?
Submit Quiz
Mid-term 1, Part 1 CSE 565 Fall 2021 (Instructor: Mingfu Shao)
Problem 1 (3 points).
• Correct. (Note: A more accurate statement would be “all other 3 choices are not always true”.)
• False. Counter-example: A = G, B = G, and C = GG.
• False. Counter-example: A = G, B = T , and C = G.
• False. Counter-example: A = T T , B = T , C = G, and D = T G.
Problem 2 (3 points).
• False. dist(9,v) = dist(i,v) for all i � 10 implies that there does not exist a path from s to v that go
through a negative cycle. But it is still possible that G contains negative cycle reachable from s—it’s
just that such negative cycle cannot reach v. In fact, to show that G does not contain negative cycle
reachable from s, we need this statement to hold for every vertex v.
• False.
• False.
• True. (Proved in class.)
Problem 3 (3 points).
Think about a lower bound and a upper bound of logn: asymptotically n0 logn n0.1:
T (n) = 2T (n/2)+n0 gives T (n) = Q(n), using master’s theorem;
T (n) = 2T (n/2)+n0.1 gives T (n) = Q(n), using master’s theorem.
Therefore, T (n) = 2T (n/2)+ logn must also give T (n) = Q(n).
In fact, a more general form of master’s theorem solves the recurrence: T (n) = aT (n/b)+Q(nd · logs n).
T (n) =
8
<
:
Q(nlogb a) logb a > d
Q(nd · logs+1 n) logb a = d
Q(nd · logs n) logb a < d
Problem 4 (3 points).
• Dual 1: False. Point A is below line p in the primal plane, so in the dual plane p⇤ should be below
line A⇤.
• Dual 2: False. The slope of r is larger than the slope of p in the primal plane, so in the dual plane, the
x-coordinate of r⇤ should be larger than that of p⇤. This option will become true if p⇤ can be moved
slightly to the left so that its x-coordinate can be less than that of r⇤.
• Dual 3: False.
• Dual 4: False.
Note: This problem were regraded so that full points were granted to any answer.
1
Mid-term 1, Part 1 CSE 565 Fall 2021 (Instructor: Mingfu Shao)
Problem 5 (3 points).
Among all n/17 medians, n/34 of them are guaranteed larger than x. There are n/34 subarrays, each of
which contains 8 numbers that are guaranteed larger than x. In total, there are n/34 + 8n/34 = 9n/34
numbers guaranteed larger than x.
2