Week2-6

Outline • • • • • •

Data Structures – Week #2 Algorithm Analysis & Recursion

Performance of Algorithms Performance Prediction (Order of Algorithms) Examples Exercises Recursion Recurrences

November 11, 2005

Borahan Tümer, Ph.D.

2

Performance of Algorithms

Performance Assessment

• Algorithm is a finite sequence of instructions that the computer follows to solve a problem. • Algorithms solving the same problem may perform differently. Depending on resource requirements an algorithm may be feasible or not. To find out whether or not an algorithm is usable or relatively better than another one solving the same problem, its resource requirements should be determined. • The process of determining the resources of an algorithm is called algorithm analysis. • Two essential resources, hence, performance criteria of algorithms are

• The actual execution time of an algorithm is hard to assess if one does not know the intimate details of the computer architecture, the operating system, the compiler, the quality of the program and the other factors. • Execution time may be found for a given algorithm using some special performance programs called benchmarks. • Second alternative for performance assessment is to find the growth rate of an algorithm. • The execution time is a function of the input size such as the number of elements in an array, the number of records in a file etc...

– execution time – memory space used. November 11, 2005

Borahan Tümer, Ph.D.

3

November 11, 2005

Borahan Tümer, Ph.D.

4

Assessment Tools

“Big O” Notation by words

• We can use the concept “the growth rate or order of an algorithm” to assess both criteria. However, our main concern will be the execution time. • Notation for the “order of” concept • Mathematically expressed, the “order of” or “Big O” (O()) concept is as follows: • Let f: N->R* be an arbitrary function. • O(f(n)) = {t: N->R* | (c  R+)(n0  N)(n t n0) [t(n)d cf(n)]},

• Expressed by words; O(f(n)) is the set of all functions t(n) mapping (->) integers (N) to nonnegative real numbers (R*) such that (|) there exists a positive real constant c (c  R+) and there exists an integer constant n0 (n0  N) such that for all values of n greater than or equal to the constant (n t n0), the function values of t(n) are less than or equal to the function values of f(n) multiplied by the constant c (t(n)d cf(n)). • In other words, O(f(n)) is the set of all functions t(n) bounded above by a positive real multiple of f(n), provided n is sufficiently large (greater than n0).

– where R* is the set of nonnegative real numbers and R+ is the set of strictly positive real numbers (excluding 0). November 11, 2005

Borahan Tümer, Ph.D.

5

November 11, 2005

Borahan Tümer, Ph.D.

6

Execution time of various structures

Execution time of various structures

• Simple Statement

• O(f1(n)+}+fs(n))=O(max(f1(n),},fs(n))) ??? • Proof: t(n) O(f1(n)+}+fs(n)) Ÿ t(n)d c[f1(n)+…+fs(n)] d sc*max [f1(n),…, fs(n)],sc another constant. Ÿ t(n) O(max(f1(n),},fs(n))) Hence, hypothesis follows.

O(1), executed within a constant amount of time irresponsive to any change in input size.

• Decision (if) structure if (condition) f(n) else g(n) O(if structure)=max(O(f(n)),O(g(n)) • Sequence of Simple Statements O(1), since O(f1(n)+}+fs(n))=O(max(f1(n),},fs(n))) November 11, 2005

Borahan Tümer, Ph.D.

7

November 11, 2005

Execution Time of Loop Structures

Borahan Tümer, Ph.D.

8

Examples Find the execution time t(n) in terms of n!

• Loop structures’ execution time depends upon whether or not their index bounds are related to the input size. • Assume n is the number of input records • for (i=0; i<=n; i++) {statement block}, O(?) • for (i=0; i<=m; i++) {statement block}, O(?)

for (i=0; i<=n; i++) for (j=0; j<=n; j++) statement block; for (i=0; i<=n; i++) for (j=0; j<=i; j++) statement block; for (i=0; i<=n; i++) for (j=0; j<=n; j*=2) statement block;

November 11, 2005

Borahan Tümer, Ph.D.

9

November 11, 2005

Borahan Tümer, Ph.D.

10

Exercises

Recursion

Find the number of times the statement block is executed! for (i=0; i<=n; i++) for (j=0; j<=i; j*=2) statement block;

Definition: Recursion is a mathematical concept referring to programs or functions calling or using itself.

for (i=0; i<=n; i*3) for (j=0; j<=n; j*=2) statement block;

A recursive function is a functional piece of code that invokes or calls itself.

November 11, 2005

Borahan Tümer, Ph.D.

11

November 11, 2005

Borahan Tümer, Ph.D.

12

Recursion

Recursion… cont’d

Concept: • A recursive function divides the problem into two conceptual pieces: – a piece that the function knows how to solve (base case), – a piece that is very similar to the original problem, hence still unknown how to solve by the function (call(s) of the function to itself). November 11, 2005

Borahan Tümer, Ph.D.

13

Recursion Examples

Borahan Tümer, Ph.D.

• To make the recursion feasible, the latter piece must be slightly simpler.

November 11, 2005

Borahan Tümer, Ph.D.

14

Towers of Hanoi… cont’d Algorithm: Hanoi(n,i,j) // moves n smallest rings from rod i to rod j F0A0 if (n > 0) { //moves top n-1 rings to intermediary rod (6-i-j) F0A2 Hanoi(n-1,i,6-i-j); //moves the bottom (nth largest) ring to rod j F0A5 move i to j // moves n-1 rings at rod 6-i-j to destination rod j F0A8 Hanoi(n-1,6-i-j,j); F0AB }

• Towers of Hanoi • Story: According to the legend, the life on the world will end when priests in a Far-Eastern temple move 64 disks stacked on a peg in an decreasing order in size to another peg. They are allowed to move one stack at a time and a larger disk can never be placed over a smaller one. November 11, 2005

• Base case: the simplest version of the problem that is not further reducable. The function actually knows how to solve this version of the problem.

15

Function Invocation in MM

November 11, 2005

Borahan Tümer, Ph.D.

16

Function Invocation (Call) in MM • Code and data are both in MM. • Hanoi function is called by the instruction at MM cell C0D5 with arguments (4,1,3). • Program counter is a register in ȝP that holds MM address of next instruction to execute. • If current instruction is a function call, the serial flow of execution is interrupted.

November 11, 2005

Borahan Tümer, Ph.D.

17

November 11, 2005

Borahan Tümer, Ph.D.

18

Function Call in MM… cont’d

Towers of Hanoi… cont’d Example: Hanoi(4,i,j)

• Following problems arise: – how to keep the return address from the function called (Hanoi) back to the caller function (C0D8 at main and both F0A5 and F0AB at Hanoi); – how to store the values of variables local to caller function.

413 312 213 112 013

323 221 123 021

2o3

1o2

013

032

1o3

2o1

123 021

131 032

3o1

2o3

• Both problems are solved by keeping the return address and local variables’ values in a portion of the main memory called system stack. • Another register called Stack Pointer points to the address pushed most recently to system stack. Return addresses are retrieved from system stack in a last-infirst-out (LIFO) fashion. We will see stacks later.

021

013

1o2

2o3

232 131 032

213 112 013

1o2

3o1

032

021

3o2

1o3

112 013

123 021

1o2

2o3

032

013

1o3 November 11, 2005

Borahan Tümer, Ph.D.

19

November 11, 2005

Towers of Hanoi… cont’d o

o

o

o

Borahan Tümer, Ph.D.

20

Recursion Examples o

• Fibonacci Series – tn= tn-1 + tn-2; t0=0; t1=1

o

o

o

o

o

o

o

o

o

o

o

o

o

November 11, 2005

Borahan Tümer, Ph.D.

21

Fibonacci Series… cont’d

• Algorithm long int fib(n) { if (n==0 || n==1) return n; else return fib(n-1)+fib(n-2); } November 11, 2005

Borahan Tümer, Ph.D.

22

Fibonacci Series… cont’d

• Tree of recursive function calls for fib(5) • Any problems???

• Redundant function calls slow the execution down. • A lookup table used to store the fibonacci values already computed saves redundant function executions and speeds up the process. • Homework: Write fib(n) with a lookup table!

November 11, 2005

Borahan Tümer, Ph.D.

23

November 11, 2005

Borahan Tümer, Ph.D.

24

Homogeneous Recurrences

Recurrences or Difference Equations

We are looking for solutions of the form: tn = xn Then, we can write the recurrence as a0 xn + a1xn-1+ … + ak xn-k = 0 th • This k degree equation is the characteristic equation (CE) of the recurrence.

• Homogeneous Recurrences • Consider a0 tn + a1tn-1 + … + ak tn-k = 0. • The recurrence – contains ti values which we are looking for. – is a linear recurrence (i.e., ti values appear alone, no powered values, divisions or products) – contains constant coefficients (i.e., ai). – is homogeneous (i.e., RHS of equation is 0).

November 11, 2005

Borahan Tümer, Ph.D.

25

November 11, 2005

Borahan Tümer, Ph.D.

26

Homogeneous Recurrences

Inhomogeneous Recurrences

If ri, i=1,…, k, are k distinct roots of a0 xk + a1 xk-1+ … + ak = 0, then

Consider • a0 tn + a1tn-1 + … + ak tn-k = bn p(n) • where b is a constant; and p(n) is a polynomial in n of degree d.

k

¦c r

tn

n

i i

i 1

If ri, i=1,…, k, is a single root of multiplicity k, then k

tn

¦c n i

i 1 n

r

i 1

November 11, 2005

Borahan Tümer, Ph.D.

27

November 11, 2005

Inhomogeneous Recurrences

Borahan Tümer, Ph.D.

28

Generalized Solution for Recurrences

Generalized Solution for Recurrences Consider a general equation of the form (a0 tn + a1tn-1 + … + ak tn-k ) = b1n p1(n) + b2n p2(n) + … We are looking for solutions of the form: tn = xn Then, we can write the recurrence as (a0 xk + a1 xk-1+ … + ak ) (x-b1) d1+1 (x-b2) d2+1 …= 0; where di is the polynomial degree of polynomial pi(n). This is the characteristic equation (CE) of the recurrence. November 11, 2005

Borahan Tümer, Ph.D.

If ri, i=1,…, k, are k distinct roots of (a0 xk + a1 xk-1+ … + ak)=0 k

tn

¦c r

i i

n

 ck 1b1n  ck  2 nb1n  /  ck 1 d1 n d1 1b1n  ck  2 d1 b2n  ck 3 d1 nb2n  /  ck  2 d1  d 2 n d 2 1b2n

i 1

29

November 11, 2005

Borahan Tümer, Ph.D.

30

Examples

Examples

Homogeneous Recurrences Example 1. tn + 5tn-1 + 4 tn-2 = 0; sol’ns of the form tn = xn xn + 5xn-1+ 4xn-2 = 0; n-2 trivial sol’ns (x2+5x+4) = 0; characteristic equation (CE) x1=-1; x2=-4; nontrivial sol’ns Ÿ tn = c1(-1)n+ c2(-4)n ; general sol’n

November 11, 2005

Borahan Tümer, Ph.D.

Homogeneous Recurrence Example 2. tn-6 tn-1+12tn-2-8tn-3=0; tn = xn xn-6xn-1+12xn-2-8xn-3= 0; n-3 trivial sol’ns CE: (x3-6x2+12x-8) = (x-2)3= 0; by polynomial division x1= x2= x3 = 2; roots not distinct!!! Ÿtn = c12n+ c2n2n + c3n22n; general sol’n 31

November 11, 2005

Borahan Tümer, Ph.D.

Examples

Examples

Homogeneous Recurrence Example 3. tn = tn-1+ tn-2; Fibonacci Series xn-xn-1-xn-2 = 0; Ÿ CE: x2-x-1 = 0; 1 r 5 ; distinct roots!!! x1, 2 2

Ÿ tn

n

§1 5 · §1 5 · ¸  c2 ¨ ¸ c1 ¨¨ ¸ ¨ 2 ¸ © 2 ¹ © ¹

Example 3… cont’d We use as many ti values as ci 0

t0

§1 5 · §1 5 · ¸  c2 ¨ ¸ 0 c1 ¨¨ ¸ ¨ 2 ¸ © 2 ¹ © ¹

t1

§1 5 · §1 5 · ¸ ¸  c2 ¨ 1 c1 ¨¨ ¸ ¨ 2 ¸ ¹ © © 2 ¹

n

1

; general sol’n!! We find coefficients ci using initial values t0 and t1 of Fibonacci series on the next slide!!!

Borahan Tümer, Ph.D.

n

33

0 Ÿ c1

 c2

§1 5 · §1 5 · ¸ ¸  c1 ¨ c1 ¨¨ ¸ ¨ 2 ¸ Ÿ c1 ¹ © © 2 ¹

1 , c2 5



1 5

November 11, 2005

n

Borahan Tümer, Ph.D.

34

Examples Example 4.

Example 3… cont’d What do n and tn represent?

tn = 2tn-1 - 2tn-2; n t 2; t0 = 0; t1 = 1; CE: x2-2x+2 = 0; Complex roots: x1,2=1ri As in differential equations, we represent the complex roots as a vector in polar coordinates by a combination of a real radius r and a complex argument T: z=r*eT i; Here, 1+i=—2 * e(S/4)i 1-i=—2 * e(-S/4)i

n is the location and tn the value of any Fibonacci number in the series.

What is the meaning of tn in recursive function fib(n) on page 22 ? tn is the number of times the condition in the if structure (chosen as a barometer) is checked in fib(n).

Borahan Tümer, Ph.D.

c1  c2

1 §1 5 · 1 §1 5 · ¨ ¸  ¨ ¸ 5 ¨© 2 ¸¹ 5 ¨© 2 ¸¹

Examples

November 11, 2005

1

0

Check it out using t2!!! Ÿ tn

November 11, 2005

32

35

November 11, 2005

Borahan Tümer, Ph.D.

36

Examples

Examples

Example 4… cont’d Solution: tn = c1 (2)n/2 e(nS/4)i + c2 (2)n/2 e(-nS/4)i;

Inhomogeneous Recurrences Example 1. (From Example 3) We would like to know how many times fib(n) on page 22 is executed in terms of n. To find out: 1. choose a barometer in fib(n); 2. devise a formula to count up the number of times the barometer is excuted.

From initial values t0 = 0, t1 = 1, tn = 2n/2 sin(nS/4); (prove that!!!)

November 11, 2005

Borahan Tümer, Ph.D.

37

November 11, 2005

Borahan Tümer, Ph.D.

Examples

Examples

Example 1… cont’d In fib(n), the only statement is the if statement. Hence, if condition is chosen as the barometer. Suppose fib(n) takes tn time units to execute, where the barometer takes one time unit and the function calls fib(n-1) and fib(n-2), tn-1 and tn-2, respectively. Hence, the recurrence to solve is tn = tn-1 + tn-2 + 1 November 11, 2005

Borahan Tümer, Ph.D.

Example 1… cont’d tn - tn-1 - tn-2 = 1; inhomogeneous recurrence The homogeneous part comes directly from Fibonacci Series example on page 33. RHS of recurrence is 1 which can be expressed as 1nx0. Then, from the equation on page 29, CE: (x2-x-1)(x-1) = 0; from page 30, n

tn 39

n

§1 5 · §1 5 · n ¸  c2 ¨ ¸ c1 ¨¨ ¸ ¨ 2 ¸  c31 © 2 ¹ © ¹

November 11, 2005

Borahan Tümer, Ph.D.

Examples tn

Example 1… cont’d n

§1 5 · §1 5 · ¸  c2 ¨ ¸ c1 ¨¨ ¸ ¨ 2 ¸  c3 © 2 ¹ © ¹

n

tn

Now, we have to find c1,…,c3. Initial values: for both n=0 and n=1, if condition is checked once and no recursive calls are done. For n=2, if condition is checked once and recursive calls fib(1) and fib(0) are done. Ÿ t0 = t1 = 1 and t2 = t0 + t1 + 1 = 3. November 11, 2005

40

Examples

Example 1… cont’d n

38

Borahan Tümer, Ph.D.

c1

n

§ 1 5 · §1 5 · ¸  c2 ¨ ¸ c1 ¨¨ ¸ ¨ 2 ¸  c3 ; t0 © 2 ¹ © ¹ 5 1 ; c2 5

5 1 ; c3 5 n

tn

t1 1, t 2

3

1 n

ª 5  1º § 1  5 · ª 5  1º § 1  5 · ¸  1; ¸ « »¨¨ « »¨¨ ¸ ¸ ¬ 5 ¼© 2 ¹ ¬ 5 ¼© 2 ¹

Here, tn provides the number of times the barometer is executed in terms of n. Practically, this number also gives the number of times fib(n) is called. 41

November 11, 2005

Borahan Tümer, Ph.D.

42