Overview of algorithm

• To apply algorithm first of all there should be a problem

that needs solution
– Is there any problem for which we can’t design algorithm?

– Program = Algorithm + Data Structure

1
 What is an algorithm?
• An algorithm is a clearly specified set of simple
instructions to be followed to solve a problem
• Any well-defined computational procedure that takes some
value (or set of values) as an input and produces some
value (or set of values) as an output
• A sequence of computational steps that transforms the
input into the output
• A set of well-defined, finite rules used for problem solving
• A finite set of instructions that, if followed, accomplishes a
particular task
• It is a precise, systematic method for producing a specified
result
2
 What is an algorithm?
• An algorithm is a sequence of unambiguous
instructions for solving a problem, i.e., for
obtaining a required output for any legitimate
input in a finite amount of time

• From the above definition, algorithm has the

following five properties: Sequence,
Unambiguous, Input, Output, Finite
3
Properties of an algorithm: Sequence
• It is a step-by-step procedure for solving a given
problem
• Every algorithm should have a beginning (start)
and a halt (end) step
• The first step (start step) and last step (halt step)
must be clearly noted
• Between the two every step should have
preceding and succeeding steps
• That is, each step must have a uniquely defined
preceding and succeeding step
4
Properties of an algorithm: Unambiguous
• Define rigorously the sequence of operations performed
for transforming the inputs into the outputs
• No ambiguous statements are allowed: Each step of an
algorithm must be clearly and precisely defined, having
one and only one interpretation.
• At each point in computation, one should be able to tell
exactly what will happen next
• Algorithms must specify every step. It must be composed
of concrete steps
• Every detail of each step must be spelled out, including
how to handle errors
• This ensures that if the algorithm is performed at
different times or by different systems using the same
data, the output will be the same. 5
Properties of an algorithm: Input specified
• The inputs are the data that will be transformed
during the computation to produce the output
• An input to an algorithm specifies an instance of the
problem the algorithm solves
• Every algorithm should have a specified number
(zero or more) input values (or quantities) which are
externally supplied
– We must specify the type of data and the amount of data
• Note that, correct algorithm is not one that works
most of the time but one that works correctly for all
legitimate inputs
6
Properties of an algorithm: Output specified
• The output is the data resulting from the computation
– It is the intended result

• Every algorithm should have one or a sequence of

output values
–There must be one or more result values
• A possible output for some computations is a
statement that there can be no output, i.e., no solution
is possible
• The algorithm can be proved to produce the correct
output given a valid input.
7
Properties of an algorithm: Finiteness
• Every valid algorithm must complete or terminate
after a finite number of steps.
• If you trace out the instructions of an algorithm, then
for all cases the algorithm must terminate after a
finite number of steps
– It must eventually stop either with the right output or with a
statement that no solution is possible
• Finiteness is an issue for computer algorithms
because
– Computer algorithms often repeat instructions
– If the algorithm doesn’t specify when to stop, the computer
will continue to repeat the instructions forever 8
 Why need algorithm analysis ?
• There are many ways to solve a given problem
– So writing a working program to solve a problem is
not good enough
• The program may be inefficient and/or
incorrect!
• If the program is run on a large data set, then
the running time becomes an issue
• Always we have to undertake algorithm
analysis before implementation
• Example: Selection Problem
– Given a list of N numbers, determine the kth
largest, where k  N.
 Example: Selection Problem
• Algorithm 1:
(1) Read N numbers into an array
(2) Sort the array in decreasing order by
some simple algorithm
(3) Return the element in kth position
 Example: Selection Problem…
• Algorithm 2:
(1) Read the first k elements into an array and
sort them in decreasing order
(2) Each remaining element is read one by one
– If smaller than the kth element, then it is ignored
– Otherwise, it is placed in its correct spot in the
array, bumping one element out of the array.
(3) The element in the kth position is returned as
the answer.
 Example: Selection Problem…
• Which algorithm is better when
– N =100 and k = 100?
– N =100 and k = 1?
• What happens when N = 1,000,000 and k
= 500,000?

• Which one is an efficient algorithm?

Correct algorithm?
– Is there exist better algorithms?
 Algorithm Evaluation
Two main ways:
• The Efficiency of the algorithm
– determination of the number of resources necessary to
execute it, such as
• the number of steps or iterations (time complexity) or
• storage locations (space complexity).
– the efficiency or running time of an algorithm is stated
as a function relating the input length to time and
storage requirement
• The Correctness of the algorithm
– We only analyze the efficiency of correct algorithms
13
 Correct Algorithm
• A correct algorithm solves the given computational
problem
– If the algorithm is not doing what it is supposed to do, it is
worthless
• An algorithm is said to be correct if, for every input
instance, it halts with the correct output
• An incorrect algorithm
–might not halt at all on some input instances, or
–might halt with a wrong answer.
• In order to show that an algorithm is incorrect, you need
just one instance of its input for which the algorithm fails
• How to prove the correctness of an algorithm ?
– Common techniques are by mathematical induction & contradiction
14