1
CSCI 570 – Fall 2020 – HW 2
Due September 9th
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(n2) time complexity.
¡Ì
(c) F(n) = 4n +
(d) For a search starting at node s in graph G, the DFS Tree is never as
3n is both O(n) and ¦¨(n). 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