辅导CMPSC 465编程、讲解Java程序语言、Python，c++编程设计调试 讲解Python程序|解析SPSS
- 首页 >> Java编程 Solution of Mid-term 1 CMPSC 465 Fall 2020
INSTRUCTIONS:
1. You may directly use the algorithms introduced in lectures.
2. You always need to analyze the running time of your algorithm.
3. Unless requested, you don’t need to prove the correctness of your algorithm.
Problem 1 (12 points).
Order the following functions in non-decreasing order by their asymptotic growth rate. Use < and =,
representing “small-o” and “Big-Theta”, in your order (for example: f1 < f2 = f3 < f4 < f5 = f6).
Solution: f6 < f1 < f5 < f4 < f3 < f2
Problem 2 (6 + 6 + 6 = 18 points).
1. Draw an instance of convex hull problem with 6 points, such that if Graham-Scan algorithm runs on
this instance, the sequence of stack operations is (push, push, push, push, pop, pop, push, pop, push).
Solution: Refer Figure 1. Make sure: p3 → p4 → p5 is turning right , so p4 is poped; p2 → p3 → p5
is turning right , so p3 is poped; p2 → p5 → p6 is turning right , so p5 is poped.
Figure 1: Problem 2.1. An correct instance.
1
Solution of Mid-term 1 CMPSC 465 Fall 2020 (Instructor: Mingfu Shao)
2. Let G = (V,E) be a directed graph, and (u, v) ∈ E be an edge of G. During a run of DFS on G, the
[pre, post] interval for u and v are [4,7] and [2,9], respectively. Is it possible that G is a DAG? Either
give an example to show that this is possible, to prove that this is not possible.
Solution: No. The graph cannot be a DAG. This is because [pre(v), post(v)] contains[pre(u), post(u)],
i.e., exploring u is within exploring v, implying that v can reach u. And (u, v) ∈ E. Then this forms a
cycle. Therefore G can be a DAG.
3. Below are the pre- and post-numbers of vertices a,b, c,d, e in a run of DFS on a directed graph (there
are other vertices in the graph that are not shown). One of the vertices has incorrect pre-/post-numbers.
Indicate which one is incorrect and explain why.
vertex pre-number post-number
a 10 21
b 18 25
c 17 30
d 12 15
e 11 16
Solution: a must be the vertex with incorrect pre-/post-numbers. This is because in any DFS run,
two [pre, post] intervals must be either disjoint or nested. In the given values, the interval for a
intersects (partially overlaps) with that for b and c. And all the intervals for b, c, d and e are either
nested or disjoint.
Problem 3 (10 points).
You are given two arrays A and B, each of which contains n distinct integers. Design an algorithm to count
the number of pairs (i, j), 1 ≤ i, j ≤ n, satisfying that A[i] < A[ j] and B[i] < B[ j]. Your algorithm should run
in O(nlogn) time.
Solution: Note: this problem is similar to the counting-inverse-pairs problem (in programming assignment
2), but different. In the inverse pairs problem, we count pairs (i, j) with 1 ≤ i < j ≤ n and A[i] > A[ j]. In
this problem, we count pairs (i, j) with 1 ≤ i, j ≤ n, A[i] < A[ j], and B[i] < B[ j]; there is no requirement that
i < j in this problem, and this makes a difference.
The algorithm is to sort A while keep B synchronized. Formally, this means we are applying the same
permutation to both A and B. To actually do it, we make n pairs: (A[i],B[i]), 1 ≤ i ≤ n, and we sort these n
pairs in which we only use A to compare which pair is smaller (i.e., we define (A[i],B[i]) < (A[ j],B[ j]) if and
only if A[i] < A[ j]). Let (A
0
[i],B
0
[i]), 1 ≤ i ≤ n, be the sorting results. If we only look at A
0
then it is sorted,
[i + 1], for any 1 ≤ i < n. (But this may not be true for B
0
.) We assume π is the underlying
permutation in the sorting, i.e., the i-th pair (A[i],B[i]) becomes the π(i)-th pair after sorting, or equivalently,
A
0
[π(i)] = A[i] and B
0
[π(i)] = B[i]. Therefore, counting the number of pairs (i, j) that satisfies A[i] < A[ j]
and B[i] < B[ j] is equivalent to counting the number of pair (π(i),π(j)) satisfies A
0
[π(i)] < A
0
[π(j)] and
B
0
[π(i)] < B
0
[π(j)]. Since a permutation is a bijection, the latter case is further equivalent to counting the
number of pairs (i, j) satisfies A
0
[i] < A
0
[ j] and B
0
[i] < B
0
[ j]. As A
0
is sorted, i.e., A
0
[i] < A
0
[ j] if and only
if i < j, we have the following equivalent form: to counting the number of pairs (i, j) satisfies i < j and
B
0
[i] < B
0
[ j]. This is exactly the counting-inverse-pairs problem, with B
0 being the input array.
2
Solution of Mid-term 1 CMPSC 465 Fall 2020 (Instructor: Mingfu Shao)
The running time of the algorithm is O(nlogn) as it involves sorting n pairs and calling the solver for
counting-inverse-pairs problem, each of which takes O(nlogn) time.
Note: here is an example; it may help you to understand the solution.
Problem 4 (7 + 7 = 14 points).
You are given a full complete binary tree T of height d (Figure 2). In such a tree the d-th layer consists
of 2d−1
leaves, and each of the vertices in the first (d − 1) layers has exactly 2 children. Each vertex v is
labeled with an integer l(v); all labels are distinct. A vertex v is defined as a special vertex, if the label of v
is larger than the label of its parent (if any) and the labels of its children (if any).
1. Let T(v) be the sub-tree whose root is vertex v. Let pv be the parent of v. Prove that, if l(v) > l(pv),
then T(v) must contain a special vertex.
2. Design an algorithm to find one special vertex v in the tree. Your algorithm should run in O(d) time.
20
19
10 7 8 5
2 4 14 1
21 12
11
17 6
Figure 2: An example of full complete binary tree of height 4. The labels are marked next to vertices. The
special ones are marked red. Note: the problem asks to find one special vertex (not all).
Solution:
1. Let u be the vertex in T(v) with largest label. Then we show that u must be a special vertex of T.
Consider two cases. First, if u 6= v, i.e., u is not the root of T(v), then all the parent and children
of u are within subtree T(v). So u is a special vertex of T as the label of u is larger than all of
these. Second, if u = v, then u is still a special vertex. This is because the label of v is larger than its
parent (the condition) and the label of u is larger than its children (if any), as u has the largest label in
T(v) while the children of u are in T(v) too.
3
Solution of Mid-term 1 CMPSC 465 Fall 2020 (Instructor: Mingfu Shao)
2. Following above statement, we can design a divide-and-conquer algorithm. The recursive function
special-vertex (v) returns one special vertex rooted at v. We always guarantee that, at the time specialvertex
(v) is called, either v is the root of T, or l(v) > l(pv); so, using above statement, a special vertex
always exists in T(v).
function special-vertex (v)
if v does not have any children: return v;
let u1 and u2 be the two children of v;
if l(v) > l(u1) and l(v) > l(u2): return v;
if l(u1) > l(u2): return special-vertex (u1);
if l(u1) < l(u2): return special-vertex (u2);
end function;
To analyze the running time, let T(d) be the running time of this algorithm when the height of subtree
T(v) is d. As in either special-vertex (u1) or special-vertex (u2), the height of the subtree is reduced
by 1, we have recursion T(d) = Θ(1) +T(d −1). Hence, T(d) = Θ(d).
Problem 5 (8 + 8 = 16 points).
We define a pair of vertices u and v in a directed graph is intimate if u can reach v, or v can reach u, or both.
1. Given a directed acyclic graph G = (V,E), design an algorithm to decide if every pair of vertices of G
is intimate. Your algorithm should run in O(|V|+|E|) time. Prove that your algorithm is correct.
2. Given a directed graph G = (V,E), design an algorithm to decide if every pair of vertices of G is
intimate. Your algorithm should run in O(|V|+|E|) time. Prove that your algorithm is correct.
Solution.
1. We can show that for a DAG G, every pair of vertices of G is intimate if and only if G has a unique
linearization. We know how to check if a DAG has a unique linearization (problem 3 of assignment 2)
in O(|V|+|E|) time. Below we prove this statement.
Suppose that G has a unique linearization; let X = (X1,X2,···,Xn) be this linearization. According to
the problem 3 of assignment 2, we know that (Xi
,Xi+1) ∈ E for every 1 ≤ i < n. Consequently, there
exists a path from Xi
to Xj for any 1 ≤ i < j ≤ n. Hence, every pair of vertices is intimate.
Suppose that every pair is intimate. Then for any pair of vertices, its order in any linearization is fixed.
Hence, G must have a unique linearization.
2. Let G
M = (V
M,E
M) be the meta-graph of G; G
M is a DAG. Below, we prove that every pair of vertices
of G is intimate if and only if G
M has a unique linearization. We know how to construct G
M and how
to determine if G
M has a unique linearization in O(|V|+|E|) time.
If G
M has a unique linearization, then again there exists a path between every pair of connected
components of G. Since all vertices within each component are connected, this means that there
exists a path between every pair of vertices of G.
If every pair of vertices of G is intimate, then in G
M every pair of vertices is intimate. Following part
1 of this problem, we know that G
M has a unique linearization.
4
Solution of Mid-term 1 CMPSC 465 Fall 2020 (Instructor: Mingfu Shao)
Bonus Problem (10 points).
A vertex u in a directed graph is defined as a black-hole vertex if there is an edge from every other vertex to
u, and there is no edge from u to any other vertex. Given the adjacency matrix representation G, design an
algorithm to decide if G contains a black-hole vertex. Your algorithm should run in O(|V|) time. (The time
to load the adjacency matrix does not count towards to the running time.)
Solution. Assume V = {1,...,n}. In each of the first n−1 steps one vertex is determined not a black-hole.
The algorithm keeps this invariant: before the i-th step (i = 2,...,n), vertex j and vertices i,i+1,...,n are
still undecided, while vertices {1,...,i−1} \ { j} are known to be not black-holes. This invariant proves the
correctness of the algorithm. The algorithm runs in O(|V|) time, as it tests O(|V|) times of edges.
Algorithm:
j ← 1
for i ← 2 to n do
if (j,i) ∈ E and (i, j) ∈ E then
// neigher j nor i is a black-hole, as they both have
// outgoing edge; in this case, we do nothing
if (j,i) ∈ E and (i, j) 6∈ E then
// node j is not a black-hole, but i might be
j ← i
if (j,i) 6∈ E and (i, j) ∈ E then
// node i is not a black-hole, but j might be
// in this case, we do nothing
if (j,i) 6∈ E and (i, j) 6∈ E then
// neigher j nor i is a black-hole;
// in this case, we do nothing
Test whether j is a black-hole.
5
INSTRUCTIONS:
1. You may directly use the algorithms introduced in lectures.
2. You always need to analyze the running time of your algorithm.
3. Unless requested, you don’t need to prove the correctness of your algorithm.
Problem 1 (12 points).
Order the following functions in non-decreasing order by their asymptotic growth rate. Use < and =,
representing “small-o” and “Big-Theta”, in your order (for example: f1 < f2 = f3 < f4 < f5 = f6).
Solution: f6 < f1 < f5 < f4 < f3 < f2
Problem 2 (6 + 6 + 6 = 18 points).
1. Draw an instance of convex hull problem with 6 points, such that if Graham-Scan algorithm runs on
this instance, the sequence of stack operations is (push, push, push, push, pop, pop, push, pop, push).
Solution: Refer Figure 1. Make sure: p3 → p4 → p5 is turning right , so p4 is poped; p2 → p3 → p5
is turning right , so p3 is poped; p2 → p5 → p6 is turning right , so p5 is poped.
Figure 1: Problem 2.1. An correct instance.
1
Solution of Mid-term 1 CMPSC 465 Fall 2020 (Instructor: Mingfu Shao)
2. Let G = (V,E) be a directed graph, and (u, v) ∈ E be an edge of G. During a run of DFS on G, the
[pre, post] interval for u and v are [4,7] and [2,9], respectively. Is it possible that G is a DAG? Either
give an example to show that this is possible, to prove that this is not possible.
Solution: No. The graph cannot be a DAG. This is because [pre(v), post(v)] contains[pre(u), post(u)],
i.e., exploring u is within exploring v, implying that v can reach u. And (u, v) ∈ E. Then this forms a
cycle. Therefore G can be a DAG.
3. Below are the pre- and post-numbers of vertices a,b, c,d, e in a run of DFS on a directed graph (there
are other vertices in the graph that are not shown). One of the vertices has incorrect pre-/post-numbers.
Indicate which one is incorrect and explain why.
vertex pre-number post-number
a 10 21
b 18 25
c 17 30
d 12 15
e 11 16
Solution: a must be the vertex with incorrect pre-/post-numbers. This is because in any DFS run,
two [pre, post] intervals must be either disjoint or nested. In the given values, the interval for a
intersects (partially overlaps) with that for b and c. And all the intervals for b, c, d and e are either
nested or disjoint.
Problem 3 (10 points).
You are given two arrays A and B, each of which contains n distinct integers. Design an algorithm to count
the number of pairs (i, j), 1 ≤ i, j ≤ n, satisfying that A[i] < A[ j] and B[i] < B[ j]. Your algorithm should run
in O(nlogn) time.
Solution: Note: this problem is similar to the counting-inverse-pairs problem (in programming assignment
2), but different. In the inverse pairs problem, we count pairs (i, j) with 1 ≤ i < j ≤ n and A[i] > A[ j]. In
this problem, we count pairs (i, j) with 1 ≤ i, j ≤ n, A[i] < A[ j], and B[i] < B[ j]; there is no requirement that
i < j in this problem, and this makes a difference.
The algorithm is to sort A while keep B synchronized. Formally, this means we are applying the same
permutation to both A and B. To actually do it, we make n pairs: (A[i],B[i]), 1 ≤ i ≤ n, and we sort these n
pairs in which we only use A to compare which pair is smaller (i.e., we define (A[i],B[i]) < (A[ j],B[ j]) if and
only if A[i] < A[ j]). Let (A
0
[i],B
0
[i]), 1 ≤ i ≤ n, be the sorting results. If we only look at A
0
then it is sorted,
[i + 1], for any 1 ≤ i < n. (But this may not be true for B
0
.) We assume π is the underlying
permutation in the sorting, i.e., the i-th pair (A[i],B[i]) becomes the π(i)-th pair after sorting, or equivalently,
A
0
[π(i)] = A[i] and B
0
[π(i)] = B[i]. Therefore, counting the number of pairs (i, j) that satisfies A[i] < A[ j]
and B[i] < B[ j] is equivalent to counting the number of pair (π(i),π(j)) satisfies A
0
[π(i)] < A
0
[π(j)] and
B
0
[π(i)] < B
0
[π(j)]. Since a permutation is a bijection, the latter case is further equivalent to counting the
number of pairs (i, j) satisfies A
0
[i] < A
0
[ j] and B
0
[i] < B
0
[ j]. As A
0
is sorted, i.e., A
0
[i] < A
0
[ j] if and only
if i < j, we have the following equivalent form: to counting the number of pairs (i, j) satisfies i < j and
B
0
[i] < B
0
[ j]. This is exactly the counting-inverse-pairs problem, with B
0 being the input array.
2
Solution of Mid-term 1 CMPSC 465 Fall 2020 (Instructor: Mingfu Shao)
The running time of the algorithm is O(nlogn) as it involves sorting n pairs and calling the solver for
counting-inverse-pairs problem, each of which takes O(nlogn) time.
Note: here is an example; it may help you to understand the solution.
Problem 4 (7 + 7 = 14 points).
You are given a full complete binary tree T of height d (Figure 2). In such a tree the d-th layer consists
of 2d−1
leaves, and each of the vertices in the first (d − 1) layers has exactly 2 children. Each vertex v is
labeled with an integer l(v); all labels are distinct. A vertex v is defined as a special vertex, if the label of v
is larger than the label of its parent (if any) and the labels of its children (if any).
1. Let T(v) be the sub-tree whose root is vertex v. Let pv be the parent of v. Prove that, if l(v) > l(pv),
then T(v) must contain a special vertex.
2. Design an algorithm to find one special vertex v in the tree. Your algorithm should run in O(d) time.
20
19
10 7 8 5
2 4 14 1
21 12
11
17 6
Figure 2: An example of full complete binary tree of height 4. The labels are marked next to vertices. The
special ones are marked red. Note: the problem asks to find one special vertex (not all).
Solution:
1. Let u be the vertex in T(v) with largest label. Then we show that u must be a special vertex of T.
Consider two cases. First, if u 6= v, i.e., u is not the root of T(v), then all the parent and children
of u are within subtree T(v). So u is a special vertex of T as the label of u is larger than all of
these. Second, if u = v, then u is still a special vertex. This is because the label of v is larger than its
parent (the condition) and the label of u is larger than its children (if any), as u has the largest label in
T(v) while the children of u are in T(v) too.
3
Solution of Mid-term 1 CMPSC 465 Fall 2020 (Instructor: Mingfu Shao)
2. Following above statement, we can design a divide-and-conquer algorithm. The recursive function
special-vertex (v) returns one special vertex rooted at v. We always guarantee that, at the time specialvertex
(v) is called, either v is the root of T, or l(v) > l(pv); so, using above statement, a special vertex
always exists in T(v).
function special-vertex (v)
if v does not have any children: return v;
let u1 and u2 be the two children of v;
if l(v) > l(u1) and l(v) > l(u2): return v;
if l(u1) > l(u2): return special-vertex (u1);
if l(u1) < l(u2): return special-vertex (u2);
end function;
To analyze the running time, let T(d) be the running time of this algorithm when the height of subtree
T(v) is d. As in either special-vertex (u1) or special-vertex (u2), the height of the subtree is reduced
by 1, we have recursion T(d) = Θ(1) +T(d −1). Hence, T(d) = Θ(d).
Problem 5 (8 + 8 = 16 points).
We define a pair of vertices u and v in a directed graph is intimate if u can reach v, or v can reach u, or both.
1. Given a directed acyclic graph G = (V,E), design an algorithm to decide if every pair of vertices of G
is intimate. Your algorithm should run in O(|V|+|E|) time. Prove that your algorithm is correct.
2. Given a directed graph G = (V,E), design an algorithm to decide if every pair of vertices of G is
intimate. Your algorithm should run in O(|V|+|E|) time. Prove that your algorithm is correct.
Solution.
1. We can show that for a DAG G, every pair of vertices of G is intimate if and only if G has a unique
linearization. We know how to check if a DAG has a unique linearization (problem 3 of assignment 2)
in O(|V|+|E|) time. Below we prove this statement.
Suppose that G has a unique linearization; let X = (X1,X2,···,Xn) be this linearization. According to
the problem 3 of assignment 2, we know that (Xi
,Xi+1) ∈ E for every 1 ≤ i < n. Consequently, there
exists a path from Xi
to Xj for any 1 ≤ i < j ≤ n. Hence, every pair of vertices is intimate.
Suppose that every pair is intimate. Then for any pair of vertices, its order in any linearization is fixed.
Hence, G must have a unique linearization.
2. Let G
M = (V
M,E
M) be the meta-graph of G; G
M is a DAG. Below, we prove that every pair of vertices
of G is intimate if and only if G
M has a unique linearization. We know how to construct G
M and how
to determine if G
M has a unique linearization in O(|V|+|E|) time.
If G
M has a unique linearization, then again there exists a path between every pair of connected
components of G. Since all vertices within each component are connected, this means that there
exists a path between every pair of vertices of G.
If every pair of vertices of G is intimate, then in G
M every pair of vertices is intimate. Following part
1 of this problem, we know that G
M has a unique linearization.
4
Solution of Mid-term 1 CMPSC 465 Fall 2020 (Instructor: Mingfu Shao)
Bonus Problem (10 points).
A vertex u in a directed graph is defined as a black-hole vertex if there is an edge from every other vertex to
u, and there is no edge from u to any other vertex. Given the adjacency matrix representation G, design an
algorithm to decide if G contains a black-hole vertex. Your algorithm should run in O(|V|) time. (The time
to load the adjacency matrix does not count towards to the running time.)
Solution. Assume V = {1,...,n}. In each of the first n−1 steps one vertex is determined not a black-hole.
The algorithm keeps this invariant: before the i-th step (i = 2,...,n), vertex j and vertices i,i+1,...,n are
still undecided, while vertices {1,...,i−1} \ { j} are known to be not black-holes. This invariant proves the
correctness of the algorithm. The algorithm runs in O(|V|) time, as it tests O(|V|) times of edges.
Algorithm:
j ← 1
for i ← 2 to n do
if (j,i) ∈ E and (i, j) ∈ E then
// neigher j nor i is a black-hole, as they both have
// outgoing edge; in this case, we do nothing
if (j,i) ∈ E and (i, j) 6∈ E then
// node j is not a black-hole, but i might be
j ← i
if (j,i) 6∈ E and (i, j) ∈ E then
// node i is not a black-hole, but j might be
// in this case, we do nothing
if (j,i) 6∈ E and (i, j) 6∈ E then
// neigher j nor i is a black-hole;
// in this case, we do nothing
Test whether j is a black-hole.
5