Chapter1.1 Introduction to design and analysis of algorithm.ppt

Design and analysis of algorithm

1. Course Title: Design and Analysis of
Algorithms

2. CHAPTER 1: INTRODUCTION
•Algorithms
•Analyzing Algorithms
•Designing Algorithms

3. Algorithms?
WhyAlgorithmsisneeded?
computationalproblemsingeneralandofthe
algorithmsneededtosolvethem
WhatisAlgorithms?
Analgorithmisanywell-defined
computationalprocedure
WithWhat?
Ittakessomevalue,orsetofvalues,asinput
andproducessomevalue,orsetofvalues,as
output

4. Definition: Algorithms
•Analgorithmisthusasequenceof
computationalstepsthattransformtheinput
intotheoutput.Andalsoviewanalgorithmas
atoolforsolvingawell-specified
computationalproblem.

5. Example:
•Input:A sequence of nnumbers a
1, a
2, . . . , a
n.
•Output:A permutation (reordering)
of the input sequence such that
Ex:
Given an input sequence such as 31, 41, 59, 26,
41, 58 , a sorting algorithm returns as output
the sequence 26, 31, 41, 41, 58, 59

6. Law of Algorithms
•An algorithm is said to becorrectif, 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
other than the desired answer.

7. Steps to design the Algorithm
1.Under stand the problem
2.Decide about the way to solve the problem
3.Design the algorithm
4.Prove the correctness
5.Analysis the algorithm
6.Code the algorithm

8. Analyzing the Algorithms
WhyisitImportant?
Ithascometomeanpredictingtheresources
thatthealgorithmrequires.
Occasionally,resourcessuchasmemory,
communicationbandwidth,orlogicgatesare
ofprimaryconcern,
butmostoftenitiscomputationaltimethat
wewanttomeasure

9. Analysis of Algorithms
•Analysis of Algorithmsis the area of computer science that
provides tools to analyze the efficiency of different methods of
solutions.
•How do we compare the time efficiency of two algorithms that
solve the same problem?
Naïve Approach: implement these algorithms in a programming
language (C++), and run them to compare their time
requirements. Comparing the programs (instead of algorithms)
has difficulties.
–How are the algorithms coded?
•Comparing running times means comparing the implementations.
•We should not compare implementations, because they are sensitive to programming
style that may cloud the issue of which algorithm is inherently more efficient.
–What computer should we use?
•We should compare the efficiency of the algorithms independently of a particular
computer.
–What data should the program use?
•Any analysis must be independent of specific data.

10. CENG 213 Data Structures 10
Analysis of Algorithms
•When we analyze algorithms, we should employ
mathematical techniques that analyze algorithms
independently of specific implementations,
computers, or data.
•To analyze algorithms:
–First, we start to count the number of significant
operations in a particular solution to assess its
efficiency.
–Then, we will express the efficiency of algorithms using
growth functions.

11. Before Analyzing
•What to do?
have a model of the implementation technology
that will be used
it means, resources of that technology and their
costs and running time
Example:
random-access machine(RAM)

12. Requirement for Analayze
•mathematicaltoolsrequiredlike,discrete
combinatorics,elementaryprobabilitytheory,
algebraicdexterity,mostsignificanttermsina
formula.(behaviorofthealgorithmmay
changedifferentI/P)
•findameansofexpressionthatissimpleto
writeandmanipulate,showstheimportant
characteristicsofanalgorithm'sresource
requirements,andsuppressestediousdetails.

13. 13
General Rules for Estimation
•Loops: The running time of a loop is at most the
running time of the statements inside of that loop
times the number of iterations.
•Nested Loops: Running time of a nested loop
containing a statement in the inner most loop is the
running time of statement multiplied by the product
of the sized of all loops.
•Consecutive Statements: Just add the running times
of those consecutive statements.
•If/Else: Never more than the running time of the test
plus the larger of running times of S1 and S2.

14. Importance of Analyze Algorithm
•Need to recognize limitations of various algorithms
for solving a problem
•Need to understand relationship between problem
size and running time
–When is a running program not good enough?
•Need to learn how to analyze an algorithm's running
time without coding it
•Need to learn techniques for writing more efficient
code
•Need to recognize bottlenecks in code as well as
which parts of code are easiest to optimize

15. Measuring Complexity Again
•Theworstcaserunningtimeofanalgorithmisthefunction
definedbythemaximumnumberofstepstakenonany
instanceofsizen.
•Thebestcaserunningtimeofanalgorithmisthefunction
definedbytheminimumnumberofstepstakenonany
instanceofsizen.
•Theaverage-caserunningtimeofanalgorithmisthefunction
definedbyanaveragenumberofstepstakenonanyinstance
ofsizen.
•Whichoftheseisthebesttouse?

16. Order of Growth
•It is therate of growth,or order of growth,of
the running time
•we write that insertion sort, for example, has
a worst-case running time of θ(n
2
)

17. Best, Worst, and Average Case

18. Basic Common Growth Rates
1 constant
log n logarithmic
n linear
n log n n-log-n
n
2
quadratic
n
3
cubic
2
n
exponential
n! factorial

19. Running times for small inputs

20. •many ways to design algorithms.
•Learn general approaches to algorithm design
–Divide and conquer
–Greedy method
–Dynamic Programming
–Basic Search and Traversal Technique
–Graph Theory
–Linear Programming
–Approximation Algorithm
–NP Problem
Designing algorithms

21. Designing algorithms
•Twoapproaches:
1.incrementalapproach
2.Divideandconquerapproach
Thedivide-and-conquerapproach
recursiveinstructure
→tosolveagivenproblem,theycall
themselvesrecursivelyoneormoretimesto
dealwithcloselyrelatedsubproblems.

22. Threestepsateachlevelofthe
recursion:
•Divide
•Conquer (recurcively)
•Combine

23. Analyzing divide-and-conquer
algorithms
•When an algorithm contains a recursive call to
itself, its running time can often be described
by a recurrence equationor recurrence, which
describes the overall running time on a
problem of size nin terms of the running time
on smaller inputs.

24. A recurrence for the running time of a divide-
and-conquer algorithm is based on the three
steps of the basic paradigm

25. •Examine methods of analyzing algorithm
correctness and efficiency
–Recursion equations
–Lower bound techniques
–O,Omega and Theta notations for best/worst/average case analysis
•Decide whether some problems have no
solution in reasonable time
–List all permutations of n objects (takes n! steps)
–Travelling salesman problem
•Investigate memory usage as a different
measure of efficiency