design and analysis of algorithm

DESIGN AND ANALYSIS OF ALGORITHMS
Prepared by
R.Cheran [M.Sc. computer science]

, SYLLABUS

UNIT -I: ALGORITHM AND ANALYSIS

What is an Algorithm? - Algorithm Specification- Performance Analysis-
Randomized Algorithms.

UNIT - II: DIVIDE AND CONQUER

General Method - Binary Search - Finding the Maximum and Minimum-
Merge Sort - Quick Sort - Selection Sort- Stassen‟s Matrix
Multiplications.

UNIT - III: THE GREEDY METHOD

The General Method - Knapsack Problem – Tree Vertex Splitting - Job
Sequencing with Deadlines - Minimum Cost Spanning Trees - Optimal
Storage on Tapes - Optimal Merge Pattern - Single Source Shortest Paths.

UNIT - IV: DYNAMIC POGRAMMING

The General Method – Multistage Graphs - All pair shortest path - String
Editing - 0/1 Knapsack – Reliability Design - The Traveling Salesperson
Problem

UNIT - V: TRAVERSAL, SEARCHING & BACKTRACKING

Techniques for Binary Trees- Techniques for Graphs - The General
Method - The 8-Queens Problem – Sum of Subsets- Graph Colouring-
Hamiltonian Cycles

, DESIGN AND ANALYSIS ALGORITHM


UNIT – I
.


ALGORITHM
Informal Definition:
An Algorithm is any well-defined computational procedure that takes some value
or set of values as Input and produces a set of values or some value as output. Thus algorithm is
a sequence of computational steps that transforms the i/p into the o/p.

Formal Definition:
An Algorithm is a finite set of instructions that, if followed, accomplishes a
particular task. In addition, all algorithms should satisfy the following criteria.

1. INPUT Zero or more quantities are externally supplied.

2. OUTPUT At least one quantity is produced.

3. DEFINITENESS Each instruction is clear and unambiguous.

4. FINITENESS If we trace out the instructions of an algorithm, then for all cases, the algorithm
terminates after a finite number of steps.

5. EFFECTIVENESS Every instruction must very basic so that it can be carried out, in principle, by a
person using only pencil & paper.

Issues or study of Algorithm:

 How to device or design an algorithm creating and algorithm.

 How to express an algorithm definiteness.

 How to analysis an algorithm time and space complexity.

 How to validate an algorithm fitness.

 Testing the algorithm checking for error.
Algorithm Specification:

Algorithm can be described in three ways.

1. Natural language like English:
When this way is choused care should be taken,
we should ensure that each & every statement is definite.

2. Graphic representation called flowchart:
This method will work well when the algorithm
is small& simple.

3. Pseudo-code Method:
In this method, we should typically describe algorithms as program,
which resembles language like Pascal & algol.

DESIGN AND ANALYSIS ALGORITHM CHERAN

, DESIGN AND ANALYSIS ALGORITHM



Pseudo-Code Conventions:

1. Comments begin with // and continue until the end of line.

2. Blocks are indicated with matching braces {and}.

3. An identifier begins with a letter. The data types of variables are not explicitly declared.

4. Compound data types can be formed with records. Here is an example,
Node. Record
{
data type – 1 data-1;
.
.
.
data type – n data – n;
node * link;
}

Here link is a pointer to the record type node. Individual data items of a record

can be accessed with and period.
5. Assignment of values to variables is done using the assignment
statement. <Variable>:= <expression>;

6. There are two Boolean values TRUE and FALSE.

Logical AND, OR, NOT
OperatorsRelation <, <=,>,>=, =, !=
al Operators
7. The following looping statements are employed.

For, while and repeat-until
While Loop:
While < condition > do
{
<statement-1>
.
.
.

<statement-n>
}

For Loop:

DESIGN AND ANALYSIS ALGORITHM CHERAN