Introduction to Algorithms
Week 3: Exercises

1. a mod b

Prove that for all integers a, b with a > b > 0,

a mod b < a / 2

2. Powers and Logs

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

3. Square Root and Log

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

4. Three

Consider this program:

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

while n > 1:
  if n % 3 == 0:
    n //= 3
  else:
    print('no')
    break
else:
  print('yes')

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

5. Doubling

Consider this program:

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

s = 0
i = 1

while i < n:
  for j in range(n):
    s += j
  i *= 2

What is the program's running time as a function of n?
In the program, change "range(n)" to "range(i)". Now what is its running time?

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. Largest Prime Factor

Solve Project Euler's problem 3:

What is the largest prime factor of the number 600851475143 ?

To do this, write a program that will print the largest prime factor of any integer N.

8. Reverse The Digits

Write a program that reads an integer N and writes the same integer with the digits reversed. Do not use any string integers; instead, reverse the digits mathematically.

9. Largest Palindrome Product

Solve Project Euler's problem 4:

A palindromic number reads the same both ways. Find the largest palindrome made from the product of two 3-digit numbers.

Introduction to Algorithms Week 3: Exercises