1. Suppose that an algorithm A runs in time f_A(n) = 2n² + 7n and that an algorithm B runs in time f_B(n) = 45n + 4, for problems sizes of n. For what values of n is algorithm A faster than

B. That is, for what n is f_A(n) < f_B(n)?

2. Prove part 7 of Lemma 1.1 about logarithms. Use one of the earlier parts of Lemma 1.1 and consider taking the log of both sides.

3. How many different arrangements for a 52 card deck are there? How does this compare to the 1018 seconds that have passed since the Big Bang?

4. Show from definitions that P(S) = P(S | T)P(T) + P(S | not T)P(not T).

5. Prove equation 1.6 of your textbook.

6. Write an algorithm to find the second largest integer in a list of n integers. How many comparisons does your algorithm do in the worst case?

7. Prove Lemma 1.10 of your textbook.

8. Prove or disprove ∑ⁿ_i=1 i²∈θ(n²).

9. Draw a decision tree for the binary search algorithm (Algorithm 1.4 on pages 55-56) for n = 17.

10. Add a row to Table showing the maximum input size that can be solved in one hour.