[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

/Discuss this assignment. /Solutions.

1. Bureaucratic part

This part you will not be graded on, but you should do it anyway.

Send me email. My address is <aspnes@cs.yale.edu>. In your message, include:

  1. Your name.
  2. Your status: whether you are an undergraduate, grad student, auditor, etc.
  3. Whether you have ever taken a class that used Grade-o-Matic before.1

  4. Anything else you'd like to say.

Optional: Create an account for yourself on PineWiki, the system that holds the course web pages, by following the UserPreferences link and filling in the form it sends you to. Use the subscription feature to get minute-by-minute spam about page changes (such as updates to this assignment). Say hello to everybody on the CS365/Discuss page.

2. Technical part

This part you will be graded on.

2.1. Asymptotic notation tricks

Show that all of the following statements hold:

  1. For all f, Theta(f(n)) is equal to the intersection of O(f(n)) and Omega(f(n)).
  2. Every polynomial aknk + ak-1nk-1 + ... + a0 with ak > 0 and ai >= 0 for i < k belongs to Theta(nk).

  3. The function na is in o(nb) for any a < b.

  4. The function lna n is in o(nb) for any a and any b > 0. Hint added after homework was distributed: The notation lna n means (ln n)a and not the logarithm of n to the base a. The logarithm of n to base a is written loga n.

  5. If f(n) is in O(r(n)) and g(n) is in O(s(n)), where f(n), g(n), r(n), and s(n) are all non-negative for all n >= 0, then f(n)g(n) is in O(r(n)s(n)). The original version of this problem specificed only that r(n) and g(n) were non-negative, which was (a) almost certainly the result of a typo, and (b) not enough to prove the result if you use the definition of O() that doesn't include absolute values.

2.2. Sums

  1. Do Exercise 2.3.1 from page 67 of LevitinBook.

  2. Do Exercise 2.3.4 from page 68 of LevitinBook.

  1. Ulterior motive: The information in your email will be used to create an account for you in Grade-o-Matic. (1)

2014-06-17 11:58