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

More Related Content

What's hot

Similar to Design and analysis of algorithms

More from Dr Geetha Mohan

Recently uploaded

In this document

Design and analysis of algorithms