Introduction to Algorithms
Week 3: Exercises

1. Powers and Logs

  1. Is 2n+1 = O(2n)?

  2. Is 22n = O(2n)?

  3. Is log2(n) = O(log4(n))?

2. Growth Rates

Order these functions by increasing growth rate: N!, 2N, N10, Nlog N, 10N, N2.

3. Three

Consider this program:

n = int(input('Enter n: '))

b = True
while n > 1:
    if n % 3 == 0:
        n //= 3
    else:
        b = False
        break

print(b)
  1. For which values of n will it print 'True'?

  2. What is its best-case and worst-case big-O running time as a function of n?

4. Fraction Addition

Write a program that reads two fractions, one per line. Each fraction will consist of a numerator and denominator, separated by a slash. Compute the sum of the fractions and print it in reduced form. For example, if the input is

1/2
1/6

then the output will be

2/3

5. Reverse The Digits

Write a program that reads an integer N and writes the same integer with the digits reversed. Reverse the digits mathematically, without using any strings.

6. Base 7 to Base 3

Write a program that reads a number written in base 7, and writes the number in base 3.

7. Large Fermat Number

The Fermat number F7 has 39 digits. It is

F7 = 2128 + 1 = 340,282,366,920,938,463,463,374,607,431,768,211,457

It was first factored in 1970:

F7 = 59,649,589,127,497,217 (17 digits) × 5,704,689,200,685,129,054,721 (22 digits)

Suppose that our implementation of integer factorization via trial division can test 1 billion potential divisors per second. Approximately how long would it take to factor F7?