Introduction

Example
 Take off
3

Check in baggage Immigration check Security check

Boarding
© Oxford University Press 2018. All rights reserved. Take off
4 Landing

Immigration check

Landing

Collect baggage
5 Algorithm - [Link] FLights - Airport

Input Process Output

▪ Add the number of Number of flights
▪ Number of Flights
flights landed to the currently in the
Landed
Initial number of airport
▪ Number of Flights flights in the airport
Took off
▪ Subtract the
▪ Initial Number of
number of flights
flights
that took off

01 02 03
6 Contd…

Input: Get data from the keyboard, a file, the network, or

some other device.

Process: is basically a sequence of computations to be

performed using some logic. This is also known as an
Algorithm. Different logic gives rise to different algorithm.

output: Display data on the screen, save it in a file, send it

over the network, etc.
7 Program and Programming

▪ In the airport there are many flights landing and many flights
taking off.
▪ Unlike road traffic, the flights don’t have direct information of
other flights around them
▪ ATC (Air Traffic Control) department at the ground gives
instructions to each flight on what it should do.
▪ Similarly , instructions given to the computer to accomplish
specific tasks.
▪ Such Instructions are Known as Program
▪ The act of creating a Program is known as Programming.
8 Algorithm, Flow chart, Pseudo-code,
Programming
Algorithm: Step- by-step procedure for solving a
task or a problem
Flowchart: Diagrammatic representation of
algorithm
Pseudo code: Representation of the algorithm in
a way that is in between a program and a
normal English.
Programming: Implementation of an algorithm
9
Algorithm
What is an algorithm?

• It is a step- by-step procedure for solving a task or a

problem.
• Algorithm is an ordered sequence of finite, well
defined, unambiguous instructions for completing a
task.
11 Need of Algorithm
To understand the basic idea of the problem.
To understand the flow of the problem.
To improve the efficiency of existing techniques.
To compare the performance of the algorithm with
respect to other techniques.
 Problem
Problem

Notation
of Algorithm
Algorithm

Input
Input Output
Output
13 Characteristics of an Algorithm

Precision: The instructions should be written in a precise

manner.
Uniqueness: The outputs of each step should be
unambiguous, i.e., they should be unique and only
depend on the input and the output of the preceding
steps.
Finiteness: Not even a single instruction must be
repeated infinitely.
14 Contd…
Effectiveness: The algorithm should designed in such a
way that it should be the most effective among many
different ways to solve a problem.

Input: The algorithm must receive an input.

Output: After the algorithm gets terminated, the desired

result must be obtained.

Generality: The algorithm can be applied to various set

of inputs.
Completeness
1. Go to shop
2. Buy Chocolate Muffins
3. Return home
• A set of instructions or algorithm is said
to be complete if it covers all
eventualities.
• It must tell you what to do whatever the
situation.
• What to do in all circumstances.
• If the shop does not have chocolate
muffins (which happens all too often).
• How do we make the instructions Is this
complete?
Computing without computers, Paul Curzon
complete?
 Completeness
Step 1: Go to shop
Step 2: If shop has Chocolate Muffins
then buy Chocolate Muffins
Else if the shop has Croissants
then buy Croissants
Else buy nothing
Step 3: Return home
• Provide instructions for each eventuality that might
arise.
• The important thing for completeness is to have the final
“catch-all” instruction.
• This tells what to do if none of the situations specified
actually happen: since we cannot easily list all
Determinism
Step 1: Go to shop
Step 2: If shop has Chocolate Muffins
then buy Chocolate Muffins
Step 2.1: Else if the shop has Croissants
then buy Croissants
Step 2.2: Else buy nothing
Is this
Step 3: Return home
deterministic?
• By DETERMINISTIC we mean that if the conditions
in which rules are followed are identical, then exactly
the same result will be obtained by following the
result.
• You can determine what the result will be in advance
if you know the rules and the conditions.
18 That’s a deterministic algorithm ✅
For a given shop (input), the steps and the outcome are
always fixed.
If the shop has Chocolate Muffins, you will always buy
them.
If not, but it has Croissants, you will always buy them.
If neither, you always buy nothing.
There’s no randomness or guessing involved.
👉 So the sequence of steps and the result are
predictable and repeatable every time with the same
input.

© Oxford University Press 2018. All rights reserved.

Determinism
Step 1: Go to shop
Step 2: If shop has Chocolate Muffins
then buy Chocolate Muffins
Step 2.1: Else if the shop has Croissants
then buy Croissants
Step 2.2: Else buy anything
Step 3: Return home

They are non-deterministic. What is the difference? The

catch-all rule gives scope for different things to happen,

Is this
deterministic?
20 Its Non Deterministic

If both Chocolate Muffins and Croissants

are available, the algorithm does not
guarantee which one you will buy.
The choice depends on randomness or
guessing, so the output may differ each
time even with the same shop (input).

© Oxford University Press 2018. All rights reserved.

Termination

An algorithm should always

finish and produce a result
 Building blocks of algorithm
▪ Instructions/Statements
▪ State
▪ Control flow
▪ Functions
22
23 Contd…
An algorithm starts from an initial state with some input.

The instructions/statements describe the processing that

must be done on the input to produce the final output
(the final state).

An instruction is a single operation which when executed

converts one state to other.
24 Contd…
In the course of processing, data is read from an input device, stored in
computer’s memory for further processing, and then the result of the
processing is written to an output device. The data is stored in the
computer’s memory in the form of variables or constants.

The state of an algorithm is defined as its condition regarding current values

or contents of the stored data.

The flow of control specifies the order in which individual instructions of an

algorithm are executed.
25 Different Approaches of Designing an
Algorithm
For a complex problem, its algorithm is often divided into smaller
units called functions(or modules).
This process of dividing an algorithm into modules/ functions is
called modularization.
Advantage of modularization:
Complex algorithm simpler to design and implement
Each function can be designed independently.
While designing one function, the details of other functions can be
ignored, thereby enhancing clarity in design which in turn simplifies
implementation, debugging, testing and overall maintenance of
algorithm
26 Algorithmic problem solving steps

Steps to be followed for designing an effective algorithm are

1. Understanding the problem
2. Determining the capabilities of the computational device
3. Exact/ approximate solution
4. Select the appropriate data structure
5. Algorithm design techniques
6. Methods of specifying an algorithm
7. Proving an algorithm correctness
8. Analysing the performance of an algorithm
27 2. Determining the capabilities of the
computational device
After understanding the problem, the
capabilities of computing device should
be known.
Type of architecture, speed, memory
availability of the device are noted
28 3. Exact/approximate solution

Start Developing an algorithm

The algorithm must compute correct output for
all possible and legitimate inputs
This solution can be an exact solution or
approximate solution
29 5. Algorithm design Techniques

Developing an algorithm may never be

fully automated.
Using design techniques, we can develop
new algorithms easily
Example: Divide and Conquer, dynamic
programming, greedy
30 6. Methods of specifying an algorithm

Algorithm is a sequence of steps or

instructions to implement a solution.
After writing an algorithm, it is specified
either using a natural language or
pseudocode or flowcharts.
31 7. Proving algorithms correctness

Writing an algorithm is not just enough

Need to prove that it computes solutions for
all possible inputs.
This process is called as algorithm validation
Algorithm validation ensures that algorithm
will works correctly irrespective of
programming language
32 8. Analysing the performance of
algorithms
When an algorithm is executed, it uses the computer’s resources like central
processing unit (CPU) to perform its operations and to hold the program
and data respectively.
An algorithm is analyzed to measure its performance in terms of CPU time
and memory space required to execute the algorithm.
This is a challenging task and is often used to compare different algorithms
for a particular problem.
The result of the comparison helps us to choose the best solution from all
possible solutions.
Analysis of the algorithm also helps us to determine whether the algorithm
will be able to meet any efficiency constraint that exists or not.
 Simple strategies for
33
developing an algorithm
34 Control Structures used in Algorithms

Main control structures are

Sequence
Decision
Iteration/Repetition
Recursion
 Algorithm example

A recipe for making The method you use to

food is an solve addition or
algorithm. long division problems is
an algorithm

Planning for
Sequence of steps to Steps used for a vacation trip
carry out a surgery surveillance

Vidhya. S (CSE)
36 Sequence
▪ Sequence means – each step of algorithm is executed
in the specified order.
▪ An Algorithm to add two numbers performs the steps in
a purely sequential order.
▪ Algorithm:
▪ Step 1: Start
▪ Step 2: Input first number as A
▪ Step 3: Input Second Number as B
▪ Step 4: Set Sum = A+B
▪ Step 5: Print Sum
▪ Step 6: End
37 Practice question
Write an algorithm for exchange the value of two variables
Step 1: Start
Step 2: Input a value for variable x
Step 3: Input a value for variable y
Step 4: perform temp=x
Step 5: x=y
Step 6: y= temp
Step 7: Print x and y
Step 8 : End
38 Decision
Decision Statements are used when the outcome of the process
depends on some condition.
For Eg. If x=y, then Print “EQUAL”. The general form of the if construct
can be given as
If Condition then process
A condition in this context is any statement that may evaluate either
to a true value or a false value. In the Preceding example, the
variable x can either be equal to y. It cannot be both true and false.
If the condition is true then the process is executed.
If condition
Then process 1
ELSE process 2
39 Example
40 Example: Algorithm to find the greatest of three numbers
Step 1: Start
Step 2: Read the three numbers A,B,C
Step 3: Compare A and B. If A is greater perform step 4 else perform step 5
Step 4: Compare A and C. If A is greater, output “A is greatest” else output “c
is greatest”
Step 5: Compare B and C. If B is greater, output “B is greatest” else output “c is
greatest”
Step 6: End
41
Repetition
Iteration or repetition: which involves executing one or
more steps for a number of times, can be implemented
using constructs such as the while loops and for loops.
These loops execute one or more steps until some
condition is true.
Eg: Algorithm that prints the first 10 natural numbers
42 Example
 Repetition/Looping/Iterative
•Iterative operations
• Perform “looping” behavior: repeating actions until a
continuation condition becomes false.
• Loop: The repetition of a block of instructions

Step 1: Start
Step 2: Initialize number=1
Step 3: Repeat
Step 3.1: Print the value of number.
Step 3.2: Let number =number + 1.
Step 4: Until number < 11.
Step 5. Stop
44 Recursion
45 Example