Introduction to Algorithms
Week 1: Exercises

These are optional exercises for practicing the concepts we learned this week.

1. Powers of Two

What is the approximate value of

a) 2¹⁴

b) 2³²

c) 8⁸

2. Logarithms

What is the approximate value of

a) log₂(8,000,000,000)

b) log₁₆(16,000,000)

3. A Slow Connection

A notebook computer's disk holds 500 Gb of data. We would like to send the data across an extremely slow network that transfers only 1 byte/second. Approximately how long will the transfer take?

4. Squares Mod 4

Is this statement true or false?

For all n ∈ ℤ, n² mod 4 < 2.

Prove your answer.

5. Making Change

Write a Python program that reads a price in Czech crowns. Print out a combination of 20-Kč, 10-Kč, 5-Kč and 1-Kč coins that add up to the price, using the smallest possible number of coins.

Enter price: 67
20 Kc: 3
10 Kc: 0
5 Kc: 1
1 Kc: 2

6. Hours and Minutes

Write a Python program that reads a number of minutes since midnight and prints a time in the form (hours : minutes).

Minutes since midnight: 150
The time is 2:30

7. Hours, Minutes, Seconds

Write a Python program that reads a number of seconds since midnight and prints a time in the form (hours : minutes : seconds).

Seconds since midnight: 9089
The time is 2:31:29

8. 20 Minutes Later

Read two numbers representing a 24-hour time in hours and minutes. Print the time that is 20 minutes later, wrapping past midnight if necessary.

Hours: 2
Minutes: 30
2:50
===
Hours: 5
Minutes: 50
6:10
===
Hours: 23
Minutes: 55
0:15

9. N Minutes Later

Read two numbers representing a 24-hour time in hours and minutes. Read another number representing an offset N in minutes (a positive number). Print the time that is N minutes later, wrapping past midnight if necessary.

Hours: 2
Minutes: 30
Offset: 20
2:50
===
Hours: 5
Minutes: 50
Offset: 100
7:30
===
Hours: 23
Minutes: 55
Offset: 1000
16:35