** **

**DESIGN ****AND ****ANALYSIS ****OF ****ALGORITHM **

**SE****T ****– ****I **

**Problem ****to ****Program **

**Introduction **

1 – 2

**Performance ****Evaluation **

2-7

**Sorting ****Problem **

**7 ****– ****18 **

**Mathematical ****Preliminaries **

**18 ****– ****20 **

**Asymptotic ****Notation **

**21 ****– ***27 *

**Key **

**28 **

Grades

** **

** **

**DESIGN ****AND ****ANALYSIS ****OF ****ALGORITHM **Tic

**1****.****PROBLEM****TO****PROGRAM**

**Mathematical **

**Model ****Informal ****a lgorithm **

**Abstract ****Data ****Type **

*(***A****D****T****) ****Ps****e****udo ****Lang****u****a****g****e **

**C****o****de **

p

**Data ****Structure **

(DS) **Program ****(****C****–****P****r****ogram) **

program

1) Model the problem using an appropriate mathematic model (Informal algorithm)

2) The informal algorithm is written in pseudo language

3) The stepwise refinement of pseudo language gives various types of data used and Operations to be performed on data. (i.e., data type)

4) We create ADT for each data type.

5) We choose an appropriate Data Strucure to imp__lemen__t eachzADI

6) Finally replace informal statements in pseudo language code by C-__code __

**An ****algorithm **is a finite sequence of computational steps that transform the input into the output in finite number of steps

**A ****data ****type **is a collection of objects and a set of operati__ons __that act on those objects

An **a****bstract ****d****ata ****t****yp****e ****(****ADT**) is a data type, that is organized in such a way that the specification of the objects and the operations on the objects is separated from the representation of the objects and the implementation of the operation. **ADT ****is ****mathematical ***m***ode****l ****of ****data ****type **

**A ****dat****a ****structure****(****DS**) is a way to store and organize data in order to facilitate access and modifications. No single data structure works well for all purposes, and so it is important to know the strengths and limitations of several of them. *W*e use DS to implement ADT:

**Pseudo ****cod**e: Mixture of natural language and high level programming language constructs that describes algorithm

**A ****program **is an expression of an a__l__gorithm in a programming language

**2****.****INTRODUCTION**- 1. Non-Co
**mputational****problem**

A problem that has no precise and simple specification __Example____: __Convince your boss for salary hike; convince your faculty for marks.

**2****.****Computational****problem**

Specification of input

Specification output as function of input

__Exampl____e__: The sorting problem__: __

**Input**: a sequence <al, a2……,an> of n numbers. **Output**: a permutation <al, a2,…, an > of the input with al <= a2 <= …. <= an .

** **

RU DESI*GN *AND AN**ALYSIS ****OF ****ALGOR ITHM **

**3****.****A**__lg__orithm Definition

An Al__g__orithm is well-defined computational procedure that takes some value, or set of values as input and produces some value, or set of values as output.

**Instanc**e: A particular input called an **instance **of a computational problema __Exampl____e__: The input sequence <31, 41, 59, 26, 41 58> is an instance of the sorting problem.

**4****.****Algorithm****Characteristics**

All a__lg__orithms should satisfy the following criteria. **Input**: Zero or more quantities are externally supplied. A **Output**: At least one quantity-is, produced. **Definitene****s****s**: Each instruction is clear and unambiguous. **Finitene****s**s: For all cases, the algorithm terminates after a finite number or *s***teps****. ****Effectiveness**: instruction is basic enough to be carried out.

**Definition**: Algorithms that are definite and effecti*v*e are called **computational ****pr****oced****ures **__Example____: __Digital computer.

**Definition**: An algorithm is said to þe correct if, for every input instance, it halts with the correct output.

**Turn ****TTELU **

T

ERME.

**

IEEE!!!

- 5. The study of A
**lgorithm****includes****the****foll**owing-im**portant****areas**

!!

.

.

HU

!!BELI

**Desig****n ****an ****a lg**orithm: Creating and algorithm is an art which may never be fully automated, Different design strategies: Divide and Conquer, Greedy, Dynamic programming….etc.

**Express**

**an**

**algo**rithm: A

__l__gorithm specification using Pseudo code.

**Validat**

**e**

**an**

**algo**rithm (correctness): To show that algorithm computes the correct answer for all possible legal inputs,

**Analysis**

**an**

**algo**rithm: Find the time

__a__nd space

__com__plexity. Prove that we cannot solve the problem any faster using asymptotic analysis

**Implementati**on : Implementing algorithm in a pro

__g__ramming language

**Verification**:-Test the program (debugging and profi

__ling__)

- 3. PERFORMANCE EVALUATION
**1****.****Performance****evaluation**

As an algorithm is executed, it uses the computers CPU to perform operations and its memory to hold the program and data. **An ****efficient algorithm **

needs less running time

- uses less space 1.1. Space Complexity: The space complexity of an algorithm is the amount of memory if

needs to run to completion. 1.2. Time Complexity: The time complexity of an algorithm is the amount of computer time it

needs to run to completion. 1.3. **Performance ****evaluation **of an algorithm refers to the task of computing space and time

complexity of an algorithm **1****.****4 ****Performance ****evaluation **can be loosely divided into two major phases:

1) a priority **estimates ****(****Performance ****Analysis****) **

1 Uses analytical methods

- Machine independent

** **

** **

**DESIGN ****AND AN ALYSIS **

**OF ALGORITHM**

2). **a ****posterior ****testing ****(****Performance ****Measurement or prof**iling):

. It is the process of executing a correct program on data sets and measuring time

and space it takes to compute results

1 Machine dependent Perform**ance Analysis ****is ****general ****methodo**logy because

- It uses high level description of an algorithm (Pseudo-code)

All possible input instances are taken into account

- Machine independent

**2****.****Space****complexity**

**2****.****1 ****Components ****of ****s****p****ace ****complexity **

**Instruction ****spa****c****e****: **

Space needed for code

**Data ****Space****: **

- i. Space needed for constants and simple variables ii. Space needed for dynamically allocated objects (such as arrays, structures, etc)
**Environment****stack****space:** - i. It is used to save information needed to resume execution of partially executed function. ii. Each time a function is invoked the following data are saved on the environment stack

The return address The values of local variables and formal parameters

**Recursion ****stac****k ****s****pac****e**: Amount of stack space needed by recursive functions is called recursion stack space. It depends on

- Space needed by local variables and formal parameters
- Maximum depth of recursion (i.e., maximum number of nested recursive calls)
- Compiler being used
**T****h****e****total****s****p****ace**needed by a program is divided into two parts:

- 1. Fixed Part 2. Variable Part

**A ****fixed ****p**art independent of instance characteristics (e.g., size, number, value) 1. Instruction space 2. Data space (space needed for constants and simple variables and some dynamically

allocated objects) **Note**: The space needed by some of the dynamically allocated memory may also

be independent of problem size 3. Environment stack space for non-recursive functions

*A **v***ariable ****pa**rt dependent on instance characteristics

- 1. Dynamically allocated space 2. Recursion stack space

**2****.****2 ****D**efinition

**The ****space ****comp**lexity S (P) of any a__l__gorithm P can be written as

S (P) = C + Sp(I) C constant that denotes fixed part Sp Variable part that depends on instance characteristics (I) (e.g., size, number, value)

** **

** CRMD ****ANALYSI****S ****OF ****ALG ORITHM **

2.3 Examples

- 1.

A__lg__orithm abc(a, b, c)

return a + b + b**c**/*(a+b+4.0);

Sp(abc) = 0

C = Space needed for a, b, cand result;

- 2.

A__l__gorithm Sum(a, n)

S = 0; for(i = 1 to n)

S = s + a[i]; return s;

Space required for

**f**ormal parameters a and n

local variables s, i and constant 0

- instruction space. This amount of space needed does not depend on value of n.

Ssum(n) = 0 Since a is actually the address of the first element in a[](i.e., a[0]), the space needed by it is also constant

A__l__gorithm rsum(int a[], int n)

if(n>0)

return rsum(a, n-1)+a[n-1]; return 0;

Let reference of a = 4bytes; value of n = 4 bytes; return address = 4 bytes are stored on recursion stack for each recursion call. Each recursive call require 12 bytes Depth of recursion = (n+1) recursion stack space = 12(n+1) Sisum(n) = 12 (n+1)

**3****.****Time****Complexity**

**3****.****1 ****Time ****Complexity **

Time taken by a program P is sum of compile time and runtime

T(P) = C + TP(I) C (compile time) is independent of instance characteristics (*.*. constant) TP(I) (Run time) is dependent on instance characteristics.

(i) However, **analytical ****approach ****to ****determine ****the ****exact ****runtime ****is ****complicated **

Since runtime depends on machine dependent issues like i) Type of processor, ii) Access

rate (rate*/*write operations), iii) Architecture and machine independent issue iv) input size. **(****ii****) ****Run ****time ****expression ****should ****be ****machine****–****inde****pe****n****d****ent****. **

Therefore, **we ****estimate ****runtime ****as ****function ****of ****input ****size**. i.e., we find rate of growth of time with respect to input size.

Running time = f(input size)

## Download Algorithm Notes PDF