Introduction to the Design and Analysis of Algorithms
(Textbook. Click for information.)
 CS 3343/3341
 Analysis of Algorithms
 Fall 2012
 Recitation 2
 Recursion, Etc.
    Week 2: Sep 4-6
 Due (on time): 2012-09-10  23:59:59
 Due (late):        2012-09-14  23:59:59

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

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

  1. Look at the page Recursive Calculation of Fibonacci Numbers. Consider the excessive execution time taken in calculating Fibonacci numbers using recursion, and in the second program, the extremely short times for the same calculation using iteration.

    From the above page, you can see that it took about 70000 sec. to calculate F[60] using recursion. Suppose you have a machine 100 times as fast as the one used for the above calculation. Looking at the data, give a very rough estimate of the biggest Fibonacci number you could calculate in the same time on this faster machine, using the same recursive algorithm. Suppose instead your machine was a million times as fast. Again very roughly give the biggest Fibonacci number you could then calculate.

Lesson: Recursion isn't always the best solution, or even a good solution.

  1. The program on the xor page shows how to use three assignments involving exclusive-or to interchange the contents of two variables without using a third temporary location. Fill in the remaining values for the truth table below. Then explain how this truth table is proving that the program correctly interchanges 32-bit integer values.

    +---+---+------------+-------------+--------------+
| 1 | 2 |  column 3  |   column 4  |    column 5  |
+---+---+------------+-------------+--------------+
| a | b | a1=a xor b | b1=a1 xor b | a2=a1 xor b1 |
+---+---+------------+-------------+--------------+
| 0 | 0 |     0      |             |              |
| 0 | 1 |     1      |             |              |
| 1 | 0 |     1      |             |              |
| 1 | 1 |     0      |             |              |
+---+---+------------+-------------+--------------+

  1. Look at Weird Topic 1: WOM Storage.
    1. Suppose you have the following information as bits: 01 11 10 11 00 10. Show the result of burning this to storage in the manner of the topic. Then burn the following information as a second generation and show the result: 10 01 00 11 10 10.

    2. Show that the formula involving xor lets you recover the original first two information bits correctly, both first and second generations (01 and 10). (See the xor page.)

  1. Study the page Number Base Conversion carefully.

    1. The "difficulty" in the original program was that the numbers came out in the opposite order from what we wanted. The page shows two ways around this: pushing the numbers on a stack and then popping the stack, or using recursion (with an implicit stack in the background). In either Java or C describe briefly (without a full program) at least one other simple way around this problem.
    2. Adapt one of the programs given so that you can convert the base 10 integer "123456789" to base 8. Change it again slightly so that you can convert this integer to base 16 (hexadecimal). You don't need to write a general program, but you will have to produce the hex digits somehow.
Lesson: Recursion is similar to having a separate copy of the function for each recursive call.
Lesson: Recursion can give you the use of a stack for free.

  1. In each case below, solve for x: [You must show your work. Beware of extraneous solutions. Formulas (1) and (2) on the logs page should come in handy.]

    1. log3(x) = 6.

    2. 2*log9(√x) - log9(6x-1) = 0.

    3. log x + log(x - 1) = log(3x + 12).

    4. ln(10) - ln(7-x) = ln(x).

  2. Calculate log3/2(10). [You must show your work. Logs base 3/2 occur on page 91 of your text.]

  3. Prove that the equation log2(x + y) = log2(x) + log2(y) is not a correct identity. Can you find positive values of x and y for which the equation is true?

  4. How many bits are needed to represent a number that is 100 decimal digits long? [Ans: 333.] How many decimal digits are needed to represent a number that is 1000 bits long? [Ans: 302.] You must show where these answers come from.

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