Department of Computer Science
Faculty of Communication & Information Sciences
University of Ilorin, Ilorin, Nigeria
CSC 421:
Algorithm Design and Analysis
(Core, 3 Credit Units)
Amos O. BAJEH, PhD
Room 29, Ground Floor/
Sub Dean’s Office
Lecture Etiquette/Principles
No cell phones
No random coming in and going out
No noise making
If you are sleepy, go home
If you want to read email or surf the Web,
please do it elsewhere
Course Content
Analysis of algorithms (time and space requirements): worst,
average, best cases analysis, amortization and potential
methods. Various techniques for algorithms design: Divide and
Conquer, greedy method, dynamic programming, recursion and
use of invariant, searching and sorting techniques. Cook’s
theorem. Backtracking, pattern matching, and string/text
algorithm. Numeric approximation algorithm. Hash Tables and
Graphs analysis. NP-hard and NP-complete problems.
30h (T), 45h (P); C. Pr: CSC 317
Algorithm Design & Analysis
Module 1: Basics of Algorithm
Definition of Algorithm
Algorithm Representation
Module 2: Algorithm Analysis
Time Complexity Analysis
Space Complexity Analysis
Classes of Computational Complexity
Asymptotic Notations
P, NP-Hard and NP-Complete
Algorithm Design & Analysis
Module 3: Approaches to Algorithm Development
Divide and Conquer
Greedy Method
Dynamic Programming
Backtracking
Module 4: Computational algorithms
Searching Algorithms
Sorting Algorithms
Recursion
Graph
Numeric approximation Algorithm
Algorithm Design & Analysis
Week 1: Basics of Algorithm
Week 2: Algorithm Analysis: Time and space complexity
Week 3: Asymptotic analysis
Week 4: Algo. Development Approach: Divide and Conquer,
and Greedy Method
Week 5: Dynamic Programming and Backtracking
Week 6: Searching and Sorting Algorithms
Week 7: Continuous Assessment (CA)
Week 8: Graphs
Week 9: Algorithm Analysis II: P, NP-Hard and NP-Complete
Basics of Algorithm
What is Algorithm?
Algorithm is the ordered steps taken to solve computational
problems.
Characteristics of good algorithm:
Unambiguous
Finite steps
Language independence
Input: 0 or more inputs
Output: 1 or more outputs
Feasibility: should be feasible with available resources
Efficient in usage of computational resources: time and space
Generality: be able to solve all problems within a given problem domain
Basics of Algorithm
Difference between Algorithm and Program
Algorithm Program
Design Implementation
Domain knowledge expert Programmer
Lang. independent Programming Language
H/W and OS independent H/W and OS dependent
Priori Analysis Posteriori Testing
Basics of Algorithm
Algorithm Representation
2 main forms in which algorithms can be represented:
Flowchart: graphical representation using symbols:
Terminal symbols
Arrow symbol
Input/output symbols
Decision symbols
Processing symbol
Database or storage symbol
Pro-processing symbol
Connector symbol
Subroutine symbol
Pseudocode: representation in words
Algorithm Analysis
Resources considered for Algorithm Analysis
Time Complexity
Time complexity is the measure of the time required by an
algorithm to execute from start to finish.
It is the objective of computer scientist to reduce the time
complexity of algorithms or development algorithms that
requires the minimum possible time to execute.
Space Complexity
Space complexity is the measure of the amount of memory
required by an algorithm for its execution from start to finish.
This complexity measure is significant in cases where memory
needs to be shared among demanding programs and the
memory is limited.
Algorithm Analysis
Time Complexity
How do we answer the question: How long will it take the
following code to run?
ans = 1
DO WHILE n > = 1
ans = ans * 1
n = n - 1
END DO
CPU clock time
The value of the time in second will depend on the following issues:
1. The speed of the computer on which it is executed (machine-
dependent)
2. The value of the input, n
Algorithm Analysis
Time Complexity
Resolving the issues above:
1. The speed of the computer on which it is executed
By
a) basing the computation time on the number of basic
operations in the algorithm
b) assuming that each basic operation takes constant time
This method is known as Frequency count
2. The value of the input, n:
By determining how the time grows as the size of input
grows - This is known as asymptotic analysis using
asymptotic notation
Algorithm Analysis
1
n+1
2xn
2xn
Algorithm Analysis
n 1 5n
10 2 98
1000 0.01 99.99
5000 0.004 99.996
10000 0.002 99.998
1000000 0.00002 99.99998
Algorithm Analysis
Algorithm Analysis
Time Complexity
Exercises
1. Determine the time function for the algorithm to determine:
i. the sum of the content of a given array
ii. the sum of two matrices
iii. the product of two matrices
Algorithm Analysis
Time Complexity
Exercises
2. Determine the time function for the following code segments
i. for(i = 0; i<n; i++){
stmt
}
ii. for(i = 1; i<n; i=i+2){
stmt
}
Algorithm Analysis
Time Complexity
Exercises
2. Determine the time function for the following code segments
iii. for(i = 0; i<n; i++){
for(j=0; j<n; j++){
stmt
}
}
Algorithm Analysis
Time Complexity
Exercises
2. Determine the time function for the following code segments
iv. for(i = 0; i<n; i++){
for(j=0; j<i; j++){
stmt
}
}
v. for(i=1; i<n; i=i*2){
stmt
}
Algorithm Analysis
Time Complexity
2. Determine the time function for the following code segments
vi. for(i = 0; i*i<n; i++){
stmt
}
vii. for(i=0; i<n; i++){
stmt;
}
for(j=0; j<n; j++){
stmt
}
Algorithm Analysis
Time Complexity
2. Determine the time function for the following code segments
viii. for(i = 0; i<n; i++){
for(j=0; j<n; j=j*2){
stmt
}
}
Algorithm Analysis
Time Complexity
2. Determine the time function for the following code segments
ix. i = 0
while(i<n){
stmnt;
i++;
}
x. a = 0
while(a<b){
stmnt;
a = a*2;
}
Algorithm Analysis
Time Complexity
2. Determine the time function for the following code segments
xi. i = 1
k = 1
while(k<n){
stmnt;
k = k + i;
i++;
}
xii. While(m != n)
if(m > n)
m = m – n
else n = n – m
}
Algorithm Analysis
Reading Assignment 1
Recurrence Relations and how to solve them
Recurrence relationships are good for representing the
complexity of recursions in algorithms
Algorithm Analysis
Classes of Complexity
1. Constant complexity: O(1)
2. Logarithm complexity: O(log n)
3. Linear complexity: O(n)
4. Log-Linear complexity: O(n log n)
5. Polynomial complexity: O(nk)
6. Exponential complexity: O(kn)
Algorithm Analysis
Classes of Complexity
1. Constant complexity: O(1)
This indicates that the asymptotic time is independent of the size of
the input. E.g., algorithms to add or multiply two numbers
Note: this complexity doesn’t imply that there are no loops or recursive call in
the algorithm.
2. Logarithm complexity: O(log n)
This indicates a complexity that grows as the log of its input. E.g.,
Binary search
Note: the base of the log is inconsequential since the diff between using one
base and another is merely a multiplicative constant. E.g., log2n = log210 * log10n
Algorithm Analysis
Classes of Time Complexity
3. Linear complexity: O(n)
Many algorithms that deal with collections such as list have
linear complexity because they have to touch each elements of
the collection some number of times greater than 0.
E. g.: the worst case of the linear search algorithm,
determination of factorial of numbers
Algorithm Analysis
Classes of Complexity
4. Log-Linear complexity: O(n log n)
This is slightly more complicated than the previous classes in
that it involves the product of two terms which are dependent
on the size of the input. Many practical algorithms are log linear.
Most common of them is merge sort.
Algorithm Analysis
Classes of Complexity
5. Polynomial complexity: O(nk)
The most commonly used polynomial algorithms are quadratic
which means that their complexity grows as the square of the
size of the their input. E.g.,
(i) an algorithm to test if a set is a subset of another set
(ii) An algorithm to determine the intersect of two sets and the
intersect should have no duplicates.
Algorithm Analysis
Classes of Complexity
6. Exponential complexity: O(kn)
Some problems are inherently exponential which means that
solving them completely require time that increases
exponentially as the size of the input increases. E.g., an
algorithm to generate the powerset of a given set.
Algorithm Analysis
Classes of Time Complexity
Comparison of Time Complexity functions
O(1) < O(log n) < O(n) < O(n log n) < O(nk) < O(kn)
Time complexity functions
1200000
1000000
O(1)
800000
O(log n)
600000 n
T(n)
n log n
400000 n^k
k^n
200000
0
0 1 2 3 4 5 6 7
n
Note: almost any algorithm is sufficiently efficient when run on
small input. We need to worry when the input is very large
Algorithm Analysis
Asymptotic Notations
1. Big-O notation (Upper bound): O
2. Omega notation (Lower bound): Ω
3. Theta notation (tight bound): θ
Big O notation (Upper bound): O
Definition: The function iff Ǝ positive constants such that .
Example:
Algorithm Analysis
Omega notation (Lower bound): Ω
Definition:
The function iff Ǝ positive constants and such that .
Example:
Algorithm Analysis
Theta notation (Tight bound): θ
Definition: The function iff Ǝ the positive constants such that
.
Example:
Algorithm Analysis
Exercises
Find the Ο, Ω and θ of the following functions
Algorithm Analysis
Properties of Asymptotic Notations
General property: If then .
Example: If is ,
then
Reflexive property: If is given, then
i.e., a function is an upper/lower bound of itself
Example: if
then
Algorithm Analysis
Properties of Asymptotic Notations
Transitive property: If and , then
Example: Given and
then and
thus,
Reflexive property: If is given, then
i.e., a function is an upper/lower bound of itself
Example: if
then
Algorithm Analysis
Properties of Asymptotic Notations
Symmetric property:
If then
Example: and .
Transpose symmetric property: If then
Example:
then and
Algorithm Analysis
Properties of Asymptotic Notations
other properties:
1. If and
then
2. and
then
3. and
then
Algorithm Analysis
Reading Assignment 2
How to mathematically compare functions
Function comparison is very useful for knowing which can serve
as lower or upper bound of another, and thus, the Big O and
Omega of functions can be determined
Algorithm Analysis
Best, Worse and Average cases analyses of Algorithms
Best case: This is the instance of an algorithm input in which the
algorithm has the shortest possible running time. It serve as the
lower bound on the running time of the algorithm -note that this is
not the same as the asymptotic Theta notation.
Worst case: This is the instance of the algorithm input which gives
the algorithm the longest possible running time. It is the upper
bound on the running time of the algorithm. Also, this is different
from the Big-O notation
Average case: This is the average running time over all possible
inputs of an algorithm.
Algorithm Analysis
Best, Worse and Average cases analyses of Algorithms
Using Linear search algorithm to explain this cases
A: 8 6 12 5 9 7 4 3 16 18
Key: 7, 18, 30
Best case?
Worst case?
Average case?