CSCI 570 - HW 2
1 Graded Problems
1. Solve Kleinberg and Tardos, Chapter 2, Exercise 3.
2. Solve Kleinberg and Tardos, Chapter 2, Exercise 4.
3. Solve Kleinberg and Tardos, Chapter 2, Exercise 5.
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(n
2
) time complexity.
(c) F(n) = 4n +
√
3n is both O(n) and Θ(n).
(d) For a search starting at node s in graph G, the DFS Tree is never as
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.
5. Solve Kleinberg and Tardos, Chapter 3, Exercise 2.
1
2 Practice Problems
1. Reading Assignment: Kleinberg and Tardos, Chapter 2 and 3.
2. Solve Kleinberg and Tardos, Chapter 2, Exercise 6.
3. Solve Kleinberg and Tardos, Chapter 3, Exercise 6.
2
