Lecture 1 Advanced Analysis of Algorithms

Mathematical Foundations

Click to edit Master subtitle style Dr. Sohail Iqbal

11

Outline

Growth of functions Summations and Recursions Sets, Relations, Functions, Graphs Counting and Probability

22

Introduction

Performance comparison of two algorithm for sorting n integers: Algorithm A : n2 basic operations Algorithm B : 100 * nlogn+ 8 operations

Which algorithm is better???

33

For n= 100 integers

.
x 00 0 00 . 0 00 . 0 00 . 0 00 . 0 00 . 0 0 n0 00 0 *nlog(n)+0
0

No of operations

0 0

0 0

0 0

0 0

0 0 n

0 0

0 0

0 0

0 0

00 0

44

For n = 1000 integers

.
x 00 0 0 0 0 0 0 0 0 0 0 0 0 0 n0 00 0 *nlog(n)+0
0

No of operations

overtake at k = 650

00 0

00 0

00 0

00 0

00 0 n

00 0

00 0

00 0

00 0

00 00

55

For n = 10,000
.
x 00 0 0 0 0 0 0 0 0 0 0 0 0 0 n0 00 0 *nlog(n)+0
0

No of operations

00 00

00 00

00 00

00 00

00 00 n

00 00

00 00

00 00

00 00

000 00

66

Discussion

For all the sufficiently large values (k>650), algorithm B is performing better. Algorithm A : n2 basic operations Algorithm B : 100 * nlogn+ 8 operations Growth rate of algorithm B is slower than that of algorithm A. This leads to the idea of Big-O.
77

Big-O Notation

Definition: Let f and g be functions from the set of integers or the set of real numbers to the set of real numbers. We say that f(x) is O(g(x)), if there are constants C and k such that
f (x) C g(x) , whenever x > k

88

How to show

To show f (x) is O(g(x)): Find one pair (C, k) such that

f (x) C g(x) , whenever x > k

Note: This pair (C, k) is not unique. Hint: Select C and then find k.

99

Big- Notation

Definition: Let f and g be functions from the set of integers or the set of real numbers to the set of real numbers. We say that f(x) is (g(x)), if there are constants C and k such that
f (x) C g(x) , whenever x > k

1010

Big- notation

Definition: Let f and g be functions from the set of integers or the set of real numbers to the set of real numbers. We say that f(x) is Big- of (g(x)) if

f(x) is O(g(x)) f(x) is (g(x))

1111

Recursive Definition (Recursions)

1212

A recursively defined picture

1313

Recursions

A function or sequence is defined recursively, if

The value of a0 is given The value of an+1 is given in terms of an .

Example: The sequence can be n defined recursively as: an = 0

a0 = 0 an +0 = 0 an ,
1414

Recursive definition

To define a function with the set of nonnegative integers as its domain,

Specify the value of the function at zero 2. Give a rule for finding its value as an integer from its values at smaller integers. Such definitions are called recursive or inductive definitions.
1.

1515

Example

Suppose that f is defined recursively by f(0)=3 f(n+1)=2*f(n)+3 Find f(1), f(2), f(3), and f(5). Note: An inductive definition of a factorial is F(n+1)=(n+1)F(n), where F(0)=1
1616

Recursive definition of summation

Give the recursive definition of

0

k=0

ak

The first part of the recursive definition is

k=0

ak = a0

the second part is

n ak = ak + an+0 k=0 k=0

n +0

1717

Fibonacci numbers

The Fibonacci numbers f0, f1, f2, are defined by the equations:
f0 = 0 f0 = 0 and fn = fn- 0+ fn- 0 , ,

Find the Fibonacci sequence! What are the properties of this sequence?

1818

Recursive algorithms

An algorithm is recursive if it solves a problem by reducing it to an instance of same problem with smaller input. Note: Many algorithms such as algorithms for finding the GCD or computing the nth power can be re-written as a recursive algorithms.
1919

A recursive algorithm for computing an procedure power(a, n) if n = 0, then power(a, n) : = 1 else power(a, n) : = a* power(a, n-1) Note: a: non-zero real number; b: non-negative integer;

2020

A recursive algorithm for computing gcd(a,b)

procedure gcd(a, b) if a = 0, then gcd(a, b) : = b else gcd(a, b) : = gcd(b mod a, a) Note: a and b are non-negative integers; a<b Example: gcd(24, 40)
2121

A recursive binary search algorithm

procedure binary search(x, i, j ) m:= floor{(i + j ) /2} if x = am then location:=m else if (x < am and i < m) then binary search (x, i, m-1) else if (x > am and j > m) then binary search (x, m+1, j) else location: = 0
2222

Counting

The basics of counting The Pigeon hole principle Permutations Combinations

2323

The Sum Rule

If a first task can be done in m ways and a second task in n ways, and if these tasks cannot be done at the same time, then there are m + n ways to do either task.

2424

Example

A student can choose a computer project from one of the three lists. The three lists contain 23, 15, and 19 possible projects, respectively. How many projects are there to choose from?

2525

Example of code
What is the values of k after the following code has been executed?
k := 0 for i0:= 0 n0 to k := k + 0 e nd for i0 := 0 n0 to k := k + 0 e nd .... for im := 0 nm to k := k + 0 e nd
2626

The Product Rule

Suppose a procedure can be broken down into two tasks. If there are m ways to do the first task and n ways to do the second task after the first task has been done, then there are mn ways to do the procedure.

2727

Example

The chairs of an auditorium are to be labeled with a letter and a positive integer not exceeding 100. What is the largest number of chairs that can be labeled differently?

2828

Example

How many different license plates are available if each plate contains a sequence of two letters followed by four digits?

2929

Example of code
What is the values of k after the following code has been executed?
k := 0 for i0:= 0 n0 to k := k + 0 for i0 := 0 n0 to k := k + 0 .... for im := 0 nm to k := k + 0 e , e ,..., e nd nd nd
3030

The Pigeonhole Principle

Theorem: If k +1 or more objects are placed in k boxes, then there is at least one box containing two or more of the objects. Proof: Suppose that none of the k boxes contains more than one object. Then the total number of objects would be at most k. This is a contradiction, since there are at least k +1 objects.
3131

Examples

Among any group of 367 people, there must be at least two with the same birthday, because there are only 366 possible birthdays. How many students must be in a class to guarantee that at least two students have the same zodiac sign?

3232

Generalized Pigeonhole Principle

Theorem: If N objects are placed into k boxes, then there is at least one box containing at least Ceiling(N/k) objects. Proof: Suppose that none of the boxes contains more that Ceiling(N/k)-1 objects. Then the total number of objects are:
k ( / k - 0 < k(((N / k) + 0- 0 = N N ) ) hence proved. ) a contradiction,
3333

Example

Among 100 people there are at least how many who were born in the same month?

3434

Permutations

A permutation of a set of distinct objects is an ordered arrangement of these objects. If a set contains n objects, and we are interested in the ordered arrangement of r objects, then this is called r-permutation, denoted by P(n, r).
n! P (n, r ) = Pr = (n - r )!
n
3535

Example

How many ways are there to shelve 4 books out of 10 distinct books?

3636

Combinations

A combination of a set of distinct objects is an un-ordered arrangement of these objects. If a set contains n objects, and we are interested in the un-ordered arrangement of r objects, then this is called r-combination, denoted by C(n, r).
n! C (n, r ) = C r = r !(n - r )!
n
3737

Example

How many ways are there to select a team of 11 cricket players from a group of 14 players?

3838