CS 252: Algorithms

Rod cutting plus some asymptotics

REMINDER: All problem sets are to be typeset using LaTeX and submitted on paper. See the Course Information page for details.

1. Prove that 2sqrt(log n) ∈ O(n1/2).
2. Prove that n ∉ Ω(n2).
3. Do problems 15.1-1, 15.1-2, 15.1-3, and 15.1-4 from CLRS, 3rd edition