Week 1: Notes

Algorithms

Some introductory notes about algorithms in general:

• An algorithm is a precise sequence of steps to achieve some goal.

• You already know some algorithms from daily life, i.e. algorithms for adding/subtracting/multiplying numbers which you learned in grade school.

• Different algorithms that perform the same task may differ in efficiency, as we'll see in this course.

• Algorithms are a major area of research; some computer scientists spend their entire careers working on them.

• Surprisingly, some problems cannot be solved by any algorithm. You may see a proof of this fact in a more advanced course.

powers of 2

You should know by heart:

• 2⁰ = 1

• 2¹ = 2

• 2² = 4

• 2³ = 8

• 2⁴ = 16

• 2⁵ = 32

• 2⁶ = 64

• 2⁷ = 128

• 2⁸ = 256

• 2⁹ = 512

• 2¹⁰ = 1,024 ≈ 1,000 = 10³ = 1 K = kilo

• 2²⁰ ≈ 1,000,000 = 10⁶ = 1 M = mega

• 2³⁰ ≈ 1,000,000,000 = 1 G = giga

The fact that 2¹⁰ ≈ 10³ allows you to convert between powers of 2 and 10 easily, at least approximately. For example, 2²⁶ = 2⁶ · 2²⁰ = 64 M ≈ 64,000,000.

exponentiation

You should be familiar with these identities:

• a^{u + v} = a^u · a^v

• a^{u – v} = a^u / a^v

• a^uv = (a^u)^v

logarithms

You should be familiar with these identities:

• log_b(uv) = log_b u + log_b v

• log_b(u / v) = log_b u - log_b v

• log_b(u^p) = p log_b u

• log_a b · log_b c = log_a c

integers

integers = ℤ

… , -2, -1, 0, +1, +2, +3, ...

natural numbers = non-negative integers = ℕ

= 0, 1, 2, 3, 4, ...

The mathematical study of the integers is called number theory.

divisibility

Let a, d, q ∈ ℤ. If a = dq then a is divisible by d. a is a multiple of d. d is a factor of a.

Example: What are all factors of 6?

1, 2, 3, 6, -1, -2, -3, -6

(Division Theorem) For any a, b ∈ ℤ with b > 0, there exist unique q, r ∈ℤ such that

a = q · b + r and 0 ≤ r < b

We write

q = quotient of a and b, denoted by a div b
r = remainder, denoted by a mod b

For example, if a = 17 and b = 5, then

q = 3
r = 2
17 = 3 · 5 + 2

So 17 div 5 = 3, and 17 mod 5 = 2.

Or if a = -17 and b = 5, then

q = -4
r = 3
-17 = -4 · 5 + 3

So -17 div 5 = -4, and -17 mod 5 = 3.

For any a ∈ ℤ,

a mod 2 = 0 <==> a is even
a mod 2 = 1 <==> a is odd

For any a ∈ ℤ, a div 1 = a, and a mod 1 = 0.

In Python, (a // b) computes a div b. (a % b) computes (a mod b).

Decimal representation

By longstanding convention, basically every society on Earth writes numbers in base 10, otherwise known as decimal. When we write a number such as 1985, we actually mean a sum of powers of 10:

1985 = 1 · 10³ + 9 · 10² + 8 · 10¹ + 5⁰

In the number above, 1 is the most significant digit, i.e. the one that represents the greatest power of 10. 5 is the least significant digit.

numbers in different bases

We use base 10 by convention, but of course the number 10 is arbitrary. We would now like to work with numbers written in non-decimal bases, i.e. bases other than 10. For example, consider base 5. In the base 5 system, every digit has a value from 0 to 4. Consider the number

2031₅

Here, the subscript 5 means that the number is written in base 5.

The decimal value of the base-5 number above is

2 · 5³ + 0 · 5² + 3 · 5¹ + 1⁰ = 266₁₀

Every positive integer has a unique representation in any base.

Base 2 (binary) is especially common in computer programming. Here are the first natural numbers in base 2:

• 0₂ = 0₁₀

• 1₂ = 1₁₀

• 10₂ = 2₁₀

• 11₂ = 3₁₀

• 100₂ = 4₁₀

• 101₂ = 5₁₀

• 110₂ = 6₁₀

• 111₂ = 7₁₀

• 1000₂ = 8₁₀

We also often use base 16 (hexadecimal), in which we have extra digits A = 10, B = 11, C = 12, D = 13, E = 14, F = 15. For example,

FF₁₆ = 255₁₀ because 15 · 16¹ + 15 · 16⁰ = 240 + 15 = 255