Horner's Rule and Problem Reduction Transform and Conquer

Horner's Rule and Binary Exponentiation

We will use representation change to design and efficient exponentiation

Horner's Rule

First consider evaluating a polynomial, p(x) = a_nxⁿ + a_n-1x^n-1 + ... + a₁x + a₀

If we calculate powers of x by successive multiplication then the total number of multiplications to evaluate the polynomial is

M(n) = ∑_i=1ⁿ i ε Θ(n²)

This an excess of multiplications.

Horner's rule uccessively uses the previous power calculation to calculate the next power.

p(x) = (...(( a_nx + a_n-1 )x + a_n-1)x... ) + a₀

There are n multiplications. (count the parenthesis)

Binary Exponentiation

Consider the problem of calculating aⁿ. A direct application has cost n and so does not improve the brute force cost.

Represent the power, n, in binary digits,

n = b_I ... b_i ... b₀

then

n = p(x=2) = b_Ix^I + ... + b_ixⁱ + ... + b₀

= b_I2^I + ... + b_i2ⁱ + ... + b₀

So we can use this determine the power of a

a_n = a^p(2) = a ^{bI2I + ... + bi2i + ... + b0}

Note a ^2p+bi2i = a^2p•a^bi = (a^p)²•a^bi

= (a^p)² if b_i=0

or

= (a^p)²•a if b_i =1

Algorithm LeftRightBinaryExponent(a, n = b[0...I])

product ← a

for i ← I-1 downto 0 do

product**

if b[i] = 1 then product ← product*a

return product

There is also a right to left binary exponentiation

Algorithm RightLeftBinaryExponent(a, n = b[0...I))

term ← a

if b[0]=1 then product ← a

else product ← 1

for i ← 1 to I do

term**

if b[i] = 1 then product ← product*term

return product

The number of multiplications is

(I-1) ≤ M(n) ≤ 2(I-1)

so the cost is ε Θ(I) = Θ(lg n)

Problem Reduction Transform and Conquer

The joke about how a math professor makes tea by putting the pot on the shelf.

Examples

1. Least common multiple of two intergers is the smallest integer divisible by m and n

lcm(m, n) = m•n/gcd(m, n)

2. Counting paths between two vertices in a graph represented by adjacency matrix, A, can be calculated by powers of A. Not that A^k[i, j] is the number of paths between v_i and v_j with length k. Note that binary exponentiation can be used for matrices. To determine if the any path between vertices, we need to check Aⁿ. If non zero than there is a path.

3. Find the minimum can be reduce to finding the maximum using

min f(x) = - max(-f(x))

4. The continuous knapsack problem can be reduced to linear programming problem

maximize f(x) = ∑_j v_jx_j

subject to ∑_j w_jx_j ≤ W

0 ≤ x_j ≤ 1 for j = 1, ... , n

4. Many problems can be reduce to a graph problem, the text demonstrate the river crossing problem as a graph.