Introduction

1. Algorithms?

2. Order

3. Analysis of Algorithm

4. Some Mathematical Background

Young Topic: Introduction 1

CS 530 Adv. Algo.
What is an algorithm?
Simple, unambiguous, mechanical procedure to
carry out some task.

Why algorithm instead of program?

1. writing an algorithm is simpler(we don’t need to
worry about the detailed implementation, or the
language syntax)

2. an algorithm is easier to read (if we write eg: an

C program to solve a problem, then the other
person cannot understand the idea of the problem
solving unless he/she understands C).
Young Topic: Introduction 2
CS 530 Adv. Algo.
How to represent an algorithm?

1. Give a description in your own language,

e.g. English, Spanish, …

2. pseudo code

3. Graphical

Young Topic: Introduction 3

CS 530 Adv. Algo.
Example – multiplying two positive integers A
and B

For example: 45*19

Usually:
45
19 (x

405
45 (+
855
Young Topic: Introduction 4
CS 530 Adv. Algo.
A different algorithm:

Multiplier Multiplicand Result

(A/2) (B*2) (pick numbers in column 2
when the corresponding
number under the multiplier
is odd)

45 19 19
22 38
11 76 76
5 152 152
2 304
1 608 608 (+
855

Young Topic: Introduction 5

CS 530 Adv. Algo.
An instance of a problem is a specific assignment
of values to the parameters. This algorithm can be
used for multiplying any two positive integers, we
say that (45, 19) is an instance of this problem.
Most problems have infinite collection of
instances. It’s ok to define the domain (i.e. the set
of instances) to be considered. And the algorithm
should work for all instances in that domain.
Although the above algorithm will not work if the
first operand is negative, this does not invalidate
the algorithm since (-45, 19) is not an instance of
the problem being considered.
Young Topic: Introduction 6
CS 530 Adv. Algo.
 Order:
Usually we use the frequency count to compare algorithms.
Consider the following 3 programs:

(a) (b) (c)

x←x+y for i ← 1 to n do for i ← 1 to n do
x←x+y for j ← 1 to n do
end x←x+y
end
end

The frequency count of stmt x ← x + y is 1, n, n2.

 no matter which machine we use to run these programs, we know
that the execution time of (b) is n times the execution time of (a).
Young Topic: Introduction 7
CS 530 Adv. Algo.
 Introduction to Worst, Average and
Best Case
Worst Case Analysis:

In the worst-case analysis, we calculate the upper limit of the

execution time of an algorithm. It is necessary to know the case
which causes the execution of the maximum number of operations.

Defines the input for which the algorithm takes more time or input
for which algorithm runs the slowest.

Young Topic: Introduction 8

CS 530 Adv. Algo.
Average Case Analysis:

In the average case analysis, we take all possible inputs and calculate
the computation time for all inputs. Add up all the calculated values ​
and divide the sum by the total number of entries.

Here we run the algorithm for any number of iterations then compute
running time for each trial sum it and divide by the number of trials
= (total running time)/(number of trials)

Assumes input is random.

Young Topic: Introduction 9

CS 530 Adv. Algo.
Best Case Analysis:

In the best case analysis, we calculate the lower bound of the

execution time of an algorithm. It is necessary to know the case
which causes the execution of the minimum number of operations.

Defines the input for which the algorithm takes less time or input for
which algorithm runs the fastest.

lower bound <= average time <= upper bound

Young Topic: Introduction 10

CS 530 Adv. Algo.
 Logarithms or log
A mathematical concept/expression that’s used a lot in Computer
Science and it’s the inverse (flip) of exponentials, and

they’re used to answer the question: How many times must one
“base” number be multiplied by itself to get some other particular
number or (what power you have to raise to, to get another
number)

or we can also define it as The power (or exponent) to which one

base number must be raised (multiplied by itself) to produce
another number.

Young Topic: Introduction 11

CS 530 Adv. Algo.
 log
Example:

How many times must a base of 20 be multiplied by itself to get

8,000? The answer is 3 (8000 = 20 × 20 × 20). So the logarithm
base 20 of 8,000 is 3.

It’s represented using a subscript (small number) to the lower right

of the base number. So the statement would be log20(8,000) = 3.

log20(400) is like asking “How many 20s do we multiply to get

400? which is 2(20 * 20). So log20(400) = 2

Young Topic: Introduction 12

CS 530 Adv. Algo.
 Big-O Notation:

Def f(n) = O(g(n)) if and only if  2 positive constants c and n0,

such that
|f(n)|  c  |g(n)|  n  n0.
So, g(n) actually is the upper bound of f(n).
c| g (n) |

| f ( n) |

n0
Figure 1. Illustrating “big O”
Young Topic: Introduction 13
CS 530 Adv. Algo.
Examples:
• Is 17 n2 – 5 = O(n2)?
 17n 2  5 17n 2 n 1
(c 17, n0 1)
 17n 2  5 O(n 2 )
• Is 35 n3 + 100 = O(n3)?
 35n 3  100 36n 3 n 5
(c 36, n0 5)
 35n 3  100 O(n 3 )
• Is 6  2n + n2 = O(2n)?
 6 2 n  n 2 7 2 n n 5
(c 7, n0 5)
 6 2 n  n 2 O(2 n )
Young Topic: Introduction 14
CS 530 Adv. Algo.
Complexity classes

f(n) n! 2n n3
n2

n log n

n (linear time)

log n

n
Figure 2. Growth rates of some important complexity classes
Young Topic: Introduction 15
CS 530 Adv. Algo.
 Assume that we have a machine that can execute
1,000,000 required operations per sec

Algorithm 1 Algorithm 2 Algorithm 3 Algorithm 4 Algorithm 5

Frequency 33n 6nlogn 13n2 3.4n3 2n

count
n=10 < 1 sec < 1 sec < 1 sec < 1 sec < 1 sec
n=10,000 < 1 sec 6 sec 22 min 39 days many many
centuries

Table 1. Execution time for algorithms with the

given time complexities

Young Topic: Introduction 16

CS 530 Adv. Algo.
Note:
log n
n(linear)
n log n polynomial time (easy or tractable)
n2
n3

2n
exponential time (hard or intractable)
n!

Young Topic: Introduction 17

CS 530 Adv. Algo.
 How do we know a given problem is easy?

Give a polynomial time algorithm for the problem

 Need to be good in
design of algorithms (CS530)
 Need to be good in
analysis of algorithms (CS530)

How do we know a given problem is hard?

Show that it is as hard as those well-known “hard”

problems.
 Need help from the
theory of NP Completeness (CS530)

Young Topic: Introduction 18

CS 530 Adv. Algo.
Whether your program is the best or not?
(Comparing algorithms)

The problem: Counting the number if 1’s in a n-bit string

algorithms:

1. c ← 0;
for i ← 1 to n do
if bi = 1 then c ← c+1;

Complexity: T(n) = O(n)

Young Topic: Introduction 19

CS 530 Adv. Algo.
2. Assume B = bnbn-1…b2b1
c ← 0;
while B ≠ 0 do
c ← c+1;
B ← B  (B –1 ); ( Note that  is “logical and” )

Complexity: T(n) = O( # of 1’s)

eg: B = 100011
c←1 100011 B
) 100010 B-1
c←2 100010 B’
) 100001 B’-1
c←3 100000 B’’
) 011111 B’’-1
000000 B’’’
Young Topic: Introduction 20
CS 530 Adv. Algo.
3. Can we do it in log n time?
B = 11010001
b8 b7 b6 b5 b4 b3 b2 b1

B 1 1 0 1 0 0 0 1
Odd 1 1 0 1
Shift even to right 1 0 0 0
B1 = Bodd + Beven 10 01 00 01
Odd 01 01
Shift even to right 10 00
B2 = Bodd + Beven 0011 0001

Odd 0001
Shift even to right 0011
B3 = Bodd + Beven 0100

Young Topic: Introduction 21

CS 530 Adv. Algo.
Idea:
4 11010001

3 1101 0001 1

==> T(n) = O(logn)

2 11 1 01 00 0 01 1

1 1 0 1 0 0 0 1
Note:
- The familiar machine that we used can only execute one
operation in each step  sequential machine.
-This stated algorithm requires the machine to have more than
one operation done in each step  parallel machine
Young Topic: Introduction 22
CS 530 Adv. Algo.
 Ω Notation
Def f (n) ( g (n)) iff  two positive constants c and n0,
such that
| f (n) | c| g (n) | n n0
So, g(n) is the lower bound of f(n).
| f ( n) |

c| g (n) |

n0
Figure 3. Illustrating Ω
Young Topic: Introduction 23
CS 530 Adv. Algo.
Examples:
•Is 3n  2 (n) ?
 3n  2 3 n n 1
(c 3, n0 1)
 3n  2 (n)
•Is 3n  2 (1) ?
 3n  2 1 1 n 1
(c 1, n0 1)
 3n  2 (1)

6 2 n  n 2 (n100 ) value of n0
•Is  6? 2 n  n 2 ? n100 n ?

n 2 100
When n is bigger, 6 faster
2 will grow
n 2 than
n n. (n you) can find n0 )
( Yes,100

Young Topic: Introduction 24

CS 530 Adv. Algo.
 Θ notation
Def f (n) ( g (n)) iff  three positive constants, c1, c2, n0 ,

c1 | g (n) | | f (n) | c 2 | g (n) | n n0 .

such that
c 2 | g (n) |

| f ( n) |

c1 | g (n) |

n0 Figure 4. Illustrating Θ
Young Topic: Introduction 25
CS 530 Adv. Algo.
Examples:

• Is 3n + 2 = (n)?
 3n 3n  2 4n n 2
(c1 3, c 2 4, n0 2)
 3n  2 (n)

• Is 3n + 2 = (n2)?
2
 3n  2 (n )
2
 3n  2 (n )

Young Topic: Introduction 26

CS 530 Adv. Algo.
• Is 6 2 n  n 2 (2 n )?
 6 2 n 6 2 n  n 2 7 2 n n 4
(c1 6, c 2 7, n0 4)
 6 2 n  n 2 (2 n )

• Is 4n 3  3n 2 (n 2 ) ?
 4n 3  3n 2 O(n 2 )
 4n 3  3n 2 (n 2 )

Young Topic: Introduction 27

CS 530 Adv. Algo.
 Property of Order

1) Transitive:
If f (n) O( g (n)) and g (n) O(h(nthen
)) f (n) O(h(n))

If f (n) ( g (n)) and g (n) (h(nthen

)) f (n) (h(n))

If f (n) ( g (n)) and g (n) (h(nthen

)) f (n) (h(n))

2) Reflexive:
f (n) O( f (n))
f (n) ( f (n))
f (n) ( f (n))

Young Topic: Introduction 28

CS 530 Adv. Algo.
3) Symmetric:

f (n) ( g (n)) g (n) ( f (n))

iff

f (n) O( g (n)) g (n) ( f (n))

iff

Young Topic: Introduction 29

CS 530 Adv. Algo.
 Analysis of Algorithms

a) Best Case, Worse Case Analysis

The problem:
Sort n keys in nondecreasing sequence.

Solving strategy:
Insertion sort – insert the ith item into a sorted list of
length (i – 1) by looking at numbers one at a time,  i
>1.
Example: sort 3,5,4,1
step 1 step 2 step 3 step 4
3 3 3 1
5 5 4 3
4 4 5 4
Young 1 1 Topic: Introduction
1 5 30
CS 530 Adv. Algo.
 Algorithm:

A(0) ← -maxint; // for efficient to stop the loop

for i ← 2 to n do
target ← A(i);
j ← i –1;
while (target < A(j))
A( j + 1) ← A(j);
j ← j –1;
A( j + 1) ← target;

Young Topic: Introduction 31

CS 530 Adv. Algo.
 Analysis:

Best Case performance is Θ(n) or Ω(n), but not

Ω(n2) since insertion sort runs in Θ(n) when
the input is sorted.

Worst Case performance is Θ(n2) or O(n2)

The running time of insertion sort is between Ω(n)

to O(n2)

The running time is bound to O(n2)

Young Topic: Introduction 32

CS 530 Adv. Algo.
b) Average Case Analysis

The problem:

Is the key x in the array S of n keys?

Solving strategy:

Sequential search

Young Topic: Introduction 33

CS 530 Adv. Algo.
Algorithm:

Procedure search ( n, S, x, location) // n is total # of keys,

S is an array,
x is the key,
location is output
parameter
begin
location ← 1;
while (location ≤ n) and (S(location) ≠ x)
location ++;
if location > n location ← 0;
end;

Young Topic: Introduction 34

CS 530 Adv. Algo.
Average Case Analysis:
1
Assume Probability prob ( x k )  1 k n
th

n
1) When x = kth, # of key comparisons = k

1 1 1 1 n
 A(n)  1  2    n  ( k )
n n n n k 1
1 n(n  1) n  1
  
n 2 2

about half array is searched.

Young Topic: Introduction 35

CS 530 Adv. Algo.
2) When may not be in the array
th1
Assume prob (x in array) = p,  prob ( x k )  p 
n
prob (x not in array) = 1 – p, and it takes
n comparisons to know that is not in the array
p n
 A(n)   k  (1  p ) n
n k 1
p n(n  1)
   (1  p ) n
n 2
p p
n (1  ) 
2 2
Young Topic: Introduction 36
CS 530 Adv. Algo.
 n 1
If p = 1, A(n)  (as calculated in case (1))
2

1 3 1
If p  , A(n)  n  (about ¾ of the array is
2 4 4
searched)

Young Topic: Introduction 37

CS 530 Adv. Algo.
 Design of Algorithms

a) Divide-and-Conquer

b) Greedy

c) Dynamic Programming

d) Backtracking & Branch-and-Bound

Young Topic: Introduction 38

CS 530 Adv. Algo.
 Some mathematical background

Definition. Logb x = y if b y = x b > 1

1) Logb is a strictly increasing function,

if x1 < x2 then Logb x1 < Logb x2 .

2) Logb is a one-to-one function,

if Logb x1 = Logb x2 then x1 = x2 .

3) Logb 1 = 0 b

4) Logb xa = a  Logb x

5) Logb(x1  x2) = Logb x1 +Topic:

Young
LogIntroduction
b x2 39
CS 530 Adv. Algo.
6) x1Logb x2 = x2Logb x1
Log b2 x
Log b1 x 
7) to convert from one base to another, Log b2 b1
n
n(n  1)
8) sum of consecutive integers
i 
i 1 2
k 1
k
a 1
9) geometric sums 
i 0
a i

a 1

10) Suppose f is a continuous, decreasing function, a, b are integers,

b 1 b b

then f ( x)dx  f (i)  f ( x)dx

a i a a 1

Young Topic: Introduction 40

CS 530 Adv. Algo.
11) Suppose f is a continuous, decreasing function, a, b are integers,

b b b 1
then
f ( x)dx  f (i)  f ( x)dx
a 1 i a a

b
12) 1

a
x
dx  Log e b  Log e a

Note:
Log2 = Lg
Loge = Ln

Young Topic: Introduction 41

CS 530 Adv. Algo.