Sir's On Basics Of Algorithm

Math. Tools and Induction Pseudo-code for Algorithm

We use pseudo-code for algorithm. Example: computing the factorial n! Function f(n) Input: n ≥ 0 Output: The value of n! f := 1; for i = 2 to n do f := f ∗ i; endfor end. Reading Material: Chapter 1,2 of Textbook 1, and Chapter 1 of Textbook 2.

Jiming Peng, AdvOL, CAS, McMaster

1

Ceiling and Floor Functions from reals to integers: x = r.s. Here r.s stands for r + s. Typically, s ∈ [0, 1]. Ceiling: ⌈x⌉ = ⌈r.s⌉ =

   r + 1 ifs > 0

⌊x⌋ = ⌊r.s⌋ =

  r

Floor:

 r

ifs = 0

ifs < 1

  r + 1 ifs = 1

Examples: ⌊3.4⌋ = 3, ⌈3.4⌉ = 4;

⌊−1.3⌋ = −2, ⌈−2.5⌉ = −2.

Jiming Peng, AdvOL, CAS, McMaster

2

A Relation of Ceiling and Floor Theorem 1 For any reals x and y, we have ⌊x⌋ − ⌈y⌉ ≤ ⌈x⌉ − ⌈y⌉ ≤ ⌈x − y⌉. Proof: Let x = m.r, y = n.s, 0 ≤ r, s < 1. There are four cases. (1) r = 0 or s = 0; (2) r > s > 0; (3) s > r > 0; (4) r = s.

• Case 1: r = 0, s > 0. We have ⌈x⌉ − ⌈y⌉ = m − (n + 1) < m − n = ⌈x − y⌉. • Case 2: r > s > 0. It follows ⌊x⌋ − ⌈y⌉ ≤ ⌈x⌉ − ⌈y⌉ = m − n < ⌈(m − n).r⌉ = ⌈(m − n).(r − s)⌉ = ⌈x − y⌉.

Cases 3 and 4 are left for exercise.

Jiming Peng, AdvOL, CAS, McMaster

3

Logs & Exponentials loga x = y if and only if ay = x. Consider the following issue, how many times can x be halved before it falls equal to or below 1? This is an optimization problem: x min n s.t. n ≤ 1. 2 Since x ≤ 2n, we obtain a lower bound for n: n ≥ log2 x. Thus, the answer is ⌈log2 x⌉. From now on, we denote by log n the expression log2 n. Some relations about logs and exponentials: 

c b a = ab·c = (ac)b ;



 b a (ac) = ab+c;

loga b · c = loga b + loga c; loga b/c = loga b − loga c; loga bc = c loga b;

Jiming Peng, AdvOL, CAS, McMaster

logc b loga b = log a. c

4

Notations Big O notation: for two functions f (n) and g(n), if there exist constants c and N such that for all n ≥ N , the relation g(n) ≤ cf (n) holds. Then we say g(n) = O (f (n)). Lemma If f (n) = O(s(n)) and g(n) = O(r(n)), then f (n)+g(n) = O(r(n)+s(n)) and f (n)g(n) = O(r(n)s(n)). On the other hand, if there exist constants c and N such that for all n ≥ N , the relation g(n) ≥ cf (n) holds. Then we say g(n) = Ω (f (n)). If f (n) = O(g(n)) and f (n) = Ω(g(n)), then we say f (n) = Θ(g(n)).

Jiming Peng, AdvOL, CAS, McMaster

5

Examples In general, exponential > polynomial > Logarithmic. Among various polynomials, the degree of the polynomial decides the relation. n2 + n = Θ(n2), log n = O(n), n2 = O(n3), n3 = 6 O(n2),

n3 = O(2n), 2n + n2 = Θ(2n).

Sometimes, we also use the small o notation. We say f (n) = o(g(n)) if f (n) = 0. n→∞ g(n) lim

n = o(n2).

Jiming Peng, AdvOL, CAS, McMaster

6

Math. Tools Two kinds of complexity: Worst-case Tw (n), average case Ta(n). The O notion can help us to compare the complexity of different algorithms. A Procedure: Sort(A[1 · · · n]) Input: an array A[1 · · · n]; Output: an array in nondecreasing order. for i := 1 to n − 1 do for j = i + 1 to n do if A[j] < A[i] then Swap(A[i], A[j]) endif endfor endfor end. Question: What is T (n)? T (n) =

n−1 X i=1

(n − i)

T (n) = T (n − 1) + (n − 1), T (1) = 0. Jiming Peng, AdvOL, CAS, McMaster

7

Mathematical Induction Let T be a theorem that we want to prove. Suppose that T includes a parameter n whose value can be any natural number. We prove the following two conditions: (1) T holds for n = 1; (2) For any n > 1, if T holds for n − 1, then T holds for n. Theorem: The sum of the first n natural numbers is n(n + 1)/2. Proof: Let us denote by S(n) the sum. First observe the theorem holds trivially for n = 1. Assume the theorem is true for n, says S(n) = n(n + 1)/2. It follows S(n + 1) = S(n) + n + 1 = (n + 1)(n + 2)/2. 2

Counting regions in the plane: Suppose a plane is cut by a set of lines in general position, which means no two lines are parallel and no three lines intersect at a common point.

Then one can show that the

number of regions in the plane formed by n lines in general position is n(n + 1)/2 + 1.

Jiming Peng, AdvOL, CAS, McMaster

8

Two coloring problem Sometimes the induction can be used to design an algorithm. Theorem: It is possible to color the regions formed by any number of lines in the plane with only two colors. Proof: We use the natural induction hypothesis. Induction Hypothesis: It is possible to color the regions formed by < n lines in the plane with only two colors. We verify first the trivial case n = 1. Then when a new line is added, we separate the region into two parts. Keep the colors in one side and reverse in another side.

Jiming Peng, AdvOL, CAS, McMaster

9

Euler’s formula Euler’s formula:Consider a connected planar map with V vertices, E edges and F faces. We count the outside region as one face. Theorem: The number V, E, F in an arbitrary connected planar map are related by the relation V + F = E + 2.

Proof: Double induction: E = V + F − 2 (two parameters). The induction proceeds first on the number of vertices and then on the number of faces. Consider first a map with only one face, thus such a map contains no cycle. A connected map without cycle is called a tree. For all trees, there holds V + 1 = E + 2.

Jiming Peng, AdvOL, CAS, McMaster

10

Proof of Euler’ Theorem First induction hypothesis: A tree with n vertices has n − 1 edges. The base case is trivial. Assume that trees with n vertices have n − 1 edges, and consider trees with n + 1 vertices. There must be at least one vertex v connected to only one edge. Otherwise, if all vertices are connected at least two edges, and if we traverse the tree along the edge, starting from any vertex, then we are guaranteed to return to a vertex already visited without getting stuck. This means there is a cycle in the tree, which is a contradiction. We can remove the vertex v together with the edge connected to it. The resulting map is still a tree but has one less vertex and one less edge, which implies the claim. Main induction hypothesis: Any planar map with n faces has E edges and V vertices such that V + n = E + 2. Consider a map with n + 1 faces. It must have a face f which is a neighbor of the outside face. Since f is a face, it is surrounded by a cycle. Removing one edge of this cycle will not disconnect the map. We remove one of the edges that separate f from the outside. We now have one less face and one less edge and the theorem follows. 2 Jiming Peng, AdvOL, CAS, McMaster

11

Summations Consider the summation S2(n) =

n X

i2 .

i=1

It is clear S2(n) ≤ n3. Suppose that S2(n) = an3 +bn2 +cn+d = P (n). Since P (0) = 0, we obtain d = 0. Moreover, using the induction P (n + 1) − P (n) = (n + 1)2 and compare the coefficients for n, n2 and n3, we can prove that a = 1/3, b = 1/2, c = 1/6. Pn An Alternative: Let S3(n) = i=1 i3. Thus, S3(n) =

n X i=1

3

(i − 1 + 1) =

n−1 X

(i + 1)3

i=0

= S3(n − 1) + 3S2(n − 1) + 3

n−1 X

i + n.

i=1

Since S3(n) − S3(n − 1) = n3 and S2(n) − S2(n − 1) = n2, we have S2(n) = (n3 − 3n(n − 1)/2 − n)/3 + n2 = n(n + 1)(2n + 1)/6.

Pn Exercise: F (n) = i=0 2i. Jiming Peng, AdvOL, CAS, McMaster

12

Recurrence Relations Definition: A recurrence is a way to define a function by an expression involve the same function. Fibonacci numbers: F (n) = F (n − 1) + F (n − 2), F (1) = F (2) = 1.

We guess that F (n) = an? Then an = an−1 + an−2 or a2 − a − 1 = 0. There exist two roots of this equation, √ √ a1 = (1 + 5)/2, a2 = (1 − 5)/2.

We can write the recurrence as c1(a1)n + c2(a2)n. We consider another example:

T (2n) ≤ 2T (n) + 2n − 1, T (2) = 1.

Typically, T (n) = O(f (n)). But, what is f (n)? f (n) = n2, f (n) = cn,

or f (n) = n log2 n?

How to identify a suitable f (n)? Jiming Peng, AdvOL, CAS, McMaster

13

Divide & Conquer:I Consider the general case T (n) ≤ 2T (⌊n/2⌋) + n − 1, T (2) = 1.

Note T (n) should be increasing. Suppose n = 2k for some integer k. We have T (n) = O (n log2 n). If n 6= 2k , then there must exist k such that 2k−1 ≤ n ≤ 2k ≤ 2n.

Therefore, we can still write T (n) = O (n log2 n). Traps Consider T (2n) ≤ 2T (n) + 2n − 1. A wrong proof: First T (2) ≤ O(2), hence T (2n) ≤ 2T (n) + 2n − 1 ≤ O(n) + 2n = O(n). A Math Trick: Let G(n) = T (n)/n, then we can write G(2n) ≤ G(n) + 1 − 1/2n ≤ G(n) + 1.

This implies

G(n) ≤ O (log2 n) .

Substituting it into T (n), we get the right relation! Jiming Peng, AdvOL, CAS, McMaster

14

Divide & Conquer:II Let T (n) = aT (n/b) + cnk . We assume b > 1, n = bm and T (1) = c. Thus we get T (n) = a(a(· · · T (n/bm)+c(n/bm−1)k )+· · ·)+cnk . That is m

T (n) = ca +ca

m−1 k

b +ca

m−2 2

mk

b k+· · ·+cb

= ca

m

m X

k

b /a .

i=1

There are three cases: (1) a > bk ;(2) a = bk ; (3) a < bk . We have Theorem The solution of the recurrence relation T (n) = aT (n/b) + cnk , where a and b are integer constants a ≥ 1, b ≥ 2, and c and k are positive constants, is     log a k; b  O n if a > b      k T (n) = O n log n if a = bk ;        O nk if a < bk . Jiming Peng, AdvOL, CAS, McMaster


i

15

Recurrence in Full History Definition: A full-history recurrence relation is one that depends on all the previous values of the function. First instance: T (n) = c +

n−1 X

T (i).

i=1

It follows readily T (n + 1) = 2T (n). Does it mean T (n + 1) = T (1)2n? The correct answer is T (n + 1) = (T (1) + c)2n−1! Another example: n−1

2X T (n) = n − 1 + T (i). n i=1

To estimate T (n), we rewrite the relation as T (n + 1) = (n + 2)T (n)/(n + 1) + 2n/(n + 1).

Let G(n) = T (n)/(n + 1), we obtain G(n + 1) ≤ G(n) + 2/(n + 1) ≤ ... ≤ 2H(n + 1),

where H(n) = 1 + 1/2 + 1/3 + · · · + 1/n is the Harmonic series. And H(n) = log n + γ + Jiming Peng, AdvOL, CAS, McMaster

16

O (1/n) where γ = 0.577 . . . is Euler’s constant. Hence T (n) ≤ O (n log n) .