Introduction to the Design and Analysis of Algorithms
Textbook.
 CS 3343/3341
 Analysis of Algorithms
 Fall 2012
 Recitation 3
 Big-Θ, Etc.
    Week 3: Sep 11-13
 Due (on time): 2012-09-17  23:59:59
 Due (late):        2012-09-21  23:59:59

Recitation 3 should be submitted following directions at: submissions with deadlines
  • 2012-09-17  23:59:59 (that's Mon, 17 Sep 2012, 11:59:59 pm) for full credit.
  • 2012-09-21  23:59:59 (that's Fri, 21 Sep 2012, 11:59:59 pm) for 75% credit.

  1. The first problem will be made accessible during the Recitation hour: Rec 3, In-Class Problem 1 (password protected, use "CS3343" without quotes for "User Name" and password from class just before the recitation).

  1. This problem is concerned with the weird problem: Newton's Method, Part 1: Square Root of Two. In printing results, you should print each successive approximation on a separate line, as we have done with the examples given in class.

    1. Alter the given simple Java or C code that calculates √2 so that it will calculate √10. Run the code to get output (as you are always supposed to do). (Change only the formula for x1. Leave the initial assignment x0 = 1 as it is.)

    2. Alter the given simple Java or C code that calculates √2 so that it will calculate √100000. Run the code. (Again change only the formula for x1. Leave the initial assignment x0 = 1 as it is.)

    3. Compare the answers to Part i and Part ii above and compare the number of loop iterations required. Could you have gotten the answer to Part ii from Part i with less computation?

  1. Use Newton's method to find the unique solution to the equation cos(x) = x. (There is no closed formula for the answer, so the only option is an approximate solution.)

    1. Use x0 = 1 as your initial guess. [Hints: x is in radians, which is what C and Java use by default for cos. Look for a root of the equation f(x) = cos(x) - x. Remember that d/dx(cos(x)) = -sin(x). Print each successive approximation on a separate line. The answer starts out with 0.739....]

    2. What happens with x = -1 as the initial guess?

    3. What happens with x = -13 as the initial guess? [Be prepared for unusual output.]

  1. Simplify the bound O(6*n*√n + 3*n2 + 7*n5/2) . [ See Big-Θ.]

  2. Problem 3.1-3 on page 56. [Explain why the statement, "The running time of algorithm A is at least O(n2)," is meaningless.]

  3. Problem 3.1-4 on page 56. [Is 2n+1 = O(2n)? Is 22n = O(2n)?] For credit you must give reasons for your answers.

  4. Suppose it takes 5 seconds for a low-performance sort to sort 1000 items into order. Assume the sort has Θ(n2) performance. If the constant implied by the bound stays the same, how long would it take to sort 1000000 items?
    Now suppose a high-performance sort also takes 5 seconds to sort 1000 items into order. The better sort has performance Θ(n*log2(n)). Again assuming the implied constant stays the same, how long would it take to sort 1000000 items into order.? [Answers: about 2 months and about 2.75 hours. (Note change in the second answer.)] (Note: I used log base 2 above just to make it more specific, but you get the same answer with log to any base.)

Revision date: 2012-09-03. (Please use ISO 8601, the International Standard.)