# DAA Introduction

Views:

Category: Education

## Presentation Description

No description available.

By: raj_mahesh123 (122 month(s) ago)

By: babyricha (124 month(s) ago)

## Presentation Transcript

### 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)