代写CMPSC 465编程、代做Java程序语言、Python，c++编程设计调试

日期：2020-11-06 11:24

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