Introduction to Algorithms
Week 3: Exercises

1. a mod b

True or false? If a, b are integers with a > b > 0, then a mod b < a / 2.

If true, prove the statement. If false, give a counterexample.

2. Smallest Multiple

Solve Project Euler's problem 5:

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

3. Reverse the Digits

Write a program that reads an integer N and prints out N with its digits reversed. Do not use any strings (except for reading the input) or lists. You must reverse the digits using arithmetic operations only.

4. Painting a Room

A room has dimensions D (width) x 2D (length) x D (height).

What is the total surface area of the room's four walls?
How long will it take to paint the four walls, asymptotically speaking (i.e. in big-O), as a function of D?
How long will it take to paint the room as a function of V, where V is the volume of the room?
Let N = log₂(D). How long will it take to paint the room as a function of N?

5. Powers of Two

(Cormen, exercise 3.1-4)

Is 2ⁿ⁺¹ = O(2ⁿ)? Is 2²ⁿ = O(2ⁿ)?

6. Square Root and Log

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

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

8. Doubling

Consider this program:

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

s = 0
i = 1

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

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

9. Swap the Digits

Find all two-digit decimal numbers whose value remains unchanged if you swap their digits and then read them in base 7. In other words, if a and b are the digits,

a b ₁₀ = b a ₇

10. Digit Cycle

Write a program that rotates the digits in a number: the first digit moves to the last position, and all other digits shift leftward. Do not use any strings except for reading the input. You must accomplish the task by performing arithmetic operations only.

Sample input:

Sample output:

Introduction to Algorithms Week 3: Exercises