Questions on algorithms
The following set of questions was created by Avrim and Manuel Blum, CMU, who kindly agreed to allow reproduction of these questions on this website.
Problem 1: An algorithm to factor positive integers takes as input a binary number N and outputs the prime factorization of N. Q: What is n, the size (length) of the input, as a function of N? Your answer should be correct up to ± 1.
Problem 2: Suppose we have three functions f(n), g(n), and h(n) such that f(n) = O(h(n)) and g(n) = O(h(n)). Must it be the case that f(n) = O(g(n))? Explain why or give a counterexample showing why not.
Problem 3: For each pair <f,g> of functions below, list which of the following are true: f(n) = o(g(n)), f(n) = Theta(g(n)), or g(n) = o(f(n)).
- (a) f(n) = ln(n), g(n) = lg(n). ["ln" is log-base-e, and "lg" is log-base-2]
- (b) f(n) = n2, g(n) = n*lg(n).
- (c) f(n) = 2n, g(n) = 4n.
Problem 4. Sorting.
(a) Show that it is possible to sort any array of 4 elements using only 5 comparisons. Note: there are multiple correct ways to do this.
(b) Is it possible to sort any array of size 4 using only 4 comparisons? Why or why not?