Scribd
Upload
89 views12 pages

B.Bhuvaneswaran, AP (SG) / CSE, REC: 13 January 2022

The document discusses algorithms and their analysis. It introduces key characteristics of algorithms like input, output, definiteness, finiteness, and effectiveness. It also discusses analyzing algorithm complexity through asymptotic analysis and recurrence relations.

Uploaded by

bhuvangates
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
89 views12 pages

B.Bhuvaneswaran, AP (SG) / CSE, REC: 13 January 2022

The document discusses algorithms and their analysis. It introduces key characteristics of algorithms like input, output, definiteness, finiteness, and effectiveness. It also discusses analyzing algorithm complexity through asymptotic analysis and recurrence relations.

Uploaded by

bhuvangates
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 12

Introduction

B.Bhuvaneswaran, AP (SG) / CSE, REC

13 January 2022

B.Bhuvaneswaran, AP (SG) / CSE, REC 1


Unit-I
 Introduction: Characteristics of Algorithm. Analysis of Algorithm:
Performance Measurements of Algorithm, Time and Space Trade-
Offs, Asymptotic analysis of Complexity Bounds - Best, Average
and Worst-Case behaviour; Analysis of Recursive Algorithms
through Recurrence Relations: Substitution Method, Recursion
Tree Method and Masters’ Theorem.

B.Bhuvaneswaran, AP (SG) / CSE, REC 2


Text Books
 Fundamental of Computer Algorithms, E. Horowitz and S. Sahni.
 The Design and Analysis of Computer Algorithms, A. Aho, J.
Hopcroft and J. Ullman.

B.Bhuvaneswaran, AP (SG) / CSE, REC 3


Reference Books
 Introduction to Algorithms, T. H. Cormen, C. E. Leiserson and R. L.
Rivest.
 Computer Algorithms: Introduction to Design and Analysis, S.
Baase.
 The Art of Computer Programming, Vol. 1, Vol. 2 and Vol. 3, .D. E.
Knuth.

B.Bhuvaneswaran, AP (SG) / CSE, REC 4


What is an Algorithm?
 An algorithm is a finite set of instructions that, if followed,
accomplishes a particular task.
 In addition, all algorithms must satisfy the following criteria:
– Input
– Output
– Definiteness
– Finiteness
– Effectiveness

B.Bhuvaneswaran, AP (SG) / CSE, REC 5


Input
 Zero or more quantities are externally supplied.

B.Bhuvaneswaran, AP (SG) / CSE, REC 6


Output
 At least one quantity is produced.

B.Bhuvaneswaran, AP (SG) / CSE, REC 7


Definiteness
 Each instruction is clear and unambiguous.

B.Bhuvaneswaran, AP (SG) / CSE, REC 8


Finiteness
 If we trace out the instructions of an algorithm, then for all cases,
the algorithm terminates after a finite number of steps.

B.Bhuvaneswaran, AP (SG) / CSE, REC 9


Effectiveness
 Every instruction must be very basics so that it can be carried out,
in principle, by a person using only pencil and paper.
 It is not enough that each operation be definite as in criterion3; it
also must be feasible.

B.Bhuvaneswaran, AP (SG) / CSE, REC 10


Queries…?
Thank You…!

You might also like