1
CSCI 570 – Fall 2020 – HW 2 Solution
Graded Problems
1. Solve Kleinberg and Tardos, Chapter 2, Exercise 3.
Answer: We know from the text that polynomials grow slower than exponentials. Thus, we will consider f1, f2, f3, f6 as a group, and then put f4 and f5 after them. For polynomials fi and fj, we know that fi and fj can be ordered by comparing the highest exponent on any term in fi to the highest exponent on any term in fj. Thus, we can put f2 before f3 before f1. Now, since f6 grows faster than n2, and we know that logarithms grow slower than polynomials, so f6 grows slower than nc for any c > 2. Thus we can insert f6 between f3 and f1. Finally come f4 and f5, we know that exponential can be ordered by their bases, so put f4 before f5. Therefore, in ascending order of growth, the list is f2, f3, f6, f1, f4, f5.
2. Solve Kleinberg and Tardos, Chapter 2, Exercise 4.
Answer: In ascending order of growth, the list is g1(n), g3(n), g4(n), g5(n), g2(n), g7(n), g6(n). In most cases calculating the logarithms of both sides makes the compar-
ison easier.
3. Solve Kleinberg and Tardos, Chapter 2, Exercise 5.
Answer: Assume that functions f(n) and g(n) take nonnegative values.
(a) False. Consider for example f (n) = 2, ∀n and g(n) = 1, ∀n. Clearly,f(n)=O(g(n)). Observethatlog2(f(n))=1,∀nandlog2(g(n))=
0, ∀n. Hence log2(f(n)) ̸= O(log2(g(n))).
Note: If we further add the constraint that ∃N such that g(n) ≥
2, ∀n > N , then the statement becomes true.
(b) False. Consider for example f(n) = 2n and g(n) = n. Clearly 4n is not O(2n).
1
(c) True. Since f(n) = O(g(n)), there exists positive constants c and n0 such that f(n) ≤ cg(n),∀n ≥ n0. This implies f(n)2 ≤ c2g(n)2,∀n ≥ n0, which in turn implies that f(n)2 = O(g(n)2).
4. Which of the following statements are true?
(a) If f, g, and h are positive increasing functions with f in O(h) and g
in Ω(h), then the function f + g must be in Θ(h).
(b) Given a problem with input of size n, a solution with O(n) time
complexity always costs less in computing time than a solution with
O(n2) time complexity.
√
3n is both O(n) and Θ(n).
(d) For a search starting at node s in graph G, the DFS Tree is never as
(c) F(n) = 4n +
the same as the BFS tree.
(e) BFS can be used to find the shortest path between any two nodes in a non-weighted graph.
Answer:
(a) False. Consider for instance f(n) = n and g(n) = n2. Clearly n + n2 is not in Θ(n).
(b) False. The O(n) notation merely gives an upper bound on the run- ning time. To claim one is faster than other, you need an upper bound for the former and a lower bound (Ω) for the latter.
(c) True. The dominant term is 4n, which is obviously both O(n) and Ω(n)
(d) False. For instance, G being a tree is a counterexample.
(e) True.
5. Solve Kleinberg and Tardos, Chapter 3, Exercise 2.
Answer: Without loss of generality assume that G is connected. Other- wise, we can compute the connected components in O(m + n) time and deploy the below algorithm on each component.
Starting from an arbitrary vertex s, run BFS and obtain a BFS tree (call
it T). If G = T, then G is a tree and has no cycles. Otherwise, G has
a cycle and hence there exists an edge e = (u, v) such that e is in G but
not in T . Find the least common ancestor of u and v in the tree. Call the
least common ancestor w. There exist a unique path (call P1) in T from
u to w (and likewise a unique path P2 in T from v to w). These paths
can be constructed in O(m) time by starting from u (respectively from v)
and going up the tree until w is reached. Output the cycle e concatenated
with P concatenated with P ̄ . Here P ̄ denotes P in the reverse order. 2111
2
2
Practice Problems
1. Reading Assignment: Kleinberg and Tardos, Chapter 2 and 3. 2. Solve Kleinberg and Tardos, Chapter 2, Exercise 6.
Answer:
(a) The outer loop of the given algorithm runs for exactly n iterations, and the inner loop of the algorithm runs for at most n iterations. Therefore, the line of code that adds up array entries A[i] through A[j] (for various is and js) is executed at most n2 times. Adding up any array entries A[i] through A[j] takes O(j − i + 1) operations, which is O(n). Store the results in B[i, j] requires only constant time. Therefore, the running time of the entire algorithm is at most n2·O(n), and so the algorithm runs in O(n3).
(b) Consider the times during the execution of the algorithm when i ≤ n 4
and j ≥ 3n. In this case, j−i+1 ≥ 3n −n +1 > n. Therefore, adding 4442
up the array entries A[i] through A[j] takes at least n operations. How 2
many times during the execution of the algorithm do we encounter such cases (i < n and j > 3n)? There are n2 pairs of (i,j) with
i < n and j > 3n . The given algorithm enumerates over all of them, 44
such pair. Therefore, the algorithm perform at least n · n 2 = n3
operations. This is Ω(n3).
(c) Consider the following algorithm:
for i = 1,2,··· ,n do
Set B[i,i+1] to A[i]+A[i+1]
end for
for k = 2, 3, · · · , n − 1 do
for i = 1, 2, · · · , n − k do j=i+k
B[i, j] to be B[i, j − 1] + A[j] end for
end for
This algorithm works since the values B[i, j−1] were already computed in the previous iteration of the outer for loop, when k was j − 1 + i, since j−1−i < j−i. It first computes B[i,i+1] for all i by summing A[i] with A[i + 1]. This requires O(n) operations. For each k, it then computes all B[i,j] for j−i = k by setting B[i,j] = B[i,j−1]+A[j]. For each k, this algorithm performs O(n) operations since there are at most n B[i, j]’s such that j − i = k. There are less than n values of k to iterate over, so this algorithm has running time O(n2).
3
444
and as shown above, it must perform at least n operations for each 2
2 4 32
3. Solve Kleinberg and Tardos, Chapter 3, Exercise 6.
Answer: Assume that G contains an edge e = (x, y) that does not belong toT. SinceT isaDFStreeand(x,y)isanedgeofGthatisnotanedge of T, one of x or y is ancestor of the other. On the other hand, since T is a BFS tree if x and y belong to layer Li and Lj respectively, then i and j differ by at most 1. Notice that since one of x or y is an ancestor of the other, we have that i ̸= j and hence i and j differ by exactly 1. However, combining that one of x or y is ancestor of the other and that i and j differ by 1 implies that the edge (x, y) is in the tree T. It contradicts the assumption that e = (x,y) that does not belong to T. Thus G cannot contain any edges that do not belong to T.
4