Design and Analysis of

Algorithm

Hilal Jan

Department of Computer Science

COMSATS University, Islamabad
The Role of
Algorithms in
Computing

Department of Computer Science

Motivating
Discussion
 Let us start with a basic question:
 Given a certain problem how will you solve
this through computer?
 By developing its algorithm
 Before a computer can perform a task, it must have
an algorithm that tells it what to do.
 The Role of Algorithms in Computing:
 An algorithm is a great problem-solving
tool(series of instructions to solve a
problem)

Department of Computer Science 3

Motivating
Discussion
 What is primary job of a software engineer?
 To develop a software
 What is software?
 Programs that run on a device(e.g., computer).
 What is program?
 Program = Data + Logic
Data

Department of Computer Science 4

Motivating
Discussion
 How do you write an efficient Program?
 Since a program consist of data and logic, so
the efficiency of a program depends on:
 How you specify your input?
 How you solve the given problem?

Department of Computer Science 5

Motivating
Discussion
 How to write an efficient Program?
 Since a program consist of data and logic, so
the efficiency of a program depends on:
How you specify your input?
 To specify input for efficient program, we choose
appropriate data structure.
 How you solve the given problem?
 To solve a given problem efficiently, we design
algorithm by selecting appropriate algorithmic
designing technique.
 Now we can redefine our definition of Program as:
 Program = Data Structure + Algorithm
Department of Computer Science 6
Motivating
Discussion
 Program = Data Structure + Algorithm
 So,
 A good understanding of algorithms is
essential for a good understanding of the
most basic element of computer science:
Programming.

Department of Computer Science 7

UP-
SHOT
 So, we can say:

Algorithms are fundamental to

computer science.
Computer science is the study of
problems, problem-solving, and
the solutions that come out of
the problem-solving process.
Given a problem, a computer scientist’s goal
is to develop an algorithm.
Department of Computer Science 8
Different Areas of an Algorithm
study
 The focus of this subject is :
1. How to design good algorithms?
 Designing an algorithm is an art which can never be
fully automated.
 This section includes study of different algorithm
design techniques which helps the designer to devise
new and helpful algorithms.
2. How to validate algorithms?
 Once an algorithm is devised, it is necessary to show
that it computes the correct answer for all possible
3.legal
How inputs.
to analyze algorithms?

 This section includes task of determining how much

computing time and storage an algorithm requires.
Department of Computer Science 05/14/25 9
Objectives of this course

 The course “Design and analysis of algorithms” has

essentially two objectives:
1. Familiarize students with existing algorithms
 This objective deals with analysis

2. To equip the students with the necessary tools,

techniques, and confidence required in solving
a non- textbook problem
 This objective concerned with the design of

algorithms

Department of Computer Science 05/14/25 10

What should you know to learn this
subject?

 As we may realize design anything such as

computers, cars, cloths is an art.
 In some sense we must be creative, but it can't
be taught, in other sense there are very well-
defined design techniques which are used for these
purposes.
 Our goal is to study these techniques and to apply
later in our life.
 Therefore, we need some prerequisites to study
these techniques. These are given as follows.
 Familiar with basic programming languages (such as C,
C++, Java etc.)
 Knowledge on data structure
 Some amount of knowledge on discrete mathematics
Department of Computer Science 05/14/25 11
Our journey(road map) towards these
objectives

Department of Computer Science

Our journey: PART 1 DESIGN
Fundamenta Concept, Properties, The Role of Algorithms in
ls of Computing, Algorithm Design & Analysis Process, CLO-1
Algorithmic Iterative Algorithm Design Issues, Top-Down
Problem Design, Design using Recursion.
Solving
Brute Force (BF) Designing Algorithms for Sorting problem,
Technique: Pattern Matching, Closest-Pair, and
Convex-Hull Problem.
Decrease and Designing Algorithm for Sorting Problem,
Conquer Technique: Graph Traversal, Topological Sorting,
Algorithms for Generating Combinatorial
Objects, Decrease by -a-Constant Factor
Algorithms, Variable Size Decrease
Algorithms.
Design Divide and Conquer Designing Algorithms for Sorting Problem,
Technique: Closest-Pair, Convex-Hull Problem, and
Paradigm Matrix Multiplication Problem.
Transform and Transformation to more convenient CLO-2
Conquer Technique: instance, Transformation to different
representation, and Problem Reduction.
Dynamic Component & Properties; Designing
Programming (DP) Algorithms for Edit Distance; Longest
Technique: Common Subsequence (LCS); Knapsack;
and Matrix Chain Multiplication Problems.
Department of Computer
Greedy Science
Approach: Coin Change Problem, and Algorithm for
Our journey: PART 2 ANALYSIS

Correctness of Pre-conditions, Post-conditions, Loop CLO 3

Algorithms Invariant, Correctness of Iterative &
Recursive Algorithms.
RAM Model, Asymptotic Notations, Worst, CLO 4

Analysis of Best & Average Case Behavior of

Algorithm Algorithms; Complexity Classes; Solving
Recurrence Relations: Substitution
Method, Recurrence Tree Method, Master
Method and Time & Space Tradeoffs.
Computability Computability: The Complexity Classes P & CLO 5
NP; and Introduction to NP Complete
Problems.

Department of Computer Science

Assessment Plan
Assessmen
CLO-1 CLO-2 CLO-3 CLO-4 CLO-5
t Tools
Quizzes Quiz 1 Quiz 2 Quiz 3 Quiz 4
Assignmen Assignment Assignment
Assignment 4
ts 1&2 3
Mid Term Mid Term Mid Term
- -
Exam Exam Exam
Final Term
Final Term Exam
Exam
Blooms
Sr.# Course Learning Outcomes Taxonomy
Learning Level
Demonstrate fundamental concepts of and algorithm
CLO-1 Understanding
along with an algorithmic approach to a given problem.
Design new algorithms for different computational
CLO-2 Creating
problems.
Prove correctness of an algorithm using loop invariant
CLO-3 Applying
and induction.
Analyze best, average, and worst-case behaviors of an
CLO-4 Analyzing
algorithm.
Explain the concept of various complexity classes with
CLO-5of Computer Science
Department Understanding
15
examples.
Logistics
 Web: CUOnline
 Textbook: See next slide
 Grading on 100

Assignme Mid Term Terminal

Quizzes Total
nts Exam Exam
15 10 25 50 100
 Keys to success
 Don’t absent in class(80% Attendance)
 Respect due date(Submit your assignment on due
date,10% marks will be deducted on late submission)
 Start early, Don’t fall behind, Seek help from
Instructor
 Don’t cheat
Department of Computer Science
Text
Books

Department of Computer Science

Reference
Books

Department of Computer Science

Reference
Books

Department of Computer Science

Let us Start our
Journey

Department of Computer Science

Lecture No 1

Introduction

(What, Why and Where. . .)

Department of Computer Science 21

ORIGION/
HISTORY

Department of Computer Science

Origin of word:
Algorithm
 The term algorithm is a corruption of the
name of the muslim author Abu Ja’far
Mohammad ibn Musaal-Khowarizmi.
 Originally, the word algorism
was used for the rules for
performing arithmetic using decimal
notation.
 Much of al-Khwarizmi’s work was written in a
book titled al Kitab al-mukhatasar fi
hisab al-jabrwa’l-muqabalah

Department of Computer Science

Algorithm
 An algorithm is an exact specification of how to solve
a computational problem
 Algorithms are the threads that tie together most of
the subfields of computer science.
 Something magically beautiful happens when a
sequence of commands and decisions is able to
marshal a collection of data into organized
patterns or to discover hidden structure.
Donald Knuth

Department of Computer Science

CONCEPT
WHAT

Department of Computer Science

Algorithms: Informal
Introduction
Recipe for baking a cake….
Ingredients: Input

2 sticks butter
 2 cups flour
 1 cup sugar
 4 eggs
 1 cup milk
 1 tsp baking powder
 Cocoa powder (1/2 pound)

Procedure:Metho
Mix the sugar,d baking powder and flour, mix in
beaten eggs, melted butter and bake at 325F for
40 mins.
Outpu
Result:t
Department of Computer Science
What is
Algorithm?
 What is binary equivalent of decimal integer
75?
 1001011
 How can we convert this number into its
binary equivalent?
 We have a procedure for this.
 Let us see how we convert 75 into binary

Department of Computer Science

Convert 75 to
binary
2 75 remainder
2 37 1
2 18 1
2 9 0
2 4 1
2 2 0
2 1 0
0 1

1001011
Department of Computer Science
Procedure for Decimal to Binary
conversion
1. Write the decimal number
2. Divide by 2; write quotient and remainder
3. Repeat step 2 on the quotient; keep on repeating until
the quotient becomes zero
4. Write all remainder digits in the reverse order (last
remainder first) to form the final result
 What is it?
 A procedural solution to given problem
 Briefly speaking, algorithms are
procedural solutions to problems
 Algorithms are not answers, but rather
precisely defined procedures for getting
answers. (e.g., sorting 3 numbers)
Department of Computer Science
Formal
Definition

Department of Computer Science

What is
Algorithm?
 An algorithm is a well-defined computational
procedure that takes some value or set of
values (collection of elements) as input and
produces some value or set of values(collection
of elements) as output.

 A computer algorithm is a detailed step-by-step

method for solving a problem by using a
computer.

Department of Computer Science

What is
Algorithm?
 An algorithm is a sequence of unambiguous
instructions for solving a computational
problem, i.e., for obtaining a required output for
any legitimate input in a finite amount of time.

proble
m

algorithm

input “compute output

r”

Department of Computer Science

Example: Largest integer among five
integer

Is there a
relationship
between input
and output?

Department of Computer Science

Defining actions in FindLargest
algorithm

L
o
g
i
c

Algorithm= Data +
Logic

Department of Computer Science

FOOD FOR
THOUGHT

 What is the difference between a

RECIPE and an ALGORITHM

Department of Computer Science

Does a problem have unique solution or
multiple?
 Statement of problem:
 Input: a sequence of N numbers <a1, a2, …, aN>
 Output: a reordering of the input sequence <a’ 1,
a’2, …, a’N> so that a’i ≤ a’j whenever i < j
 Instance: the sequence <5, 3, 2, 8, 3> becomes
<2, 3, 3, 5, 8> after sorting
 Algorithms:
 Bubble Sort
 Selection sort
 Insertion sort
 Merge sort
 Quick sort and many more

Department of Computer Science

UP-
SHOT
 For each problem or class of problems,
there may be many different algorithms.

Department of Computer Science

BUILDING
BLOCKS/
THREE
CONSTRUCTS
Department of Computer Science
Three
Constructors

Department of Computer Science

CHARACTERISTICS
OF
ALGORITHM

Department of Computer Science

Characteristics of an
Algorithm
 Not all procedures can be called algorithms.
 An algorithm should have the following characteristics
 Input: An algorithm must take zero or more inputs
values from a specified set.
 Output: From each set of input values an algorithm
produces output value(s) from a specified set.
 Definiteness/precision: The steps to be performed
in the algorithm must be clear and unambiguous.
 Determinism: The intermediate results of each step
of execution are unique and are determined only by
the inputs and results of the preceding steps.
 Correctness: An algorithm should produce the
correct output values for each set of input values.

Department of Computer Science

Characteristics of an
Algorithm
 Finiteness: An algorithm should produce the
desired output after a finite number of steps for
any input in the set.
 Generality: The procedure should be applicable
for all instances of the given problem, not just for
a particular set of input values.

Department of Computer Science

EXAMPLES

Department of Computer Science

Examples: Characteristics of
Algorithm
 Determine which characteristics of an algorithm
input, output, precision, determinism, finiteness,
correctness, generality the following procedure have
and which it lack.
 Procedure:
 Step 1: Find prime factors of m
 Step 2: Find prime factors of n
 Step 3: Identify all common prime factors of m and n (if p is a prime factor
occurring pm and pn times in m and n, it should be repeated min{pm, pn} times)
 Step 4: Compute product of all common factors and return product as the
answer.

Department of Computer Science

Examples: Characteristics of
Algorithm
 Procedure:
 Step 1: Find prime factors of m
 Step 2: Find prime factors of n
 Step 3: Identify all common prime factors of m and n (if p is a prime factor occurring p m and pn times in m and n, it
should be repeated min{p m, pn} times)
 Step 4: Compute product of all common factors and return product as the answer.
 Input(Y/N)
 Yes: Because two nonnegative, not-both-zero integers m and n are given.
 Output(Y/N):
 Yes: Because procedure return product of all the common factors as the GCD of m and n.

Department of Computer Science

Examples: Characteristics of
Algorithm
 Procedure:
 Step 1: Find prime factors of m
 Step 2: Find prime factors of n
 Step 3: Identify all common prime factors of m and n (if p is a prime factor occurring pm and pn times in m and n, it should
be repeated min{pm, pn} times)
 Step 4: Compute product of all common factors and return product as the answer.
 Determinism(Y/N)
 No : Because the prime factorization steps(Step 1 and 2) are defined ambiguously: they
require a list of prime numbers, and we did not explain how to obtain such a list.
 Step 3 is also not defined clearly enough. Its ambiguity is much easier to rectify than that of
the factorization steps, however. How would you find common elements in two sorted lists?

Department of Computer Science

Examples: Characteristics of
Algorithm
 Procedure:
 Step 1: Find prime factors of m
 Step 2: Find prime factors of n
 Step 3: Identify all common prime factors of m and n (if p is a prime factor occurring pm and pn times in m and n, it should be repeated min{pm, pn}
times)
 Step 4: Compute product of all common factors and return product as the answer.
 Finiteness (Y/N)
 Yes : Because in order to find prime factors pi in step 1, we perform at most iterations and in step 2 we do
at most iterations.
 Correctness (Y/N)
 Yes : Because it produces correct output against legitimate input
 Generality(Y/N)
 Yes: Because it can find GCD of any two positive integers

 m
 n

Department of Computer Science

Examples: Characteristics of
Algorithm
 Determine which characteristics of an algorithm
the following procedure have and which it lack.
Procedure 1 double(n)
// The purpose of this procedure is to double a positive integer
while n > =0 do
n 2n
Input: Yes, since n is a positive number,
Finiteness: No, the while loop in this procedure
will run forever, therefore this procedure is not
finite.
Modify above procedure so that they satisfies all
the properties
ALGORITHM 1 double(n)
//Input: positive integer n
n 2n
Department of Computer Science
return n
Examples: Characteristics of
Algorithm
 Determine which characteristics of an algorithm the
following procedure have and which it lack.
Procedure 2 sum(n:positive integer)
// The purpose of this procedure is to find the sum of n integers.
sum = 0
while i < 10 do
sum sum + i
 The value  of i is never set in the procedure, so the given
procedure lacks definiteness. Without knowing the initial value
of i, the behavior of this algorithm is undetermined.
 Modify above procedure so that they satisfies all the properties
ALGORITHM 2 sum(n:positive integer)
a[n]
sum = 0
i=1
 while i≤ n
 sum = sum +a[i]
 i= i+1;
 end while
 return sum

Department of Computer Science 05/14/25 49

Examples: Characteristics of
Algorithm
 Determine which characteristics of an algorithm
the following procedure have and which it lack.
Procedure 3 reciprocal(n:positive integer)
// The purpose of this procedure is to find the reciprocal of a
positive integer n till 1.
while n>= 0 do
 1/n
m
n  n-1
 Procedure is not effective since the line “m  1/n” cannot
be executed when n=0, which will eventually be the case.
 It can also be argued that this procedure is not finite: if a
line in the procedure cannot be completed, the procedure
as a whole cannot be completed.
 It can also be argued that the procedure lacks

correctness since the “m 1/n” line will also keep the
procedure from arriving at a correct answer.
Department of Computer Science
Examples: Characteristics of
Algorithm
 Determine which characteristics of an algorithm
the following procedure have and which it lack.
Procedure 4 choose(a, b: integers)
// The purpose of this procedure is to choose a number from
two positive numbers
 x either a or b

 The only line in the procedure is ambiguous, how does

the procedure decide which value (a or b) to assign to x?
 Without knowing how this decision is made, the behavior of
this procedure is undetermined; therefore, this procedure
lacks definiteness.

Department of Computer Science

Your
Turn
Is the following a legitimate algorithm?
i 1
while i ≤ 10 do
a i + 1
print value of a

Not finite, goes on and on…

Department of Computer Science

FOOD FOR
THOUGHT
 What is the difference between an
ALGORITHM and a PROGRAMM

Department of Computer Science

Difference between PROGRAM and
ALGORITHM
 Unlike programs, algorithms are not
dependent on:
 a particular Programming Language
 Machine
 System
 Compiler.
 They are mathematical entities, which can
be thought of as running on some sort of
idealized computer with an infinite random
access memory and an unlimited word size.
 Algorithm design is all about the
mathematical theory behind the design
of good programs.
Department of Computer Science
Problems vs Algorithms vs
Programs
 For each problem or class of problems, there
may be many different algorithms.
 For each algorithm, there may be many
different implementations (programs).

Department of Computer Science

Points to Ponder

Upshot

A program is one type of algorithm!

All programs are algorithms!
Not all algorithms are programs!

Department of Computer Science

REPRESENTATION
OF
AGORITHM

Department of Computer Science

Methods of Specifying
Algorithms
 An algorithm may be expressed in a
number of ways, including:
 Natural language
 usually verbose and ambiguous.
 Flow chart
 Graphical representation
 avoid most (if not all) issues of ambiguity
 difficult to modify w/o specialized tools
 largely standardized

Department of Computer Science 05/14/25 58

Methods of Specifying
Algorithms
 Pseudo-code
 A mixture of natural language and
programming language-like structures
 Precise and brief
 also avoids most issues of ambiguity
 No particular agreement on syntax
 programming language
 tend to require expressing low-level details
that are not necessary for a high-level
understanding

Department of Computer Science 05/14/25 59

Flow Chart

 A graphical representation of a process

(e.g. an algorithm), in which graphic
objects are used to indicate the steps &
decisions that are taken as the process
moves along from start to finish.
 Individual steps are represented by boxes
and other shapes on the flowchart, with
arrows between those shapes indicating
the order in which the steps are taken.

Department of Computer Science

Start or stop

Process
Input or output

Flowchar Decision

t Flow line
Symbols Connector

Off-page connector

Department of Computer Science

Process Module

Flowchar
t counter
Automatic-
Symbols counter loop
A
S
B

Department of Computer Science

Flowcharts for three
constructs

Department of Computer Science

Pseudo
code
 Language that is typically used for writing algorithms

 Similar to a programming language, but not as rigid

 The method of expression most suitable for a given

situation is used:

 At times, plain English

 At others, a programming language like syntax

Department of Computer Science

Pseudo code
Details
 Pseudo-code in this course
 omits declarations of variables
 Expressions
 Control flow  Assignment
 if … then … [else …] (like  in Java)
 while … do …  Equality testing
 repeat … until … (like  in Java)
 for … do … n2 Superscripts and
 Indentation replaces other mathematical
braces formatting allowed
 Method declaration
Algorithm method (arg [, arg…])
Input …
Output …
Department of Computer Science
Pseudo code for three
constructs

Department of Computer Science

Pseudo code for three
constructs

Department of Computer Science

Example-1
 Let us illustrate three representation by
discussing simple computation problem
 Problem: Describe the standard
algorithm for finding the binary
representation of a positive decimal
integer
 a. in English.
 b. Flow Chart
 b. in Pseudo code.

Department of Computer Science 05/14/25 68

English
Description
1. Write the decimal number
2. Divide by 2; write quotient and
remainder
3. Repeat step 2 on the quotient; keep on
repeating until the quotient becomes
zero
4. Write all remainder digits in the reverse
order (last remainder first) to form the
final result

Department of Computer Science 05/14/25 69

Natural Language Flow
Chart
Write the decimal
Start

1.
number Input
Number
Base Step 1
2. Divide by 2; write
quotient and remainder Quatient=Number / Base
Remainder = Number %
Base

3. Repeat step 2 on the Step 2

Step 3
Record Remainder to List
quotient; keep on Number = Quotient

repeating until the

quotient becomes zero No
If Quotient
=0 Step 3
4. Write all remainder digits
in the reverse order (last Yes

remainder first) to form Display List

In Reverse Order Step 4
the final result
End

Department of Computer Science 05/14/25 70

Natural Language Pseudo Code
1. Write the decimal
number

2. Divide by 2; write
quotient and
remainder

3. Repeat step 2 on the

quotient; keep on
repeating until the
quotient becomes
zero

4. Write all remainder

digits in the reverse
order (last remainder
first) to form the final
result

Department of Computer Science 05/14/25 71

Example
2
Problem: Computing Greatest Common
Divisor of two non-negative, not-both zero
integers
 gcd(m, n): the largest integer that divides both m
and n
 Examples:gcd(60,24) = 12, gcd(60,0) = 60, gcd(0,0)
=?
Example: gcd(60,24) = gcd(24,12) = gcd(12,0) = 12
Algorithm: ?
Remember:
For each problem or class of problems, there may be many
different algorithms.
Department of Computer Science 05/14/25 72
Computing GCD:
Procedure 1
 Step 1 Find the prime factors of m
 Step 2 Find the prime factors of n
 Step 3 Identify all the common factors in the
two prime expansions found in Steps 1 and 2. If
p is a common factor occurring i and j times in
m and n, respectively, it should be repeated
min{i, j} times
 Step 4 Compute the product of all the common
factors and return it as the GCD of m and n
 Note: as written, this procedure requires that m
and n be integers greater than 1, since 1 is not
a prime
 Is this procedure an algorithm?

Department of Computer Science

Procedure 2:Euclid’s Algorithm for computing
GCD
 Idea:
 if n  0, gcd(m, n) = gcd(n, m mod n);
 if n = 0, gcd(m, n) = m.
 Euclid’s algorithm for computing gcd(m,
n)
 Step1 If n=0, return the value of m as the
answer and stop; otherwise proceed to Step2.
 Step2 Divide m by n and assign the value of
the remainder to r.
 Step3 Assign the value of n to m and the value
of r to n. Go to Step1.

Department of Computer Science

Specifying an
algorithm
Pseudo code description

Department of Computer Science 1-75

Computing GCD:
Procedure 3

 Step 1 Assign the value of min{m,n} to t

 Step 2 Divide m by t. If the remainder of
this division is 0, go to Step 3; otherwise, go
to Step 4
 Step 3 Divide n by t. If the remainder of
this division is 0, return the value of t as the
answer and stop; otherwise, proceed to Step
4
 Step 4 Decrease the value of t by 1. Go to
Step 2
 Note: m and n are positive integers
Department of Computer Science
What can we learn from the three examples of
gcd(m, n) ?
 These examples help us to illustrate
following important points:
 The nonambiguity requirement for each
step of an algorithm cannot be
compromised.
 The range of inputs for which an
algorithm works has to be specified
carefully.
 The same algorithm can be represented in
several different ways.
 There may exist several algorithms for
solving the same problem.
Department of Computer Science 05/14/25 77
What can we learn from the three examples of
gcd(m, n) ?
 Algorithms for the same problem can
be based on very different ideas and
can solve the problems with dramatically
different speeds.

Department of Computer Science 05/14/25 78

CONCLUSION

Department of Computer Science

One Problem, Many
Algorithms
Problem
 The statement of the problem specifies, in
general terms, the desired input/output
relationship.
Algorithm
 The algorithm describes a specific
computational procedure for achieving
input/output relationship.
Example
 One might need to sort a sequence of numbers
into non-decreasing order.
Algorithms
 Various algorithms e.g. merge sort, quick sort,
heap
Department sorts
of Computer etc.
Science
What we have
learnt?
 What is an algorithm?
 Understand the concept and properties of an
algorithm.
 Define and use the three constructs for developing
algorithms: sequence, decision, and repetition.
 What properties an algorithm must have?
 Understand the properties of an algorithm.
 How to specify an algorithm?
 Understand and use three tools to represent
algorithms:
flowchart, pseudocode, and structure.
 One problem different algorithms having
different speeds
 Discussed importance of algorithms

Department of Computer Science 05/14/25 81

Summary
 An algorithm is a Recipe, process,
method, technique, procedure, routine,…
with following
characteristics/requirements:
1. Input
 valid inputs are clearly specified
2. Output
 can be proved to produce the correct output given a valid
input
3. Finiteness
 terminates after a finite number of steps
4. Definiteness
 rigorously and unambiguously specified
5. Effectiveness
 steps are sufficiently simple and basic

Department of Computer Science

Points to
remember
Algorithm It is sequence of unambiguous
instructions for solving a
particular problem in a finite
amount of time
Properties Input, Output, Precision,
Determinism, Finiteness,
Definiteness, Correctness,
Generality
Building Sequence, Decision structure,
Blocks repetitive structure

Representati Structured description, flow

on chart, pseudo code

Important There may exist several

Point algorithms for solving the same
problem.

Department of Computer Science 05/14/25 83