The Theory of Computation

Bernard M.E. Moret

ADDITIONAL EXERCISES FOR CHAPTER 2

Additional Problem 2.1
Prove or disprove each of the following three statements.
- n/log n is Omega(sqrt(n))
- 3^{2log n} is O(n³)
- 3²ⁿ is Theta(6ⁿ)
Additional Problem 2.2
- Prove that, for any integer k >= 2, (k+1)ⁿ is not O(kⁿ), but log((k+1)ⁿ) is O(log(kⁿ)).
- Is n^{logloglog n} either of O((log n)!) or Omega((log n)!)?
Additional Problem 2.3
Let f be a function (not necessarily a bijection) that maps the first n natural numbers into themselves. Show that we can identify in linear time the largest subset S of {1,2,...,n} that obeys f(S)=S.
Additional Problem 2.4
A star is a person whom everyone knows, but who knows no one. Suppose that you have a crowd of n people and want to find out if there is a celebrity in the crowd, but without making yourself too conspicuous. You are allowed to ask only questions of the type "do you (person i) know this person (person j)?"
Show how you can identify a unique candidate for star status while asking n-1 of these questions (hint: each question eliminates either the person of whom it is asked or the person to whom it is referring) and then decide whether or not that candidate is indeed a star by asking at most 2(n-1) additional questions.
Additional Problem 2.5
A feedback edge set in an undirected graph is a collection of edges, the removal of which leaves the graph acyclic. Use depth-first search to identify in linear time a feedback edge set of minimum size. (Contrast this result with those of Additional Exercises 7.4 and 7.5.)

Back to The Theory of Computation