Transcript Algorithms Design and Analysis Ch1: Analysis Basics

Data Structures and Algorithms
Introduction to
Algorithms
M. B. Fayek
CUFE 2006
Agenda
1.
2.
3.
4.
5.
Introduction to Algorithms
Algorithm Design Basics
Time Complexity of an Algorithm
Analysis using Asymptotic Notation
Basic Efficiency Classes
1. Introduction to Algorithms

Why study Algorithms?
Heart of computer
 Promote analytical skills
 Donald Knuth:
“ A person does not understand something until
after teaching it to someone else.
Actually: A person does not understand something
until after he teaches it to a ……COMPUTER!”

1. Introduction to Algorithms


What is an algorithm?
“A sequence of unambiguous instructions for
solving a problem, i.e., for obtaining a required
output for any legitimate input in a finite
amount of time.”
1. Introduction to Algorithms







Algorithms are all around us in everyday life.
In the recipe of a cook book.
In assembling a toy.
In setting the table.
In preparing a cup of tea.
In calling your friend on the phone.
…. There are countless examples!
Agenda
1.
2.
3.
4.
5.
Introduction to Algorithms
Algorithm Design Basics
Time Complexity of an Algorithm
Analysis using Asymptotic Notation
Basic Efficiency Classes
2. Algorithm Design Basics

Guidelines for Algorithm Designing and
Analysis:
1.
2.
3.
4.
5.
6.
Understand the Problem (requirement
analysis)
Select Data structure
Write Pseudo Code
Analyze Performance
Implement using suitable programming
language
Test to resolve syntax and logic errors
2. Algorithm Design Basics

Guidelines for Algorithm Designing and
Analysis:
1.



Understand the Problem (requirement
analysis)
Gather data
Ask users
Carefully review any written requirements
2. Algorithm Design Basics

Guidelines for Algorithm Designing and
Analysis:
2.


Select Data structure:
To verify the appropriateness of the selected
data structure:
Judge how well your data structure responds
to user requirements (updates, questions)
Modify design as necessary
2. Algorithm Design Basics

Guidelines for Algorithm Designing and
Analysis:
3.


Write Pseudo Code
Use pseudo code or flow chart
level of details of the pseudo code may vary
2. Algorithm Design Basics

Guidelines for Algorithm Designing and
Analysis:
4.




Analyze Performance
Determine the feasibility of solution w.r.t.
memory requirements, performance
constraints … etc.
Manually review and validate pseudo code
Analyze the complexity of the algorithm using
the big O notation to determine the
complexity w.r.t. to time and storage.
Other criteria include: Clarity, Maintainability,
Portability
2. Algorithm Design Basics

Guidelines for Algorithm Designing and
Analysis:
5.

Implement using suitable programming
language:
Is rather direct provided a good pseudo code
is written, however erroneous mapping may
occur!
2. Algorithm Design Basics

Guidelines for Algorithm Designing and
Analysis:
6.


Test to resolve syntax and logic errors.
Testing is divided into 2 main parts:
Trying to break the function of the program by
entering unexpected data.
Debugging: It is concerned with finding out what
is what caused the program to function in
incorrectly.
Agenda
1.
2.
3.
4.
5.
Introduction to Algorithms
Algorithm Design Basics
Time Complexity of an Algorithm
Analysis using Asymptotic Notation
Basic Efficiency Classes
3. Time Complexity of an Algorithm



Time complexity is a main issue in evaluating
an algorithm.
It reflects how the algorithm responds to
the increase in data size (n) it handles, by
measuring the corresponding increase in
number of instructions to be performed.
Time complexity is meant to classify
algorithms into categories.
3. Time Complexity of an Algorithm

Steps to determine time complexity:
1.
Identify basic operations used for evaluating
complexity.
Usually, loops and nested loops are the significant
parts of a program.
One iteration of the loop is considered as a unit. It is
then important to determine the order of
magnitude of run time involved based on the
number of iterations.
Parts concerned with initializations and reporting
summary results are of secondary importance.
2.
3.
4.
Example 1
Example1: count number of different chars in a file:
// Input: string of characters
// Output: array of 256 integers containing the count of the 256
chars
Bookkeeping!
For all 256 char do
assign zero to counter
end for
while there are more chars do
get next char
increment count for this char
end while
257 assignment
+ 256 increment
+ 257 bound check
N+1 Eof check
+ N count increment
Example 1
Total =
257 assign + 256 Inc + 258 check
(bookkeeping)
+ N Inc + N+1 check



(integral)
Consider basic operation BOP = 1 Inc + 1 check
for N= 500, integral BOP ≈ 500
bookkeeping ≈ 50 %
For N =10000, BOP ≈ 10000
bookkeeping = 7 %
Time grows linearly with n !
Example 2
Summing each of the rows of an N x N twodimensional array A, storing row sums in a
one-dimensional array Sum and the overall in
GrandTotal.
// Input: 2-dimensional array A
// Output: 1- dimensional array Sum that
contains the sum of 1st, 2nd,… row in 1st, 2nd,
… element and GrandTotal that contains the
total sum

Example 2

First Algorithm :
► complexity = n2 !
GrandTotal = 0
For k = 1 to N do
Basic Operation
Sum [K] = 0
For J = 1 to N do
Sum [K] = Sum [K] + A [K,J]
GrandTotal = GrandTotal + A [K,J]
EndFor
EndFor
Example 2
Second Algorithm :
2
►
complexity
=
n
GrandTotal = 0
For k = 1 to N do
Basic Operation 1
Sum [K] = 0
For J = 1 to N do
Basic
Operation 2
Sum [K] = Sum [K] + A [K,J]
EndFor
GrandTotal = GrandTotal + A [K,J]
EndFor

► complexity = n
Example 2
Total complexity= n2 + n
Hence Total Complexity mainly depends on n2

►Note however that:
 In the first approach the basic operation
includes 2 additions
 In the second approach each basic operation
includes 1 addition
 Hence, BOTH approaches are of order n2,
however, the second is better!
…. Why?
Agenda
1.
2.
3.
4.
5.
Introduction to Algorithms
Algorithm Design Basics
Time Complexity of an Algorithm
Analysis using Asymptotic Notation
Basic Efficiency Classes
4. Analysis using Asymptotic Notation

Big Oh:
 If
 Then
g  ( f )
there exists c such that
g (n)  cf (n)
4. Analysis using Asymptotic Notation

Find Big Oh
g  ( f )
by finding f(n) such that
g ( n)
lim
c
n  f ( n )
for some real value
cR
*
4. Analysis using Asymptotic Notation
A Useful Property:
 If

t1 (n)  O( g1 (n))
and
t 2 (n)  O( g 2 (n))
Then
t 2 (n)  t 2 (n)  O(max{g1 (n), g 2 (n)})
Agenda
1.
2.
3.
4.
5.
Introduction to Algorithms
Algorithm Design Basics
Time Complexity of an Algorithm
Analysis using Asymptotic Notation
Basic Efficiency Classes
5. Basic Efficiency Classes

Common complexities (ordered in
ascending order) are:

log n
n
n log n
n2
n3
2n





Complexity
5. Basic Efficiency Classes

Values of important asymptotic functions
n
log2 n
n
n log2 n
n2
n3
2n
n!
Example 1
Find the number of binary digits in the binary
representation of a number
// input: A is a positive number
// output: number of bin digits that represent A
count <-- 1
while n > 1 do
count <-- count + 1
n <-- n/2
return count

Example 2: Element Uniqueness
Element Uniqueness Problem:
//Check whether all elements of array are unique
// input: array A[0, .. n-1]
// output true or false
for i <-- 0 to n-2 do
for j <-- i+1 to n-1 do
if A[i] = A[j] return false
return true

► Efficiency does not depend on n only!
There is a best, worst and average case
efficiency!
…… When do those cases occur?
Example 3: Fibonacci Numbers
It is a series described by:
Fi = Fi-1+ Fi-2 and F(0) =0, F(1) =1
// Input: A nonnegative integer n
// Output: The nth Fibonacci number
F[0] <-- 0; F[1] <-- 1
for i <-- 2 to n do
F[i] <-- F[i-1] + F[i-2]
return F[n]
►EXTRA ARRAY STORAGE, necessary?

Exercises




Write an implementation of the fibonacci
example without using and additional array!
Check if a number is prime or not
Find all prime numbers in a specified range
Find the GCD of 2 numbers
Website at
 http://elearning.eng.cu.edu.eg