Implementation of Algorithms

08.09.2025
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

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 is should do.
§ Similarly , to 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
complete? Is this complete?
Computing without computers, Paul Curzon
 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
possibilities.
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 deterministic?
Step 3: Return home
• 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.
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?
Termination

An algorithm should always

finish and produce a result
 Building blocks of
algorithm
§ Instructions/Statements
§ State
§ Control flow
§ Functions
20
21 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.
22 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.
23 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
24 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
25 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
26 3. Exact/approximate solution

Start Developing an algorithm

The algorithm must compute correct output for
all possible and legitimate inputs
T h i s s o l u t i o n c a n b e a n e x a c t s o l u t i o n o r
approximate solution
27 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
28 6. Methods of specifying an algorithm

A l g o r i t h m i s a s e q u e n c e o f s t e p s o r
instructions to implement a solution.
After writing an algorithm, it is specified
either using a natural language or
pseudocode or flowcharts.
29 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
30 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
31
developing an algorithm
32 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 algorithm. solve addition or
long division problems is
an algorithm

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

Vidhya. S (CSE)
34 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
35 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
36 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
37 Example
38  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
39 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 execut e o n e o r m o re st e ps u n t il so m e
condition is true.
Eg: Algorithm that prints the first 10 natural numbers
40 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
42 Recursion
43 Example
44
Flowchart
09.09.2025
45 Flowcharts
§ A flowchart is a graphical or symbolic representation of a process.
When designing a flowchart, each step in the process is depicted by
a different symbol and is associated with a short description.

§ A flowchart is a diagrammatic representation that illustrates the

sequence of steps that must be performed to solve a problem.

§ It is usually drawn in the early stages of formulating computer

solutions. It facilitates communication between programmers and
users.

§ Once a flowchart is drawn, programmers can make users

understand the solution easily and clearly.
46

Flowcharts is a graph used to depict or show a step by step solution

using symbols which represent a task.

The symbols used consist of geometrical shapes that are connected

by flow lines.

It is an alternative to pseudocoding; whereas a pseudocode

description is verbal, a flowchart is graphical in nature
47 Flowcharts
48 Contd…
49 Advantages
§ They are very good communication tools to explain the logic of
a system to all concerned.

§ They help to analyse the problem in a more effective manner.

§ They are also used for program documentation.

§ They direct the programmers to go from the starting point of the

program to the ending point without missing any step in
between. This results in error-free programs.

§ They help the programmers to easily detect, locate, and remove

mistakes in the program in a systematic manner.
50
Limitations
§ Drawing flowcharts is a difficult and a time-consuming activity.

§ Many a times, the flowchart of a complex program becomes complex

and clumsy.

§ At times, a little bit of alteration in the solution may require complete

redrawing of the flowchart.

§ The essentials of what is done may get lost in the technical details of
how it is done.

§ There are no well-defined standards that limit the details that must be
incorporated into a flowchart.
51 Pseudo code
52 Pseudocode
 Pseudocode is a compact and informal high-level description of an
algorithm that uses the structural conventions of a programming
language.

 It facilitates designers to focus on the logic of the algorithm without

getting bogged down by the details of language syntax.

 An ideal pseudocode must be complete, describing the entire

logic of the algorithm, so that it can be translated straightaway into
a programming language.
53 Pseudocode
It consist of short English phrases that explain specific
tasks within a program’s algorithm.

The sole purpose of pseudocodes is to enhance human

understandability of the solution.
54 Rules for writing Pesudo Code

Write one statement per line

Capitalize initial keywords
Indent to show hierarchy
End multiline structure
Keep Statements language independent
55 Contd…
Pseudo Code Looks like
56 Eg: Making a cup of tea
Organize everything together;

Plug in kettle;

Put teabag in cup;

Put water into kettle;

Wait for kettle to boil;

Add water to cup;

Remove teabag with spoon/fork;

Add milk and/or sugar;

Serve;
57 As a program
58 Contd…
 SELECTION
• What if we want to make a choice, for example, do we
want to add sugar or not to the tea?
• We call this SELECTION.

 So, we could state this as

59
Selection Loop
60 Contd…