Design and Analysis of
Algorithms
week #1 Adapted from slides by Dr A. Sattar
Books
Recommended Text Books:
Author Title Edition/Year Published Publisher
T. H. Cormen, C. E.
2nd/
Leiserson, and R. L. Introduction to Algorithms MIT Press,
2001
Rivest,
Recommended Reference Books
Author Title Edition/Year Published Publisher
1st/
Jon Kleinberg, Eva Tardos Algorithm Design Addison-Wesley
2005
Computer Algorithms:
Sara Baase, Allen van 3rd/
Introduction to Design & Addison-Wesley
Gelder 2000
Analysis
1st/
Robert Sedgewick Algorithms in C++ Addison-Wesley
2001
week #1 Adapted from slides by Dr A. Sattar
History
• Procedures for solving geometric and arithmetic problems were formulated by ancient
Greeks
• Some two thousands years ago, the celebrated procedure for finding greatest common
divisor (gcd) was discovered by Euclid
• The word algorithm comes from the name of the 9th century Persian mathematician
Abu Abdullah Muhammad ibn Musa al-Khwarzimi
• His works introduced algebraic concepts
• He worked in Baghdad at the time when it was the centre of scientific studies and
trade.
• Al-Khwarzimi's name was translated into Latin, and eventually became algorithm
week #1 Adapted from slides by Dr A. Sattar
Importance
week #1 Adapted from slides by Dr A. Sattar
Algorithms today
• The word originally referred only to the rules of performing arithmetic
• The word evolved to include all definite procedures for solving problems
or performing tasks
• In the mid-twentieth century D.E. Knuth undertook in depth study and
analysis of algorithms
• His work is embodied in his comprehensive book ‘The art of computer
programming’, which serves as a foundation for modern study of
algorithms
week #1 Adapted from slides by Dr A. Sattar
Definition
• An algorithm is an orderly step-by-step procedure, which has the characteristics:
1) It accepts one or more input value
2) It returns at least one output value
3) It terminates after finite steps
• An algorithm may also be viewed as a tool for solving a computational problem
‘Determine whether the number x is in the list S of n numbers. The answer is Yes if x is in S and No
if it is not’
S = [5, 7, 11, 4, 9] n = 5 x = 9 is an instance of the problem
Solution to this instance is ‘Yes’
week #1 Adapted from slides by Dr A. Sattar
Applications
• Algorithms have been developed to solve an enormous variety of
problems in many application domains. Some broad categories of
algorithms are listed below.
• Sorting Algorithms
• Searching Algorithms
• String Processing (Pattern matching, Compression, Cryptography)
• Image Processing (Compression, Matching, Conversion)
• Mathematical Algorithms (Random number generator, matrix operations)
• Machine Learning Algorithms
week #1 Adapted from slides by Dr A. Sattar
Applications (contd…)
• Some applications do not explicitly require algorithmic content at the
application level
• Even so, it may rely heavily upon algorithms
• Does the application require fast hardware?
• Hardware design uses algorithms
• Does the application rely on networking?
• Routing in networks relies heavily on algorithms
• Does it use a language other than machine code?
• Compilers, Interpreters make extensive use of algorithms
week #1 Adapted from slides by Dr A. Sattar
Algorithms Classic Problems
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
Analysis of Algorithms
Objective
• Analyzing an algorithm has come to mean predicting the resources that it
requires
• The purpose of algorithm analysis is to determine:
• Time efficiency
• Performance in terms of running times for different input sizes
• Space utilization
• Requirement of storage to run the algorithm
• Correctness of algorithm
• Results are trustworthy, and algorithm is robust
week #1 Adapted from slides by Dr A. Sattar
Algorithm Efficiency
• Time efficiency remains an important consideration when developing
algorithms
• Algorithms designed to solve the same problem may differ
dramatically in efficiency
• These differences can be much more significant than differences due
to hardware and software
• Example : Sequential search vs. Binary search
week #1 Adapted from slides by Dr A. Sattar
Algorithm Efficiency (contd…)
• The number of comparisons done by sequential search and binary search
when x (value being searched) is larger than all array items
Array Size Number of comparisons - Sequential Number of comparisons - Binary
search search
128 128 8
1,024 1,024 11
1,048,576 1,048,576 21
4,294,967,296 4,294,967,296 33
week #1 Adapted from slides by Dr A. Sattar
Algorithm Efficiency (contd…)
• Another comparison in terms of algorithm execution time
Execution time of Algorithm 1 Execution time of Algorithm 2
41 ns 1048 µs
61 ns 1s
81 ns 18 min
101 ns 13 days
121 ns 36 years
161 ns 3.8 * 107 years
201 ns 4 * 1013 years
week #1 Adapted from slides by Dr A. Sattar
Approaches to Analysis
• Basically three approaches can be adopted to analyze algorithm
running time in terms of input size:
• Empirical Approach
• Running time measured experimentally
• Analytical Approach
• Running time estimated using mathematical modeling
• Visualization
• Performance is studied through animation for different data sets
week #1 Adapted from slides by Dr A. Sattar
Empirical Approach
• The running time of algorithm is measured for different data sizes and
time estimates are plotted against the input. The graph shows the trend.
week #1 Adapted from slides by Dr A. Sattar
Limitations
• Running time critically depends on:
• Hardware resources used
• (CPU speed, IO throughput, RAM size)
• Software environment
• (Compiler, Programming Language)
• Program design approach
• (Structured, Object Oriented)
• Data set
• Choice of data values and range of data
week #1 Adapted from slides by Dr A. Sattar
Analytical Approach
• We want a measure that is independent of the computer, programming language and
complex details of the algorithm.
• Usually this measure is in terms of how many times a basic operation is carried out for each
value of the input size.
• Strategy: Running time is estimated by analyzing the primitive operations which make a
significant contributions to the overall algorithm time. These may broadly include:
• Assigning a value
• Comparing data items
• Computing a value
• Moving a data item
• Calling a procedure
• Returning a value
week #1 Adapted from slides by Dr A. Sattar
The Need for Analysis
week #1 Adapted from slides by Dr A. Sattar
Things to Remember
week #1 Adapted from slides by Dr A. Sattar
Algorithm Specification
Conventions
For the purpose of design and analysis, the algorithms are often
specified in either of the ways:
• Plain natural language
• High level description which identifies significant steps, mainly to describe
the design features.
• Pseudo Code
• Low level to facilitate analysis and implementation
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
Types of Analysis
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
week #1 Adapted from slides by Dr A. Sattar
Algorithm
Design and
Analysis Process
