CS/ECE 374 A (Spring 2022) Midterm 2 Solutions
Answer: Θ(n2).
Justification: by the master theorem, since n + 4n2 = Θ(n2) has a higher growth rate
than nlog2 3+ε.
Copyright By PowCoder代写 加微信 powcoder
[Alternative justification: by unfolding the recurrence (and ignoring floors), T(n) =
3T(n/2)+O(n2) = 9T(n/4)+O(3(n/2)2+n2) = ··· = 3kT(n/2k)+O(k−1 3i(n/2i)2). i=0
Setting k = log2(n/374), we get T(n) ≤ 3log2(n/374)T(374) + O(n2 i(3/4)i) = O((n/374)log2 3 + n2) = O(n2). (And trivially, T (n) = Ω(n2).)]
Justification: The median-of-medians-of-5 algorithm runs in O(n) time, while mergesort runs in Θ(n log n) time. (And n = o(n log n).)
Justification: X has O(n) bits. Thus, line 3 takes O(n) time. So, the total time is O(n2). [Or, to be more precise: X has Θ(i) bits at iteration i. So, the total time is Θ(ni=1 i) = Θ(n2 ).]
Counterexample: take any directed graph that contains a cycle, and take any edge (u, v) that is a back edge.
[Or more concretely, take a directed graph with 3 vertices forming a cycle a, b, c, a. The DFS tree starting at a yields a back edge (c, a), and c finishes before a. ]
Justification: in a DAG, there are no back edges.
Justification: take any sequence of vertices v0,v1,v2,… where vi+1 is an out-neighbor of vi (which must exist when the out-degree of vi is at least one). Some vertex must be repeated in this sequence, yielding a cycle.
[Or: Suppose G does not have a cycle. Then it is a DAG. And as we know, any DAG has a sink with out-degree 0: contradiction.]
Repeatedly run BFS from every vertex (since BFS solves the single-source shortest paths problem for an unweighted graph). Since each BFS takes O(m + n) time, the total time for the n runs is O(n(m + n)) = O(n2) when m = O(n). And O(n2) time is the fastest possible (since the output size is Θ(n2)).
[Note: Floyd–Warshall would require O(n3) time, which is slower; running Dijkstra n times would require O(n2 log n) time, which is slightly slower.]
2. The idea is to recursively split the first half of the array and the second half of the array, which gives
⟨A[1],A[3],…,A[n/2−1],A[2],A[4],…,A[n/2], A[n/2+1],A[n/2+3],…,A[n−1],A[n/2+2],A[n/2+4],…,A[n]⟩,
and then swap the second and third quarters of the array to yield ⟨A[1],A[3],…,A[n/2−1],A[n/2+1],A[n/2+3],…,A[n−1],
as desired.
Pseudocode.
A[2],A[4],…,A[n/2],A[n/2+2],A[n/2+4],…,A[n]⟩,
split(A[1, . . . , n]):
1. ifn=1return
2. split(A[1, . . . , n/2])
3. split(A[n/2+1,…,n])
4. for i = 1 to n/4 do [now swap the second and third quarters]
5. swap A[n/4 + i] with A[n/2 + i]
Analysis. Let T(n) be the running time of split(A[1,…,n]). Lines 2–3 take 2T(n/2) time. Lines 4–5 take O(n) time. So,
O(1) if n = 1 T(n)= 2T(n/2)+O(n) ifn>1
This is the same recurrence as mergesort, and so T (n) = O(n log n).
The swap in line 5 only requires one temporary variable. So, lines 4–5 require only O(1) extra space. So, the whole algorithm requires only O(1) extra space (minor technicality: if one takes the recursion stack into account, the space usage is actually O(log n), but it can be made O(1) with a more careful implementation).
(Note. There are actually O(n)-time algorithms for this kind of problem about permuting an array with O(1) extra space, by using more advanced ideas (chasing cycles). . . )
3. (a) Pseudocode.
1. 2. 3. 4. 5. 6. 7. 8.
fori=1tondoC[i,−1]=−∞
for i = n down to 1 do [Evaluation order: decreasing i.]
fork=0toK do C[i,k] = 1
for j = i + 1 to n do
ifaj >ai thenC[i,k]=max{C[i,k],C[j,k−1]+1} else C[i, k] = max{C[i, k], C[j, k] + 1}
return maxi∈{1,…,n} C[i, K]
The answer we want is maxi∈{1,…,n} C (i, 0, L).
Base case. C(i,−n,l) = C(i,n,l) = −∞ for all i ∈ {1,…,n} and l ∈ {1,…,L}. And C(i,0,1) = ai for all i ∈ {1,…,n} and C(i,k,1) = −∞ for all i ∈ {1,…,n} and k ∈ {−(n − 1), . . . , n − 1} − {0}.
Recursive formula. For each i ∈ {1,…,n} and k ∈ {−(n − 1),…,n − 1} and l ∈ {2,…,L},
max (C(j, k − 1, l − 1) + ai) C(i, k, l) = max j∈{i+1,…,n} such that aj >ai
max (C(j, k + 1, l − 1) + ai) j∈{i+1,…,n} such that aj
with weight −w(u, v).
For each edge (u,v) ∈ E with weight w(u,v) < 0, create an edge from (u,1) to (v,0)
with weight −w(u, v).
Run a single-source shortest path algorithm to compute shortest paths from (s,0) to (t,0), from (s,0) to (t,1), from (s,1) to (t,0), and from (s,1) to (t,1) in G′. If all four paths have nonnegative total weight, return no. Otherwise, take one of these paths with negative total weight and return the corresponding walk in G.
(Justification. A path in G′ corresponds to a walk in G that alternates between positive- and negative-weight edges, and the weight of the path in G′ is the negation of the weight of the corresponding walk in G. Thus, there is a walk from s to t in G of positive total weight satisfying the alternation condition iff one of the four shortest paths in G′ have negative total weight.)
Runtime. The graph has N = 2n vertices and M = m edges. By the Bellman–Ford algorithm, the running time for each of the four shortest path computations is O(MN) = O(mn). Total time: O(mn).
(Alternatively, we could use Floyd–Warshall’s APSP algorithm. The running time would be O(n3), which is worse for sparse graphs. We can’t use Dijkstra’s algorithm, because of negative weights.)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com