CS/ECE 374 A (Spring 2022) Conflict Midterm 2 Solutions
Answer: Θ(nlog2 3).
Justification: by the master theorem, since n3/2 has a lower growth rate than nlog2 3−ε
(even without a calculator, one can see 3/2 < log2 3, since 23/2 < 3, i.e., 23 < 32).
Copyright By PowCoder代写 加微信 powcoder
[Alternative justification: by unfolding the recurrence (and ignoring floors), T(n) =
3T(n/2)+n3/2 = 9T(n/4)+3(n/2)3/2 +n3/2 = ··· = 3kT(n/2k)+k−1 3i(n/2i)3/2 = i=0
3kT(n/2k)+n3/2 k−1(3/23/2)i = 3kT(n/2k)+Θ(n3/2(3/23/2)k). Setting k = log (n/2022), i=0 2
we get T(n) ≤ Θ(3kT(2022) + n3/2nlog2(3/23/2)) = Θ(nlog2 3 + nlog2 3) = Θ(nlog2 3).] False.
Justification: Quicksort has O(n log n) expected running time, and may occasionally run in O(n2) time, but mergesort always runs in O(n log n) time.
O(n). O(n2).
Justification: X,Y,Z are O(n) bits long, since Fn ≤ 2n. 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 ).]
Justification: if there is an edge between a vertex u at level i and a vertex v at level i + 3, then v would have been placed at level i + 1 (or earlier) by BFS: contradiction. [Or: the level of a vertex v in a BFS tree rooted at s is just the shortest-path distance δ(s,v)fromstov. Butif(u,v)isanedge,thenδ(s,v)≤δ(s,u)+1. So,ifthelevelof u is i, then the level of v is at most i + 1.]
Justification: in a DAG, the strongly connected components are just the n singletons (sets of size 1).
Justification: If G does not have a cycle, then G is an undirected acylic graph, i.e., a forest, and so m ≤ n−1, where m is the number of edges and n is the number of vertices. But if every vertex has degree at least two, then the total degree is at least 2n and so m ≥ n: contradiction.
[Or: take any sequence of vertices v0,v1,v2,… where vi+1 is a neighbor of vi different from vi−1 (which must exist when the degree of vi is at least two). Some vertex must be repeated in this sequence, yielding a cycle.]
Repeatedly run Dijkstra’s single-source shortest paths algorithm from every source ver- tex. Since Dijkstra’s algorithm (with a Fibonacci heap implementation) takes O(n log n+ m) time, the total time for the n runs is O(n(n log n + m)) = O(n5/2) when m = n3/2. [Note: Floyd–Warshall would require O(n3) time, which is slower.]
2. Note the correction: “find the minimum k such that…” (for otherwise the problem would be trivial).
We assume that all ai’s are positive (because negative elements don’t help and may be re- moved). And we assume that a1 + · · · + an ≥ S (for otherwise there would be no answer).
Pseudocode. The following procedure returns the minimum such k:
search({a1, . . . , an}, S):
1. ifn=1thenreturn1
2. let m be the ⌈n/2⌉-th largest in {a1, . . . , an}
3. letL={ai :ai
Unrolling the recurrence (and ignoring ceilings) gives T (n) = O(n + n/2 + n/4 + · · · ) = O(n) by a geometric series. So, the algorithm runs in O(n) time.
[Alternatively, we can invoke the master theorem (since n obviously has a higher growth rate than nlog2 1+ε, as log2 1 = 0).]
3. (a) Pseudocode.
1. 2. 3. 4. 5.
(b) Definition of subproblems. For each i ∈ {1,…,n} and k ∈ {0,…,r}, let C(i,k) be the max value of the optimal subsequence of ⟨ai, . . . , an⟩ that starts at ai and has exactly k consecutive pairs of distance greater than L.
The answer we want is maxi∈{1,…,n} C(i, r).
Base case. C(i,−1) = −∞ for all i ∈ {1,…,n}.
Recursive formula. For each i ∈ {1,…,n} and k ∈ {0,…,r},
for i = n down to 1 do [Evaluation order: decreasing i.] C[i] = 1
for j = i + 1 to n do
if d(pi , pj ) ≤ L then C [i] = max{C [i], C [j ] + 1}
return maxi∈{1,…,n} C[i]
Run time analysis. Lines 1–4 take O(n2) time. Line 5 takes O(n) time. Total time:
C(i, k) = max j∈{i+1,…,n} such that d(pi,pj )>L
(C (j, k − 1) + d(pi , pj ))
(C(j, k) + d(p , p ))
j∈{i+1,…,n} such that d(pi,pj)≤L 2
Evaluation order. Decreasing i.
Run time analysis. The number of subproblems or table entries is O(nr). The cost to
compute each entry is O(n). Total time: O(n2r). [Note: O(n3) would also be correct.]
Define a new weighted DAG G′ as follows:
The vertices and the edges are the same as the given DAG G.
For each edge (u,v) ∈ E, define the weight of (u,v) in G′ to be −3 if (u,v) is red,
and +1 if (u, v) is blue.
We compute the shortest path from s to t in G′. The answer is yes iff the shortest path
has weight ≤ 0.
Justification. “at least 25% of the edges are red” is equivalent to “the number of blue
edges is at most 3 times the number of red edges”.
Run time analysis. The graph G′ has n vertices and m edges, and can obviously be constructed in O(m + n) time. As explained in class, there is a single-source shortest path algorithm for DAGs by dynamic programming with O(m + n) running time. Total time: O(m + n).
(b) Given G = (V, E), we construct a new weighted directed graph G′ as follows:
For each v ∈ V and each i ∈ {−n,…,n}, create a new vertex (v,i) in G′.
For each edge (u,v) ∈ E with v red and each i ∈ {−n,…,n − 1}, create an edge
from (u,i) to (v,i+1) with weight 1 in G′.
For each edge (u,v) ∈ E with v blue and each i ∈ {−(n−1),…,n}, create an edge
from (u,i) to (v,i−1) with weight 0 in G′.
Run a single-source shortest path algorithm to compute the shortest path from (s, 0) to (t,i) in G′ for every i. Take the shortest among these paths over all i ∈ {1,…,n} if s is blue, and over all i ∈ {0,…,n} if s is red, and return the corresponding walk in G.
(Justification. A path in G′ from (s, 0) to (t, i) corresponds to a walk in G from s to t where i equals the number of red vertices minus the number of blue vertices, excluding s itself. The weight of the path in G′ corresponds to the number of red vertices in the walk, excluding s itself.)
Runtime. The graph has N = O(n2) vertices and M = O(mn) edges, and can be constructed in O(n2 + mn) time. Dijkstra’s single-source shortest path algorithm (which is applicable here since all weights are nonnegative) has running time O(N log N + M ) = O(n2 log n + mn). Total: O(n2 log n + mn).
(Actually, since all the edge weights in G′ are 0 or 1, a variant of BFS can do slightly better: O(N + M) = O(n2 + mn).)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com