Computer Science homework help
Computer Science homework help. 1. For each of the following problems answer True or False and briefly justify you answer.
(a) (5pt) For a connected and undirected graph G, if removing edge e disconnects the graph, then e is a
tree edge in DFS of G.
(b) (5pt) For a DAG G, if there is only one node with no incoming edge, then there exists only one topological ordering.
(c) (5pt) For the stable matching problem, if there is a man m1 and woman w1
such that w1 has the lowest
ranking in m1
’s preference list and m1 has the lowest ranking in w1
’s preference list, then any stable
matching will not contain the pair (m1
, w1
).
(d) (5pt) If we run DFS on a DAG and node u is the first leaf node in the DFS tree, then u has no outgoing
edge.
2
:
2. (10pt) Take the following list of functions and arrange them in ascending order of growth rate. That is, if
function g(n) immediately follows function f (n) in your list, then it should be the case that f (n) is O(g(n)).
• f1
(n) = 3n
3
• f2
(n) = n(log n)
100
• f3
(n) = 2
n log n
• f4
(n) = 2
p
n
• f5
(n) = 2
0.8log n
3
3. (20pt) For a DAG with n nodes and m edges (and assume m ≥ n), design an algorithm to test if there is a
path that visits every node exactly once. The algorithm should run in O(m) time.
4
4. (20pt) Given an array A of n distinct integers and assume they are sorted in increasing order. Design an
algorithm to find whether there is an index i with A[i] = i. The algorithm should run in O(log n) time.
5
Figure 1: In this example, there are 6 flying saucers with (L1
,R1
) = (0, 2), (L2
,R2
) = (2, 7), (L3
,R3
) = (1, 3),
(L4
,R4
) = (6, 9), (L5
,R5
) = (0, 4), (L6
,R6
) = (8, 9). We need at least 3 laser canons to destroy all of them, and
1.5, 3.5, 8.5 is a set of valid positions of these laser canons.
5. (30pt) There are several flying saucers on the sky to attack the Earth. For simplicity, we assume Earth
surface is 1-D and the flying saucers are on the sky, as shown in Figure 1. We know there are n flying
saucers and each of them occupies the open interval (Li
,Ri
) (assume Li
,Ri are integers). To destroy those
flying saucers, we are going to fire the laser canon at some locations. If the laser canon is fired at position
x to the sky, it will destroy all the saucers that intersects with this vertical line, i.e., all the flying saucers
with x ∈ (Li
,Ri
) will be destroyed, as illustrated in Figure 1. However, firing the laser canon is expensive
so we want to find a way to destroy all the flying saucers using as few laser canons as possible.
Mathematically, given n intervals {(Li
,Ri
) | i = 1, .. ., n}, our goal is to find a minimum set of numbers
X = {x1
,. .. , xk
} such that for every interval i, there is at least one x j
in X contained in the interval (Li <
x j < Ri
). Give a linear time algorithm to solve this problem, and prove the correctness of your algorithm.
6