Introduction to Algorithms
Week 3: Exercises

1. Powers and Logs

Is 2ⁿ⁺¹ = O(2ⁿ)?
Is 2²ⁿ = O(2ⁿ)?
Is log₂(n) = O(log₄(n))?

2. Square Root and Log

Which function grows more quickly, sqrt(log N) or log(sqrt N)?

3. Growth Rates

Order these functions by increasing growth rate: N!, 2^N, N¹⁰, N^{log N}, 10^N, N².

4. 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)

For which values of n will it print 'True'?
What is its best-case and worst-case big-O running time as a function of n?

5. a mod b

Is the following statement true or false?

For all integers a, b with a > b > 0,

a mod b < a / 2.

Prove your assertion.

6. 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

7. 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.

8. Base 7 to Base 3

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

9. Large Fermat Number

The Fermat number F₇ has 39 digits. It is

F₇ = 2¹²⁸+ 1 = 340,282,366,920,938,463,463,374,607,431,768,211,457

It was first factored in 1970:

F₇ = 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 F₇?

Introduction to Algorithms Week 3: Exercises