Today:
Announcements:
o Quiz 3 on Tuesday
ECS 20 — Lecture 15 — Fall 2013 —14 Nov 2013
Phil Rogaway
o Solving recurrence relations . o Pigeonhole arguments
Suppose we want to multiply two decimal numbers. We write one number as x = x1 || x0 and the other was y = y1 || y0, each half having m digits (let’s not
worry about what to do if m is odd; no real complications are added). So x=x110m +x0
y=y1 10m +y0,
The product is then
xy = (x110m + x0)(y110m + y0)
= z2102m + z110m + z0 where
z2 = x1y1
z1 = x1y0+ x0y1 z0 = x0y0.
These formulas require four multiplications. Karatsuba observed that xy can be computed in only three multiplications of m-digit values. With z0 and z2 as before we can calculate
z1 = (x1 + x0)(y1 + y0) z2 z0
which holds since
z1 = (x1 + x0)(y1 + y0) x1y1 x0y0 = x1y0+ x0y1
Example Let’s compute 98 76
56 78 ——— 5928
7644
Karatsuba algorithm (1960/1962)
4256 these
5488 11900 = (98+76)(56+78) – 5928 – 5488
two sum to 11900.
———
56075928 = 23316 – 5928 – 5488
= 11900
Comparing the asymptotic running times
= 174*134 – 5928 – 5488
1
But we can also get 11900 as
First, the 4-multiply method:
T(n) = 4T(n/2) + n (when n > 1; T(n) = const when n = 1) = 4(4T(n/4) + n/2) + n
= 4^2 T(n/4) + 2n + n
= 4^3 T(n/8) + n(1 + 2 + 4)
= 4^4 T(n/2^4) + n(1 + 2 + 2^2 + 2^3) =…
= 4^k + n(2^k – 1)
\in n) + O(n^2)
\in (n^2)
Now, the 3-multiply method: T(n) = 3 T(n/2) + n
= 3 (3T(n/4) + n/2) + n
= 3^2 T(n/4) + (3n/2 + n)
= 3^2(3T(n/8) + n/4) + 3n/2 + n
= 3^3 T(n/8) + 3^2n/2^2 + 3n/2 + n
= 3^3 T(n/8) + n(1 + 3/2 + (3/2)^2))
= 3^ 4 T(n/16) + n (1 + (3/2) + (3/2)^2 + (3/2)^3)
=…
= 3^ k T(n/2^k) + n (1 + (3/2) + (3/2)^2 + (3/2)^3 + … + (3/2)^{k-1})
At this point it would be good to know what is S = 1 + x + x^2 + … + x^{k-1} + x^k
Sx = x + x^2 + … + x^k + x^{k+1} 1+Sx = 1+ x + x^2 + … + x^k + x^{k+1} 1+Sx = S + x^{k+1}
S(x-1) = x^{k+1} – 1
S = (x^{k+1} – 1) / (x-1)
It is worth remembering this result (or, better, being able to re-derive it if you need it).
1 + x + x^2 + … + x^{k-1} = (x^k – 1) / (x-1)
So, with x = 3/2, we have
(1 + (3/2) + (3/2)^2 + (3/2)^3 + … + (3/2)^{k-1}) = 2 (3/2)^k – 2
= 3^ k T(n/2^k) + n (1 + (3/2) + (3/2)^2 + (3/2)^3 + … + (3/2)^{k-1})
= 3^ k T(n/2^k) + n ((3/2)^k – 1) / (1/2) Now we want k = lg n, so
= 3^ lg n + 2n (3/2)^lg n
= (2^lg 3)^lg n + 2n 3^lgn / 2^lg n
= n^lg3 + 2 n^lg3
= (n^lg 3)
= (n^1.5849)
Best-known: we can actually multiply two n-digit numbers in time (n log n log log n) )or this number of 2-input gaates)
using the Schönhage–Strassen algorithm (1971) – the third multiplicand
not improved by Fürer’s (2007)
2
Informal definition: for sufficiently large …
Notation
Intuition
Formal Definition
is bounded above
by (up to constant factor)
for some positive k
is bounded below by
for some positive k
is bounded above and
below by
for some positive k1, k2
is dominated
by
for every fixed positive number
for every fixed positive number
dominates
is equal
to asymptoti cally
If an additional example feels needed: do mergesort
3
The asymptotic “debate”
Asymptotic notation is everywhere in computer science, but not everyone is a fan.
Reasons for asymptotic notation:
1. Simplicity – makes arithmetic simple, makes analyses easier
2. Applied to running times: Works well, in practice, to get an understanding of
efficiency
3. When applied to running times: Facilitates greater model-independence
Reasons against:
1. Hidden constants can matter
2. Excessive reliance on asymptotics: may fail to notice about things that one really should
care about
3. Not everything has an “n” value to grow with respect to – or, may really be interested in
one particular n.
There is more than O and Θ. (Table modified from Wikipedia)
Back to the Pigeonhole Principle
If N pigeons roost in n holes, N>n, then some two pigeons share a hole.
Restated: [Pigeonhole principle]
If f : A B where A and B are finite sets, |A|>|B|, then f is NOT injective. Or
[Pigeonhole principle, strong form]
Eg, if 100 pigeons roost in 30 holes, some hole has at least 4 pigeons roosting therein. Ex 0. Any room with 3 or more people has some two of the same gender.
Ex 1. 20 people at a party, some two have the same number of friends. number of friends
proof: 0..18 or 1..19
Ex 2: Given five points inside the square whose side is of length 2, prove that two are within \sqrt{2} of each other.
Soln: divide square into four 1 x 1 cells. Diameter of each cell = \sqrt{2}
Ex 3: In any list of 10 numbers, a_1, …, a_10, there’s a subsequence of (consecutive) numbers whose sum is divisible by 10.
Consider
If f : A B where A and B are finite sets, then so point bB must have at least |B|/|A|
preimages.
4
s_1 = a_1
s_2 = a_1 + a_2
…
s_10 = a_1 + a_2 + … + a_10
Then numbers in the list. If any of these divisible by 10: done.
Otherwise, each is congruent to 1,…, 9 mod 10. to the same thing. Eg, may
a_1 + a_2 + a_3 = 6 (mod 5)
a_1 + a_2 + a_3 + a_4 + a_5 = 6 (mod 5)
So two of the s_i (mod 10) values are congruent
But then
a+4 + a_5 = 0 (mod 10)
Ex 4. (beautiful example) In any room of 6 people, there are 3 mutual friends or 3 mutual strangers (Ramsey theorem, and R(3,3)=6)
1
2
3 54
Remove person 1 5 people left.
Put into two pots: friends with 1, non-friends with 1.
One has at least three people.
If three friends: Case 1: some two know each other: DONE
Case 2: no two know each other: DONE If three non-friends: …o
Difficult Puzzle: What is the minimum number of people that must assemble in a room such that there will be at least n friends or n non-friends: R(n,n)
R(4,4) = 18 (1955)
R(5,5) = ?? open!!! known to be between 43 (1989) and 49 (1995)
R(10,10) =?? open and not tightly determined at all: range 798 (1986)- 23,556 (2002)
6
5