`|= `@=

Applied Algorithms Anna Karlin, 426C Sieg
CSE 589, Autumn 2000

Homework # 1
Due in class, October 4

1.

(Skiena, p. 25, problem 1-2.) Suppose that an algorithm A runs in worst-case time f(n) and algorithm B runs in worst-case time g(n). For each of the following questions, answer either yes, no or can't tell and explain why.

(a)

Is A faster than B for all n greater than some n₀ if $g(n) = \Omega (f(n)\log n)$?

(b)

Is A faster than B for all n greater than some n₀ if $g(n) = O (f(n)\log n)$?

(c)

Is A faster than B for all n greater than some n₀ if $g(n) = \Theta (f(n)\log n)$?

(d)

Is B faster than A for all n greater than some n₀ if $g(n) = \Omega (f(n)\log n)$?

(e)

Is B faster than A for all n greater than some n₀ if $g(n) = O (f(n)\log n)$?

(f)

Is B faster than A for all n greater than some n₀ if $g(n) = \Theta (f(n)\log n)$?

2.

(Skiena, p. 25, problem 1-3.) Big Oh: For each of the following questions, briefly explain your answer.

(a)

If I prove that an algorithm takes O(n²) worst-case time, is it possible that it takes O(n) on some inputs?

(b)

If I prove that an algorithm takes O(n²) worst-case time, is it possible that it takes O(n) on all inputs?

(c)

If I prove that an algorithm takes $\Theta(n^2)$ worst-case time, is it possible that it takes O(n) on some inputs?

(d)

If I prove that an algorithm takes $\Theta(n^2)$ worst-case time, is it possible that it takes O(n) on all inputs?

(e)

Is the function $f(n)=\Theta(n^2)$ where f(n)=100n² for even n and $f(n)= 20n^2-n\log _2 n$ for odd n?

3.

Prove that the Traditional Marriage Algorithm must terminate on the day that every girl has received a proposal.

4.

In class we argued that the Traditional Marriage Algorithm will never require more than n² days to terminate. In fact, it is possible to prove a tighter upper bound, n² -2n+ 2, on the maximum number of days until the algorithm terminates.

• Describe a set of preference lists that requires n² -2n + 2 days to terminate.
• Extra Credit. Prove that for any set of preference lists, it can take no longer than n² - 2n + 2 days until the algorithm terminates.

5.

John and Sara have a party to which they invite n other married couples. As is normal at parties, handshaking took place. Of course, noone shook their own hand or their spouses hand (and not everyone shook everyone else's hand). After all the handshaking was over, John asked all the other people present including his wife Sara ``how many different people's hands did you shake this evening?'' Interestingly, they each gave a different answer. From the information given, deduce how many different people's hands Sara shook that evening. (There is only one possible answer!) Prove your answer by induction on n. (Hint: try working through the solution for several small values of n before going to the general case.)