CS2009-Design an analysis
of Algorithm
Week 1
Dr. Ghous
Department of Computer Science | FAST-NU 1
Reference Books
1. T. Cormen, C. Leiserson, R. Rivest, and C. Stein.
Introduction to Algorithms, 3rd Edition, MIT Press,
2011.
2.Introduction to the Design and Analysis of
Algorithms by Anany Levitin
Other reference books are there in outline to
be shared this week.
2
Project [Tentative]
Programming Project (Undergrad)
The UG students will be given to select a practical problem
and they have to implement the optimal algorithm to solve
the problem.
The problem as well as the algorithm will be chosen based
upon the aptitude and inclination of the student, in
consultation with the course instructor.
3
Course Objective
The course introduces students to advanced
techniques in data structures as well as
design and analysis of high-performance
and scalable algorithms & their engineering
applications.
What should you expect in this course?
Overview of some advanced data structures.
A number of algorithms and computational
techniques to solve complex programming
problems.
Programming
What should you learn by the end of this
course
Ability to design and implement algorithms and
techniques in the broad area of computational
sciences 4
Important characteristics of
a good software
A good design
Easy to implement
Easy to use
Easy to maintain
Reliable solution of the given problem
5
Some Example Data Structures
Arrays Stack Tree Linked List
Data structure = representation and
operations associated with a data type 6
Data Structure Applications
Arrays
lists (one dimensional arrays)
matrices (two dimensional arrays)
database applications
dynamic memory allocation
to implement other data structures, such as heaps, hash
tables, queues, stacks, strings
Stacks
expression evaluation and syntax parsing
Queues
scheduling
transportation
operations management
7
Data Structure Applications
Trees
efficient searching of data (Binary search tree BST)
manipulate hierarchical data
manipulate sorted data
router algorithms
Linked lists
can be used to implement several other common
abstract data structures, such as
stacks
queues
symbolic expressions, and etc
8
So, what exactly is an
Algorithm
Algorithm:
A finite set of
statements that
guarantees an
optimal solution
in finite interval
of time
9
What is an Algorithm?
In mathematics and computer science, an
algorithm is a step-by-step procedure for
solving a problem
expressed as a finite list of well-defined
instructions
with a finite amount of data
in a finite amount of time
Algorithms are used for
calculation
data processing, and
automated reasoning
In simple words
an algorithm is a step-by-step procedure for
calculations 10
The Algorithm to Start the Car
1. Insert the key
2. Make sure car is in neutral gear
3. Press the gas pedal/ (Accelerator)
4. Turn the key to the start position
5. If the engine starts in 6 seconds
1. Release the key to the ignition position
6. Else if the engine does not start in 6 seconds
1. Release the key and gas pedal
2. Wait for 10 seconds , and repeat the steps 3 – 6,
but no more than 5 times
7. If the car does not start
1. Call the workshop 11
What is an Algorithm?
An algorithm is thus a sequence of computational steps that
transform the input into the output.
Input: A sequence of n numbers ()
Output: A permutation (reordering) () of the input sequence such
that
For example, given the input sequence (31, 41 , 59 , 26 , 41 , 58), a
sorting algorithm returns as output the sequence (26 , 31 , 41 , 41 ,
58 , 59).
Such an input sequence is called an instance of the sorting
problem.
In general, an instance of a problem consists of the input
(satisfying whatever constraints are imposed in the problem
statement) needed to compute a solution to the problem.
12
Do we have better Algorithm?
Which algorithm is best for a given
application depends on—among other
factors
The number of items to be sorted
The extent to which the items are already
somewhat sorted
Possible restrictions on the item values
The architecture of the computer
And the kind of storage devices to be used:
main memory, disks, or even tapes
13
Do we have better Algorithm?
An algorithm is said to be correct if, for every input instance, it
halts with the correct output.
We say that a correct algorithm solves the given computational
problem.
An incorrect algorithm might not halt at all on some input instances,
or it might halt with an incorrect answer.
Contrary to what you might expect, incorrect algorithms can
sometimes be useful, if we can control their error rate.
14
Good Algorithms?
Run in less time
Consume less memory
- But computational resources (time
complexity) is usually more important
- Memory is not an issue now-a-days
- Why time is important in algorithms?
- Usability
- Multiple users
15
Measuring Efficiency
The efficiency of an algorithm is a measure
of the amount of resources consumed in
solving a problem of size n.
The resource we are most interested in is time
We can use the same techniques to analyze
the consumption of other resources, such as
memory space.
It would seem that the most obvious way to
measure the efficiency of an algorithm is to
run it and measure how much processor
time is needed Is it correct
No, Computer has multiple processes to execute
16
Factors in solving the
problem
Hardware
Operating System
Algorithm
Compiler
Size of input
Nature of Input
Which should be improved?
17
How to analyze an algorithm
Time
Space
Network Traffic
Power
CPU registers
18
Running Time of an
Algorithm
Depends upon:
Input Size
Nature of Input
Generally, time grows with size of input, so
running time of an algorithm is usually
measured as function of input size.
Running time is measured in terms of
number of steps/primitive operations
performed
Independent from machine, OS
19
Analysis of Algorithms
An algorithm is a finite set of precise
instructions for performing a computation
or for solving a problem.
What is the goal of analysis of algorithms?
To compare algorithms mainly in terms of
running time but also in terms of other factors
(e.g., memory requirements, programmer's
effort etc.)
What do we mean by running time analysis?
Determine how running time increases as
the size of the problem increases.
20
Asymptotic
Asymptotic Notation,
Notation,
Review
Review of
of Functions
Functions &
&
Summations
Summations
Department of Computer Science | FAST-NU 21
Running time Analysis
Once the input size n becomes large enough, merge sort,
with its ‚.n lg n worst-case running time, beats insertion sort,
whose worst-case running time is ‚.
Although we can sometimes determine the exact running
time of an algorithm, the extra precision is not usually worth
the effort of computing it.
For large enough inputs, the multiplicative constants and
lower-order terms of an exact running time are dominated by
the effects of the input size itself.
When we look at input sizes large enough to make only the
order of growth of the running time relevant, we are studying
the asymptotic efficiency of algorithms.
That is, we are concerned with how the running time of an
algorithm increases with the size of the input in the limit, as
the size of the input increases without bound.
Usually, an algorithm that is asymptotically more efficient will
be the best choice for all but very small inputs.
22
Priori vs posteriori analysis
Priori Posteriori
Algorithms Program
Independent of Language
Language Dependent
Hardware Hardware
Independent Dependent
Time & Space Watch Time and
Function Bytes
23
Asymptotic Complexity
Running time of an algorithm as a function
of input size n for large n.
Expressed using only the highest-order
term in the expression for the exact
running time.
Instead of exact running time, say
Q(n2).
Describes behavior of function in the limit.
Written using Asymptotic Notation.
24
used to asymptotically bound
an algorithm
Big-O, Omega, and Theta are formal
notational methods for stating the growth
of resource needs (efficiency and storage)
of an algorithm.
In simple words theoretically bound an
algorithm with some function
25
Asymptotic Notation
Q, O, W, o, w
Defined for functions over the natural
numbers.
Ex: f(n) = Q(n2).
Describes how f(n) grows in comparison to n2.
Define a set of functions; in practice used
to compare two function sizes.
The notations describe different rate-of-
growth relations between the defining
function and the defined set of functions.
26
-notation
For function g(n), we define (g(n)),
big-Theta of n, as the set:
(g(n)) = {f(n) :
positive constants c1, c2, and n0,
such that n n0,
we have 0 c1g(n) f(n)
c2g(n)
}Intuitively: Set of all functions that
have the same rate of growth as g(n).
g(n) is an asymptotically tight bound for f(n).
27
Theta
Theta notation describe the tighter bound of
algorithm.
It basically combine the upper bound and
also the lower bound of algorithm.
c2.g(n)
f(n)
c1.g(n)
28
29
O-notation
For function g(n), we define
O(g(n)), big-O of n, as the set:
O(g(n)) = {f(n) :
positive constants c and n0,
such that n n0,
we have 0 f(n) cg(n) }
Intuitively: Set of all
functions whose rate of
growth is the same as or lower
than that of g(n).
g(n) is an asymptotic upper bound for f(n).
f(n) = (g(n)) f(n) = O(g(n)).
(g(n)) O(g(n)).
30
-notation
For function g(n), we define (g(n)),
big-Omega of n, as the set:
(g(n)) = {f(n) :
positive constants c and n0,
such that n n0,
we have 0 cg(n) f(n)}
Intuitively: Set of all
functions whose rate of
growth is the same as or
higher than that of g(n).
g(n) is an asymptotic lower bound for f(n).
f(n) = (g(n)) f(n) = (g(n)).
(g(n)) (g(n)). 31
Comparing Function
32
Comparing Function
33
Comparing Function
34
Ref
https://www.youtube.com/watch?v=9TlHvipP5yA&list=PLDN4rrl48XKpZkf03iYFlO29szjTr
s_O&index=6
https://www.youtube.com/watch?v=9SgLBjXqwd4&list=PLDN4rrl48XKpZkf03iYFlO29szjT
rs_O&index=7
https://www.youtube.com/watch?v=p1EnSvS3urU&list=PLDN4rrl48XKpZkf03iYFlO29szjT
rs_O&index=8
https://www.youtube.com/watch?v=w7t4_JUUTeg&list=PLDN4rrl48XKpZkf03iYFlO29szjTr
s_O&index=9
https://www.youtube.com/watch?v=5v-tKX2uRAk&list=PLDN4rrl48XKpZkf03iYFl O29szjT
rs_O&index=10
35
