Homework 1 Clarifications

Updated Wed 1-16-2013

Unless explicitly stated in the problem or on this page, you should show work for all problems.

• Problem 1a Hint: Reading Chapter 1 will be really useful here.

• Problem 1b Hint: Reading Chapter 1 will also be really useful here.

• Problem 1c You may use induction to prove 1.12a but it is not required.

• Problem 2 You should be able to use the technique of expansion discussed in class on Friday. In particular, look at slide 17 from lecture 3. For the recurrence: T(n) = 10 + T(n/2), the closed form is T(n) = 10 log n + 15.

  The floor function might cause some confusion - but be sure not to ignore it for either part a or part b. For part a, just be sure to use it correctly in your calculations. For part b, here are a few things that may be useful in your calculations. Be sure to remember what the definition of floor means:

  ⌊ x ⌋ = m iff m ≤ x < m + 1

  You may also find some of the rules here useful. Like the fact that floor is idempotent and also how nested divisions work. For part b, the problem says that "For arithmetic simplicity, you may assume n is a sufficiently large power of 2", but you really don't need to do that if you apply some of the useful facts listed above. Regardless, your answer to part b should be exact, not in big-O notation and you should go back and check that your closed form gives you the exact same answers for T(1)- T(8) that you calculated in part a.

• Problem 3 Just filling in the blanks in the table is enough for problem 3. You do not need to show any work. It is fine to make a few approximations (e.g. 30 days per month, 365 days per year, or 12*30 = 360 days per year, or for something like n = 1234567890, you can use 1.23 * 10^9).

• Problem 5 The main thing I want you to get practice with on this problem is using the definitions of Big-O, Big Omega, and Big Theta. The term "prove" might be slightly strong here. For all of a-e you will probably be using the definitions and coming up with values for c and n0, manipulating things to get to a point where it is obvious that those values will "work" as n gets larger. To really "prove" that we could take limits or use LHopital's rule (see p. 31 in Weiss). For this problem you do not need to go that far (although it is fine to do so), as long as it is obvious that your values of n0 and c will work.

  To show something is false, come up with a counter example. For parts b and c, this means functions that would make the statement not be true (again, be sure to use the definition to show that it could not be true). For parts a, d, and e, show how you could *not* pick positive constants c and n0 to make it true. I realize that sounds a little strange in the abstract, but I think once you start working on it you will be able to see what I mean. Keep in mind various manipulations we can do to both sides of an equation like taking the log or treating each side as an exponent if the current way of looking at things is not obvious to you.

• Problem 5 You can assume that the functions will only have positive values (similar to what actual runtimes would be).

• Problem 6 You do not need to show work for part a. Work is also not required for part b, but I would recommend showing some for possible partial credit.