Slide 1: Design & Analysis of Algorithm
Prof.T. Arivanantham,B.E.,M.S.,
Lecturer
The Computer as a Tool : The Computer as a Tool Much like the microscope does not define biology or the test tube does not define chemistry, the computer doesn't define Computer Science.
The computer is a tool by which Computer Scientists accomplish their goals – to solve problems.
What is Computer Science? : What is Computer Science? NOT about coding or hardware or software!
Computer Science is about PROBLEM SOLVING
Computer Science is about DEVELOPING ALGORITHMS to solve complex problems
What is an Algorithm? : What is an Algorithm? An algorithm is a well-developed, organized approach to solving a complex problem.
Computer Scientists ask themselves four critical questions when they evaluate algorithms …
Algorithm Questions : Algorithm Questions Does the algorithm solve the stated problem?
Is the algorithm well-defined?
Does the algorithm produce an output?
Does the algorithm end in a reasonable length of time?
Developing an Algorithm : Developing an Algorithm Identify the Inputs
Identify the Processes
Identify the Outputs
Develop a HIPO Chart
Identify modules
1. Identify the Inputs : 1. Identify the Inputs What data do I need?
How will I get the data?
In what format will the data be?
2. Identify the Processes : 2. Identify the Processes How can I manipulate data to produce meaningful results?
Data vs. Information
3. Identify the Outputs : 3. Identify the Outputs What outputs do I need to return to the user?
What format should the outputs take?
4. Develop a HIPO Chart : 4. Develop a HIPO Chart Hierarchy of Inputs Processes & Outputs
5. Identify Relevant Modules : 5. Identify Relevant Modules How can I break larger problems into smaller, more manageable pieces?
What inputs do the modules need?
What processes need to happen in the modules?
What outputs are produced by the modules?
Summary : Summary The goal of Computer Science is to develop sound algorithms for solving complex problems.
An algorithm is a well-developed, detailed approach for solving a problem.
Criteria for Algorithms : Criteria for Algorithms Input :Zero or more quantities
are externally supplied.
Output :At least one quantity is
produced.
Definiteness :Each instruction is clear
and unambiguous.
Finiteness :it terminates after a finite
number of steps.
Effectiveness : clear and feasible.
Study of Algorithms : Study of Algorithms How to devise algorithms
How to validate algorithms
How to analyze algorithms
How to test a program
How to devise algorithms : How to devise algorithms Something of an art form.
Cannot be fully automated.
We will describe some general techniques and try to illustrate when each is appropriate.
How to validate algorithms : How to validate algorithms It computes the correct answer for all
possible legal inputs.
Proving an algorithm generates correct
output for all inputs.
How to analyze algorithms : How to analyze algorithms The “process” of determining how much resources (time, space) are used by a given algorithm
We want to be able to make quantitative assessments about the value (goodness) of one algorithm compared to another
We want to do this WITHOUT implementing and running an executable version of an algorithm
Question: How can we study the time complexity of an algorithm if we don’t run it or even choose a specific machine to measure it on?
How to test a program : How to test a program It consists of two phases
Debugging: is a methodical process of finding and reducing the number of bugs, or defects, in a computer program
Profiling (Performance Measurement): is the process of executing a correct program on data sets and measuring the time and space it takes to compute the results.
Algorithm Specification : Algorithm Specification Pseudo code Conventions
Recursive Algorithms
Pseudo code Conventions : Pseudo code Conventions
Recursive Algorithms : Recursive Algorithms A recursive algorithm is an algorithm which calls itself with "smaller (or simpler)" input values, and which obtains the result for the current input by applying simple operations to the returned value for the smaller (or simpler) input.
Example:
int factorial(int n)
{
if (n == 0) return 1;
else return (n * factorial(n-1));
}
Performance Analysis : Performance Analysis Space Complexity
Time Complexity
Space Complexity : Space Complexity Space complexityis also important: This is essentially the number of memory cells which an algorithm needs. A good algorithm keeps this number as small as possible
Time Complexity : Time Complexity The number of (machine) instructions which a program executes during its running time is called its time complexity in computer science.
Measuring Complexity Again : Measuring Complexity Again The worst case running time of an algorithm is the function defined by the maximum number of steps taken on any instance of size n.
The best case running time of an algorithm is the function defined by the minimum number of steps taken on any instance of size n.
The average-case running time of an algorithm is the function defined by an average number of steps taken on any instance of size n.
Best, Worst, and Average Case : Best, Worst, and Average Case
Asymptotic Notations : 27 Asymptotic Notations A way to describe behavior of functions in the limit
Abstracts away low-order terms and constant factors
How we indicate running times of algorithms
Describe the running time of an algorithm as n grows to
O notation:
notation:
notation: asymptotic “less than”: f(n) “≤” g(n) asymptotic “greater than”: f(n) “≥” g(n) asymptotic “equality”: f(n) “=” g(n)