Advanced Algorithms Analysis
and Design
By
Dr. Nazir Ahmad Zafar
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
M. Sc. Mathematics:
1989-91
Quaid-i-Azam University, Islamabad
M. Phil Mathematics:
1991-93
Quaid-i-Azam University, Islamabad
M. Sc. Nuclear Engineering:
1993-94
Quaid-i-Azam University, Islamabad
PhD Computer Science:
2000-04
Kyushu University, Japan
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Objective of This Course
Major objective of this course is:
Design and analysis of modern algorithms
Different variants
Accuracy
Efficiency
Comparing efficiencies
Motivation thinking new algorithms
Advanced designing techniques
Real world problems will be taken as examples
To create feelings about usefulness of this course
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Expected Results
On successful completion, students will be able to
Argue and prove correctness of algorithms
Derive and solve mathematical models of problems
Reasoning when an algorithm calls certain approach
Analyze average and worst-case running times
Integrating approaches in dynamic and greedy algos.
Use of graph theory in problems solving
Advanced topics such as
Computational geometry, number theory etc.
Several other algorithms such as
String matching, NP completeness, approximate
algorithms etc.
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Lecture No 1
Introduction
(What, Why and Where Algorithms . . .)
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Today Covered
In this lecture we will cover the following
What is Algorithm?
Designing Techniques
Model of Computation
Algorithms as a technology
Algorithms and other technologies
Importance of algorithms
Difference in Users and Developers
Kinds of problems solved by algorithms
Conclusion
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
What is Algorithm?
A computer algorithm is a detailed step-by-step method
for solving a problem by using a computer.
An algorithm is a sequence of unambiguous instructions
for solving a problem in a finite amount of time.
An Algorithm is well defined computational procedure that
takes some value, or set of values, as input and produces
some value, or set of values as output.
More generally, an Algorithm is any well defined
computational procedure that takes collection of elements
as input and produces a collection of elements as output.
Input
Dr Nazir A. Zafar
Algorithm
output
Advanced Algorithms Analysis and Design
Popular Algorithms, Factors of Dependence
Most basic and popular algorithms are
Sorting algorithms
Searching algorithms
Which algorithm is best?
Mainly, it depends upon various factors, for
example in case of sorting
The number of items to be sorted
The extent to which the items are already sorted
Possible restrictions on the item values
The kind of storage device to be used etc.
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
One Problem, Many Algorithms
Problem
The statement of the problem specifies, in general
terms, the desired input/output relationship.
Algorithm
The algorithm describes a specific computational
procedure for achieving input/output relationship.
Example
One might need to sort a sequence of numbers
into non-decreasing order.
Algorithms
Various algorithms e.g. merge sort, quick sort,
heap sorts etc.
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Important Designing Techniques
Brute Force
Straightforward, naive approach
Mostly expensive
Divide-and-Conquer
Divide into smaller sub-problems
Iterative Improvement
Improve one change at a time
Decrease-and-Conquer
Decrease instance size
Transform-and-Conquer
Modify problem first and then solve it
Space and Time Tradeoffs
Use more space now to save time later
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Some of the Important Designing Techniques
Greedy Approach
Locally optimal decisions, can not change once made.
Efficient
Easy to implement
The solution is expected to be optimal
Every problem may not have greedy solution
Dynamic programming
Decompose into sub-problems like divide and conquer
Sub-problems are dependant
Record results of smaller sub-problems
Re-use it for further occurrence
Mostly reduces complexity exponential to polynomial
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Problem Solving Phases
Analysis
How does system work?
Breaking a system down to known components
How components (processes) relate to each other
Breaking a process down to known functions
Synthesis
Building tools
Building functions with supporting tools
Composing functions to form a process
How components should be put together?
Final solution
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Problem Solving Process
Problem
Strategy
Algorithm
Input
Output
Steps
Analysis
Correctness
Time & Space
Optimality
Implementation
Verification
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Model of Computation (Assumptions)
Design assumption
Level of abstraction which meets our requirements
Neither more nor less e.g. [0, 1] infinite continuous interval
Analysis independent of the variations in
Machine
Operating system
Programming languages
Compiler etc.
Low-level details will not be considered
Our model will be an abstraction of a standard
generic single-processor machine, called a random
access machine or RAM.
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Model of Computation (Assumptions)
A RAM is assumed to be an idealized machine
Infinitely large random-access memory
Instructions execute sequentially
Every instruction is in fact a basic operation on two
values in the machines memory which takes unit time.
These might be characters or integers.
Example of basic operations include
Assigning a value to a variable
Arithmetic operation (+, - , , /) on integers
Performing any comparison e.g. a < b
Boolean operations
Accessing an element of an array.
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Model of Computation (Assumptions)
In theoretical analysis, computational complexity
Estimated in asymptotic sense, i.e.
Estimating for large inputs
Big O, Omega, Theta etc. notations are used to
compute the complexity
Asymptotic notations are used because different
implementations of algorithm may differ in efficiency
Efficiencies of two given algorithm are related
By a constant multiplicative factor
Called hidden constant.
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Drawbacks in Model of Computation
First poor assumption
We assumed that each basic operation takes
constant time, i.e. model allows
Adding
Multiplying
Comparing etc.
two numbers of any length in constant time
Addition of two numbers takes a unit time!
Not good because numbers may be arbitrarily
Addition and multiplication both take unit time!
Again very bad assumption
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Model of Computation not so Bad
Finally what about Our Model?
But with all these weaknesses, our model is not so
bad because we have to give the
Comparison not the absolute analysis of any algorithm.
We have to deal with large inputs not with the small size
Model seems to work well describing computational
power of modern nonparallel machines
Can we do Exact Measure of Efficiency ?
Exact, not asymptotic, measure of efficiency can be
sometimes computed but it usually requires certain
assumptions concerning implementation
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Summary : Computational Model
Analysis will be performed with respect to this
computational model for comparison of algorithms
We will give asymptotic analysis not detailed
comparison i.e. for large inputs
We will use generic uniprocessor random-access
machine (RAM) in analysis
All memory equally expensive to access
No concurrent operations
All reasonable instructions take unit time,
except, of course, function calls
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
Conclusion
What, Why and Where Algorithms?
Designing Techniques
Problem solving Phases and Procedure
Model of computations
Major assumptions at design and analysis level
Merits and demerits, justification of assumptions taken
We proved that algorithm is a technology
Compared algorithmic technology with others
Discussed importance of algorithms
In almost all areas of computer science and engineering
Algorithms make difference in users and developers
Dr Nazir A. Zafar
Advanced Algorithms Analysis and Design
