Let's learn: algorithms notes part 1

Why Study Algorithms?

*Important for all branches of computer science
*Plays a key role in modern technological innovation
*Provides novel ‘lens’ outside of computer science and technology
 -quantum mechanics, economic markets, evolution
*Challenging (i.e., good for the brain!)
*Fun

Integer Multiplication

Input: two n-digit numbers x and y
Output: the product x.y

“Primitive Operation”: add or multiply
2 single-digit numbers

The Grade-School Algorithm

Upshot: #operations overall <= constant * n**2

The Algorithm Designer’s Mantra

“Perhaps the most important principle for the good algorithm designers is to refuse to be content.”

Can we do better?

Karatsuba Multiplication

Example:
X =  5678
Y =  1234

56 = a
78 = b
12 = c
34 = d

Step 1: Compute a * c = 672

Step 2: Compute b * d = 2652

Step 3: Compute (a+b)*(c+d) = 134*46 = 6164

Step 4: Compute (3) – (2) – (1) = 2840

Step 5: Pad (1) with 4 zeroes at the end * (2) * pad (3) with 2 zeroes

6720000 * 2652 * 284000 = 7006652

A Recursive Algorithm

Write x = 10(n/2)a + b and y = 10(n/2)c + d

Where a, b, c, d are n/2 – digit numbers

[example a =56, b =78, c=12, d=34]

x*y  = (10(n/2)a+b) (10(n/2)c+d)= 10(n)ac + 10(n/2)(ad+bc) + bd (*simple base case omitted)

Idea: recursively compute ac, ad, bc, bd, then compute (*) in the straightforward way

Karatsuba Multiplication:

x * y = 10(n)ac + 10(n/2)(ad+bc) + bd

Step 1: Recursively compute ac

Step 2: Recursively compute bd

Step 3: Recursively compute (a+b) (cd) = ac + ad + bc + bd

Step 4: (3) – (1) – (2) = ad + bc

Upshot: Only need 3 recursive multiplications! (and some additions)