Graded Problems
Solve Kleinberg and Tardos, Chapter 2, Exercise 3.
Solve Kleinberg and Tardos, Chapter 2, Exercise 4.
Solve Kleinberg and Tardos, Chapter 2, Exercise 5.
Which of the following statements are true?
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).
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.
p
F (n) = 4n + 3n is both O(n) and (n).
For a search starting at node s in graph G, the DFS Tree is never as the same as the BFS tree.
BFS can be used to nd the shortest path between any two nodes in a non-weighted graph.
Solve Kleinberg and Tardos, Chapter 3, Exercise 2.
1
Practice Problems
Reading Assignment: Kleinberg and Tardos, Chapter 2 and 3.
Solve Kleinberg and Tardos, Chapter 2, Exercise 6.
Solve Kleinberg and Tardos, Chapter 3, Exercise 6.
2
