Design and analysis of algorithms

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

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

What is a Computer Algorithm?
A sequence of unambiguous instructions
for solving a problem
For obtaining a required output for any
legitimate input in a finite amount of time
1/23/2019 3

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

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

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

Notion of algorithm
1/23/2019 7
Problem
Algorithm
ComputerInput Output

Notion of algorithm
 Non-ambiguity requirement for each step of an
algorithm
 Range of inputs for which an algorithm works has
to be specified
 Same algorithm can be represented in several
different ways.
 Exist several algorithms for solving the same
problem.
 Algorithms for the same problem can be based on
very different ideas and can solve the problem
with dramatically different speeds.
1/23/2019 8

Understand the problem
Decide on: Computational means
Exact vs Approximate 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

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

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

2.2 Choosing between Exact and
Approximate Problem Solving
 Exact algorithm
 Approximation algorithm
 Extracting square roots,
 Solving nonlinear equations,
 Evaluating definite integrals
1/23/2019 12

2.3 Algorithm Design Technique
 An algorithm design technique
(“strategy” or “paradigm”)
General approach to solving problems
algorithmically that is applicable to a variety
of problems from different areas of
computing.
 Algorithm design techniques make it
possible to classify algorithms according to
an underlying design idea
1/23/2019 13

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 structures remain crucially
important for both design and analysis of
algorithms.
1/23/2019 14

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

4.Prove Correctness
To prove that the algorithm yields a
required result for every legitimate input in
a finite amount of time
 A common technique for proving correctness is to use
mathematical induction
 Tracing the algorithm’s performance 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

5.Analyze the Algorithm
 Efficiency
 Time efficiency,
How fast the algorithm runs,
 Space efficiency,
How much extra memory it uses.
Simplicity
Easier to understand and easier to program
Generality
Issues - Algorithm solves
Set of inputs it accepts
1/23/2019 17

6. Code the Algorithm
 Programming an algorithm
both a peril and an opportunity.
 Test and debug program thoroughly
whenever implement an algorithm.
 Implementing an algorithm correctly is
necessary but not sufficient
 An analysis is based on timing the
program on several inputs and then
analyzing the results obtained.
1/23/2019 18

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

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

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

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

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

2. Searching
 Deals with finding a given value, called a
search key, in a given set
(or a multiset, which permits several
elements to have the same value)
 Sequential Search or linear Search
 Binary search
1/23/2019 24

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

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

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

4. Graph Problems
 Collection of points called vertices,
 Some of which are connected by line
segments called edges.
 Used for modeling a wide variety of
applications
 Transportation,
 Communication,
 Social and Economic networks
 Project scheduling
 Games.
1/23/2019 28

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

Graph Problems
 Traveling Salesman Problem (TSP)
Problem of finding the shortest tour
through n cities that visits every city
exactly once.
 Route Planning
 Circuit board
 VLSI chip fabrication
 X-ray crystallography
 Genetic Engineering
1/23/2019 30

Graph Problems
 Graph-coloring problem
 seeks to assign the smallest number of
colors to the vertices of a graph so that
no two adjacent vertices are the same
color
Event Scheduling:
Events are represented by vertices that are connected
by an edge if and only if the corresponding events
cannot be scheduled at the same time, a solution to the
graph-coloring problem yields an optimal schedule.
1/23/2019 31

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

5. Combinatorial Problems
 Issues
 Number of combinatorial objects typically grows
extremely fast with a problem’s size, reaching
unimaginable magnitudes even for moderate-
sized instances.
 There are no known algorithms for solving most
such problems exactly in an acceptable amount
of time.
1/23/2019 33

6.Geometric Algorithms
 Geometric algorithms deal with geometric
objects such as points, lines, and polygons.
 Ancient Greeks -developing procedures
For solving a variety of geometric problems,
 Constructing simple geometric shapes
-triangles, circles
 Computer graphics
 Robotics
 Tomography
1/23/2019 34

6.Geometric Algorithms
 Closest-pair problem
Given n points in the plane, find the closest
pair among them.
 Convex-hull problem
To find the smallest convex polygon that
would include all the points of a given set.
1/23/2019 35

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

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

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, selection subsets
hierarchy, ancestor/descendants, taxonomy trees
network, circuit, web, relationship graph
sites, positions, locations points
shapes, regions, boundaries polygons
text, characters, patterns strings

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!

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

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

Design and analysis of algorithms

Recommended

Recommended

More Related Content

What's hot

What's hot (20)

Similar to Design and analysis of algorithms

Similar to Design and analysis of algorithms (20)

More from Dr Geetha Mohan

More from Dr Geetha Mohan (13)

Recently uploaded

Recently uploaded (20)

Design and analysis of algorithms