Design and analysis of algorithms

Design and analysis of algorithms

1. DESIGN AND ANALYSIS OF
ALGORITHMS
Dr. G.GeethaMohan
Professor
Department of Computer Science and Engineering,
Jerusalem College of Engineering,
Chennai-600100
1/23/2019 1

2. Outline
Notion of an Algorithm
Fundamentals of Algorithmic Problem
Solving
Important Problem Types
1/23/2019 2

3. What is a Computer Algorithm?
Asequenceofunambiguousinstructions
forsolvingaproblem
Forobtainingarequiredoutputforany
legitimateinputinafiniteamountoftime
1/23/2019 3

4. Computer Algorithm Vs Program
Computer algorithm
A detailed step-by-step method for
solving a problem using a computer
Program
An implementation of one or more
algorithms.
1/23/2019 4

5. Find Greatest Common Divisor of
Two Nonnegative
1.Euclid’s algorithm
gcd(m n) = gcd(n, m mod n)
gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12.
2.Consecutive integer checking
algorithm
For numbers 60 and 24, the algorithm will
try first 24, then 23, and so on, until it
reaches 12, where it stops.
1/23/2019 5

6. Find Greatest Common Divisor of
Two Nonnegative
Middle-school procedure
for the numbers 60 and 24, we get
60 = 2 . 2 . 3 . 5
24 = 2 . 2 . 2 . 3
gcd(60, 24) = 2 . 2 . 3 = 12.
1/23/2019 6

7. Notion of algorithm
1/23/2019 7
Problem
Algorithm
Computer Input Output

8. Notion of algorithm
Non-ambiguityrequirementforeachstepofan
algorithm
Rangeofinputsforwhichanalgorithmworkshas
tobespecified
Samealgorithmcanberepresentedinseveral
differentways.
Existseveralalgorithmsforsolvingthesame
problem.
Algorithmsforthesameproblemcanbebasedon
verydifferentideasandcansolvetheproblem
withdramaticallydifferentspeeds.
1/23/2019 8

9. Understand the problem
Decide on: Computational means
Exact vsApproximate solution
Algorithm design technique
Design an algorithm
Data structures
Prove correctness
Analyze the algorithm
Code the algorithm
Algorithm Design And Analysis Process
1/23/2019 9

10. 1.Understand the problem
Understand completely the problem
given
Input
Output
An input to an algorithm specifies an
instance of the problem the algorithm
solves.
1/23/2019 10

11. 2.1 Ascertaining the Capabilities of
the Computational Device
Sequential Algorithms
Instructions are executed one after another,
one operation at a time.
Random-access Machine (RAM)
Parallel Algorithms
Execute operations concurrently( parallel)
1/23/2019 11

12. 2.2 Choosing between Exact and
Approximate Problem Solving
Exact algorithm
Approximation algorithm
Extractingsquareroots,
Solvingnonlinearequations,
Evaluatingdefiniteintegrals
1/23/2019 12

13. 2.3 Algorithm Design Technique
An algorithm design technique
(“strategy” or “paradigm”)
Generalapproachtosolvingproblems
algorithmicallythatisapplicabletoavariety
ofproblemsfromdifferentareasof
computing.
Algorithmdesigntechniquesmakeit
possibletoclassifyalgorithmsaccordingto
anunderlyingdesignidea
1/23/2019 13

14. 3.Designing an Algorithm and Data
Structures
Several techniques need to be combined,
Hard to pinpoint as applications of the
known design techniques
Algorithms+ data structures = programs
Object-oriented programming
Data structuresremain crucially
important for both design and analysis of
algorithms.
1/23/2019 14

15. Methods of Specifying an Algorithm
Pseudo code
A mixture of a natural language and
programming language
Flowchart
A method of expressing an algorithm by a
collection of connected geometric shapes
containing descriptions of the algorithm’s
steps.
Programs
Another way of specifying the algorithm
1/23/2019 15

16. 4.Prove Correctness
Toprovethatthealgorithmyieldsa
requiredresultforeverylegitimateinputin
afiniteamountoftime
A common technique for proving correctness is to use
mathematical induction
Tracing the algorithm’sperformance for a few specific
inputs to show that an algorithm is incorrect
The notion of correctness for
Exact algorithms -straight forward
Approximation algorithms-less straight forward
to be able to show that the error produced by the
algorithm does not exceed a predefined limit.
1/23/2019 16

17. 5.Analyze the Algorithm
Efficiency
Timeefficiency,
Howfastthealgorithmruns,
Spaceefficiency,
Howmuchextramemoryituses.
Simplicity
Easiertounderstandandeasiertoprogram
Generality
Issues-Algorithmsolves
Setofinputsitaccepts
1/23/2019 17

18. 6. Code the Algorithm
Programminganalgorithm
bothaperilandanopportunity.
Testanddebugprogramthoroughly
wheneverimplementanalgorithm.
Implementinganalgorithmcorrectlyis
necessarybutnotsufficient
Ananalysisisbasedontimingthe
programonseveralinputsandthen
analyzingtheresultsobtained.
1/23/2019 18

19. 6. Code the Algorithm (cond…)
Algorithm’s Optimality.
Not about the efficiency of an algorithm
About the complexity of the problem it solves
What is the minimum amount of effort any
algorithm will need to exert to solve the
problem?
Another important issue of algorithmic problem
solving
Whether or not every problem can be solved
by an algorithm.
Not talking about problems that do not have a
solution
1/23/2019 19

20. Algorithms
Inventing (or discovering?) Algorithms is
a very creative and rewarding process.
A good algorithm is a result of repeated
effort and rework
1/23/2019 20

21. Important Problem Types
Sorting
Searching
String processing
Graph problems
Combinatorial problems
Geometric problems
Numerical problems
1/23/2019 21

22. 1. Sorting
Rearrange the items of a given list in non
decreasing order
Specially chosen piece of information-key
Used as an auxiliary step in several important
algorithms in other areas
Geometric Algorithms and Data Compression
Greedy approach an important algorithm design
technique requires a sorted input.
1/23/2019 22

23. 1. Sorting
Two properties
Stable
Preserves the relative order of any two
equal elements in its input.
In-place
The amount of extra memory the
algorithm requires
An algorithm is said to be in-place if it
does not require extra memory
1/23/2019 23

24. 2. Searching
Dealswithfindingagivenvalue,calleda
searchkey,inagivenset
(oramultiset,whichpermitsseveral
elementstohavethesamevalue)
SequentialSearchorlinearSearch
Binarysearch
1/23/2019 24

25. 2. Searching
Considered in conjunction with two
other operations:
Addition to
Deletion from the data set of an item.
Data structures and Algorithms should be
chosen to strike a balance among the
requirements of each operation.
1/23/2019 25

26. 3. String processing
Sequence of characters from an alphabet
Strings of particular interest are
Text strings, which comprise letters,
numbers, and special characters;
Bit strings, which comprise zeros and ones;
Gene sequences, which can be modeled by
strings of characters from the four-
character alphabet {A,C, G, T}.
1/23/2019
26

27. String Matching
Searching for a given word in a text
1/23/2019 27

28. 4. Graph Problems
Collectionofpointscalledvertices,
Someofwhichareconnectedbyline
segmentscallededges.
Usedformodelingawidevarietyof
applications
Transportation,
Communication,
SocialandEconomicnetworks
Projectscheduling
Games.
1/23/2019 28

29. Graph Problems
Basic graph algorithms
Graph traversal algorithms
How can one reach all the points in a
network?
Shortest-path algorithms
What is the best route between two cities?
Topological sorting for graphs with
directed edges
set of courses with their prerequisites
consistent or self-contradictory?.
1/23/2019 29

30. Graph Problems
Traveling Salesman Problem (TSP)
Problemoffindingtheshortesttour
throughncitiesthatvisitseverycity
exactlyonce.
Route Planning
Circuit board
VLSI chip fabrication
X-ray crystallography
Genetic Engineering
1/23/2019 30

31. Graph Problems
Graph-coloringproblem
seekstoassignthesmallestnumberof
colorstotheverticesofagraphsothat
notwoadjacentverticesarethesame
color
EventScheduling:
Eventsarerepresentedbyverticesthatareconnected
byanedgeifandonlyifthecorrespondingevents
cannotbescheduledatthesametime,asolutiontothe
graph-coloringproblemyieldsanoptimalschedule.
1/23/2019 31

32. 5. Combinatorial Problems
Traveling Salesman Problem and the
Graph Coloring Problem are examples of
combinatorial problems.
These are problems that ask, explicitly or
implicitly, to find a combinatorial object
such as a permutation, a combination, or a
subset that satisfies certain constraints.
1/23/2019 32

33. 5. Combinatorial Problems
Issues
Numberofcombinatorialobjectstypicallygrows
extremelyfastwithaproblem’ssize,reaching
unimaginablemagnitudesevenformoderate-
sizedinstances.
Therearenoknownalgorithmsforsolvingmost
suchproblemsexactlyinanacceptableamount
oftime.
1/23/2019 33

34. 6.Geometric Algorithms
Geometricalgorithmsdealwithgeometric
objectssuchaspoints,lines,andpolygons.
AncientGreeks-developingprocedures
Forsolvingavarietyofgeometricproblems,
Constructingsimplegeometricshapes
-triangles,circles
Computergraphics
Robotics
Tomography
1/23/2019 34

35. 6.Geometric Algorithms
Closest-pairproblem
Givennpointsintheplane,findtheclosest
pairamongthem.
Convex-hullproblem
Tofindthesmallestconvexpolygonthat
wouldincludeallthepointsofagivenset.
1/23/2019 35

36. 7. Numerical problems
Problems that involve mathematical
objects of continuous nature
Solving equations
Systems of equations,
Computing definite integrals,
Evaluating functions
1/23/2019 36

37. 7. Numerical problems
Mathematical problems can be solved
only approximately
Problems typically require manipulating
real numbers, which can be represented
in a computer only approximately.
Large number of arithmetic operations
performed on approximately represented
numbers can lead to an accumulation of
the round-off
1/23/2019 37

38. Modeling the Real World
Cast your application in terms of well-studied abstract
data structures
1/23/2019
38
Concrete Abstract
arrangement, tour, ordering, sequence permutation
cluster, collection, committee, group, packaging, selectionsubsets
hierarchy, ancestor/descendants, taxonomy trees
network, circuit, web, relationship graph
sites, positions, locations points
shapes, regions, boundaries polygons
text, characters, patterns strings

39. Real-World Applications
Hardware design: VLSI
chips
Compilers
Computer graphics: movies,
video games
Routing messages in the
Internet
Searching the Web
Distributed file sharing
1/23/2019
39
•Computer aided design and
manufacturing
•Security: e-commerce,
voting machines
•Multimedia: CD player, DVD,
MP3, JPG, HDTV
•DNA sequencing, protein
folding
•and many more!

40. Some Important Problem Types
Sorting
◦a set of items
Searching
◦among a set of items
String processing
◦text, bit strings, gene
sequences
Graphs
◦model objects and their
relationships
1/23/2019
40
•Combinatorial
–find desired permutation,
combination or subset
•Geometric
–graphics, imaging,
robotics
•Numerical
–continuous math: solving
equations, evaluating
functions

41. Algorithm Design Techniques
•Brute Force & Exhaustive
Search
–follow definition / try all
possibilities
•Divide & Conquer
–break problem into
distinct subproblems
•Transformation
–convert problem to
another one
•Dynamic Programming
–break problem into overlapping
sub problems
•Greedy
–repeatedly do what is best now
•Iterative Improvement
–repeatedly improve current
solution
•Randomization
–use random numbers
1/23/2019
41