Design and Analysis of Algorithms

UNIT – I
Algorithms and Problem Solving

ndamtals

Prof. S. P. Pingat, SKNCOE, Pune

Algorithms
◼ A tool for solving a well-specified
computational problem

Input Algorithm Output

◼ Algorithms must be:

❑ Correct: For each input produce an appropriate output
❑ Efficient: run as quickly as possible, and use as little
memory as possible – more about this later

Prof. S. P. Pingat, SKNCOE, Pune

2
Algorithms Cont.
◼ A well-defined computational procedure that takes
some value, or set of values, as input and produces
some value, or set of values, as output.

◼ Written in a pseudo code which can be

implemented in the language of programmer’s
choice.

Prof. S. P. Pingat, SKNCOE, Pune

3
Correct and incorrect algorithms
◼ Algorithm is correct if, for every input instance, it ends
with the correct output. We say that a correct algorithm
solves the given computational problem.

◼ An incorrect algorithm might not end at all on some

input instances, or it might end with an answer other than
the desired one.

◼ We shall be concerned only with correct algorithms.

Prof. S. P. Pingat, SKNCOE, Pune

4
Problems and Algorithms
◼ We need to solve a computational problem
❑ “Convert a weight in pounds to Kg”

◼ An algorithm specifies how to solve it, e.g.:

❑ 1. Read weight-in-pounds
❑ 2. Calculate weight-in-Kg = weight-in-pounds *
0.455
❑ 3. Print weight-in-Kg

◼ A computer program is a computer-

executable description of an algorithm

Prof. S. P. Pingat, SKNCOE, Pune

5
The Problem-solving Process

Analysis
Problem
specification
Design

Algorithm
Implementation

Program

Compilation
Executable
(solution)

Prof. S. P. Pingat, SKNCOE, Pune

6
 From Algorithms to Programs
Problem
Algorithm: A sequence
of instructions describing
how to do a task (or
process)

C++ Program
Prof. S. P. Pingat, SKNCOE, Pune
7
•Algorithms as technology
•hardware with high clock rates, pipelining, and
superscalar architectures

•easy-to-use, intuitive graphical user interfaces (GUIs),

•object-oriented systems

•local-area and wide-area networking.

Prof. S. P. Pingat, SKNCOE, Pune

Classification of problem

Types:
1) Problems based on Algorithmic Solutions:
Include Step by step Instructions and Series of actions
eg: To find fibonacci series – Sequence of steps/actions are
required.

2) Problems based on Heuristic Solutions:

Trial and Error form
No sequence of actions or instructions
eg: Decision of which stock should I buy?

Prof. S. P. Pingat, SKNCOE, Pune

Prof. S. P. Pingat, SKNCOE, Pune
 Problem Solving Strategies

• 1) Divide and conquer: A divide-and-conquer algorithm works by

recursively breaking down a problem into two or more sub-problems of the
same or related type, until these become simple enough to be solved
directly.
• Eg: Binary search, Merge sort, Quick sort
• 2) Greedy method: The greedy approach is an algorithm strategy in
which a set of resources are recursively divided based on the maximum,
immediate availability of that resource at any given stage of execution. To
solve a problem based on the greedy approach, there are two stages.
scanning the list of items. optimization.
• Eg: Knapsack Problem, Job scheduling with deadlines.

Prof. S. P. Pingat, SKNCOE, Pune

 Problem Solving Strategies

• 3) Dynamic programming: Dynamic Programming is mainly an

optimization over plain recursion. Wherever we see a recursive solution that
has repeated calls for same inputs, we can optimize it using Dynamic
Programming. The idea is to simply store the results of subproblems, so that
we do not have to re-compute them when needed later.
• Eg: 0/1 Knapsack problem, Optimum Binary Search Tree, Travelling salesman
problem
• 4) Trial and error: Trial And Error. Trial and error is a problem solving
method in which multiple attempts are made to reach a solution. It is a basic
method of learning that essentially all organisms use to learn new behaviors.
Trial and error is trying a method, observing if it works, and if it doesn't
trying a new method.
• Eg: Printer not working problem: check ink level or check paper tray jamming

Prof. S. P. Pingat, SKNCOE, Pune

Practical Examples
◼ Internet and Networks
􀂄 The need to access large amount of information with the
shortest time.
􀂄 Problems of finding the best routs for the data to travel.
􀂄 Algorithms for searching this large amount of data to quickly
find the pages on which particular information resides.

◼ Electronic Commerce
􀂄 The ability of keeping the information (credit card numbers,
passwords, bank statements) private, safe, and secure.
􀂄 Algorithms involves encryption/decryption techniques.

Prof. S. P. Pingat, SKNCOE, Pune

13
Hard problems
◼ We can identify the Efficiency of an algorithm
from its speed (how long does the algorithm take
to produce the result).
◼ Some problems have unknown efficient solution.
◼ These problems are called NP-complete problems.
◼ If we can show that the problem is NP-complete,
we can spend our time developing an efficient
algorithm that gives a good, but not the best
possible solution.

Prof. S. P. Pingat, SKNCOE, Pune

14
Components of an Algorithm
◼ Variables and values
◼ Instructions
◼ Sequences
❑ A series of instructions
◼ Procedures
❑ A named sequence of instructions
❑ we also use the following words to refer to a
“Procedure” :
◼ Sub-routine
◼ Module
◼ Function
Prof. S. P. Pingat, SKNCOE, Pune
15
Components of an Algorithm Cont.
◼ Selections
❑ An instruction that decides which of two possible
sequences is executed
❑ The decision is based on true/false condition
◼ Repetitions
❑ Also known as iteration or loop
◼ Documentation
❑ Records what the algorithm does

Prof. S. P. Pingat, SKNCOE, Pune

16
Classification of Time Complexities

Prof. S. P. Pingat, SKNCOE, Pune

Classification of Time Complexities

•Constant Time Complexity: O(1) ...

•Linear Time Complexity: O(n) ...

•Logarithmic Time Complexity: O(log n) ...

•Quadratic Time Complexity: O(n²) ...

•Exponential Time Complexity: O(2^n)

Prof. S. P. Pingat, SKNCOE, Pune

Asymptotic Notation ( Ο Ω Θ )

[Big “oh” ] : This notation is used to express an upper bound on

computing time of an algorithm. When we say that time complexity
of Selection sort algorithm is Ο(n2) , means that for sufficiently large
values of ‘n’ , computation time will not exceed some constant time *
n2 i.e proportional to n2 (Worst Case).

Prof. S. P. Pingat, SKNCOE, Pune

[Big “oh”] Ο
• Definition : The function f(n) = Ο( g(n) ) (read as “f of n is
big oh of g of n”) iff (if and only if ) there exist positive
constants c and n0 such that f(n) <= c * g(n) for all n, n
>= n0.
• Example:
• The function 3n+2 = Ο(n) as 3n + 2 <= 4n for all n >= 2
• The function 3n+3 = Ο(n) as 3n + 3 <= 4n for all n >= 3
• The function 100n+6 = Ο(n) as 100n + 6 <= 101n for all n
>= 6
• The function 10n2+4n+2 = Ο(n2) as 10n2+4n+2 <= 11n2
for all n >= 5
• The function 1000n2+100n-6 = Ο(n2) as 1000n2+100n-6
<= 1001n2 for all n >= 100
• The function 6*2n + n2 = Ο(2n) as 6*2n + n2 <= 7*2n for
all n >= 4

Prof. S. P. Pingat, SKNCOE, Pune

[Omega] Ω
This notation is used to express an lower bound on computing time
of an algorithm. When we say that best case time complexity of
insertion sort is Ω (n), means that for sufficiently large values of ‘n’,
minimum computation time will be some constant time * n i.e
proportional to n.

Prof. S. P. Pingat, SKNCOE, Pune

 [Omega] Ω
• Definition : The function f(n) = Ω( g(n) ) (read as “f of n is
omega of g of n”) iff there exist positive constants c and
n0 such that f(n) >= c * g(n) for all n, n >= n0.
• Example:
• The function 3n+2 = Ω (n) as 3n + 2 >= 3n for all n >= 1
• The function 3n+3 = Ω (n) as 3n + 3 >= 3n for all n >= 1
• The function 100n+6 = Ω (n) as 100n + 6 >= 100n for all n
>= 1
• The function 10n2+4n+2 = Ω (n2) as 10n2+4n+2 >= n2 for
all n >= 1
• The function 6*2n + n2 = Ω (2n) as 6*2^n + n2 >= 2n for all
n >= 1

Prof. S. P. Pingat, SKNCOE, Pune

[Theta] Θ

• This notation is used to express time complexity of

an algorithm when it is same for worst & Best cases.
For example best and worst case time complexities
for selection sort is Ο(n2) & Ω (n2) i.e. it can be
expressed as Θ (n2).
• Definition : The function f(n) = Θ( g(n) ) (read as “f
of n is theta of g of n”) iff there exist positive
constants c1, c2 and n0 such that c1 *g(n) <= f(n)
<= c2 * g(n) for all n, n >= n0.

Prof. S. P. Pingat, SKNCOE, Pune

• Example:
• The function 3n+2 = Θ (n) as 3n + 2 >= 3n for all n >= 2 and 3n + 2 <=
4n for all n >= 2.
• The function 3n+3 = Θ (n)
• The function 10n2+4n+2 = Θ (n2)
• The function 6*2n + n2 = Θ (2n)

Prof. S. P. Pingat, SKNCOE, Pune

• Proving the Correctness of Algorithms
• Preconditions and Postconditions
• Loop Invariants
• Induction – Math Review
• Using Induction to Prove Algorithms

Prof. S. P. Pingat, SKNCOE, Pune

 What does an algorithm ?
• An algorithm is described by:
• Input data
• Output data
• Preconditions: specifies restrictions on input data
• Postconditions: specifies what is the result
• Example: Binary Search
• Input data: a:array of integer;
x:integer;
• Output data: found:boolean;
• Precondition: a is sorted in ascending order
• Postcondition: found is true if x is in a, and found
is false otherwise
Prof. S. P. Pingat, SKNCOE, Pune
 Correct algorithms
• An algorithm is correct if:
• for any correct input data:
•it stops and
•it produces correct output.

•Correct input data: satisfies precondition

•Correct output data: satisfies postcondition

Prof. S. P. Pingat, SKNCOE, Pune

 Proving correctness
• An algorithm = a list of actions
• Proving that an algorithm is totally
correct:
1. Proving that it will terminate
2. Proving that the list of actions applied to the
precondition imply the postcondition

• This is easy to prove for simple sequential

algorithms
• This can be complicated to prove for repetitive
algorithms (containing loops or recursivity)
• use techniques based on loop invariants and induction
Prof. S. P. Pingat, SKNCOE, Pune
 Example – a sequential
algorithm
Swap1(x,y):
Proof: the list of actions
aux := x
applied to the
x := y precondition imply the
y := aux postcondition
1. Precondition:
Precondition: x = a and y = b
x = a and y = b 2. aux := x => aux = a
Postcondition: 3. x : = y => x = b
x = b and y = a 4. y := aux => y = a
5. x = b and y = a is
the Postcondition

Prof. S. P. Pingat, SKNCOE, Pune

 Example – a repetitive
algorithm
Algorithm Sum_of_N_numbers
Proof: the list of actions
applied to the
Input: a, an array of N numbers
precondition imply
Output: s, the sum of the N numbers
in a the postcondition
BUT: we cannot
s:=0; enumerate all the
k:=0; actions in case of a
While (k<N) do repetitive algorithm
k:=k+1;
!
s:=s+a[k]; We use techniques
end based on loop
invariants and
induction
Prof. S. P. Pingat, SKNCOE, Pune
 Loop invariants
• A loop invariant is a logical predicate such
that: if it is satisfied before entering any
single iteration of the loop then it is also
satisfied after the iteration

Prof. S. P. Pingat, SKNCOE, Pune

 Example: Loop invariant for
Sum of n numbers
Algorithm Sum_of_N_numbers

Input: a, an array of N numbers

Output: s, the sum of the N numbers in a

s:=0;
Loop invariant = induction
k:=0;
While (k<N) do hypothesis: At step k, S holds the
k:=k+1; sum of the first k numbers
s:=s+a[k];
end

Prof. S. P. Pingat, SKNCOE, Pune

 Using loop invariants in proofs
• We must show the following 3 things
about a loop invariant:
1. Initialization: It is true prior to the first
iteration of the loop.
2. Maintenance: If it is true before an
iteration of the loop, it remains true before
the next iteration.
3. Termination: When the loop terminates,
the invariant gives us a useful property that
helps show that the algorithm is correct.

Prof. S. P. Pingat, SKNCOE, Pune

 Example: Proving the
correctness of the Sum
algorithm (1)
• Induction hypothesis: S= sum of the first k
numbers
1. Initialization: The hypothesis is true at the
beginning of the loop:
Before the first iteration: k=0, S=0. The first 0 numbers
have sum zero (there are no numbers) =>
hypothesis true before entering the loop

Prof. S. P. Pingat, SKNCOE, Pune

 Example: Proving the
correctness of the Sum
algorithm (2)
• Induction hypothesis: S= sum of the first k numbers
2. Maintenance: If hypothesis is true before step k, then it
will be true before step k+1 (immediately after step k is
finished)
We assume that it is true at beginning of step k: “S is the sum of the first k
numbers”
We have to prove that after executing step k, at the beginning of step k+1:
“S is the sum of the first k+1 numbers”
We calculate the value of S at the end of this step
K:=k+1, s:=s+a[k+1] => s is the sum of the first k+1 numbers

Prof. S. P. Pingat, SKNCOE, Pune

 Example: Proving the
correctness of the Sum
algorithm (3)
• Induction hypothesis: S= sum of the first k
numbers
3. Termination: When the loop terminates,
the hypothesis implies the correctness of
the algorithm
The loop terminates when k=n=> s= sum of
first k=n numbers => postcondition of
algorithm, DONE

Prof. S. P. Pingat, SKNCOE, Pune

 Loop invariants and induction
• Proving loop invariants is similar to mathematical
induction:
• showing that the invariant holds before the first iteration corresponds to
the base case, and
• showing that the invariant holds from iteration to iteration corresponds to
the inductive step.

Prof. S. P. Pingat, SKNCOE, Pune

 Mathematical induction -
Review
• Let T be a theorem that we want to prove.
T includes a natural parameter n.
• Proving that T holds for all natural values
of n is done by proving following two
conditions:
1. T holds for n=1
2. For every n>1 if T holds for n-1, then T holds for n

Terminology:
T= Induction Hypothesis
1= Base case
2= Inductive step
Prof. S. P. Pingat, SKNCOE, Pune
 Mathematical induction -
Review
• Strong Induction: a variant of induction
where the inductive step builds up on all
the smaller values
• Proving that T holds for all natural values
of n is done by proving following two
conditions:
1. T holds for n=1
2. For every n>1 if T holds for all k<= n-1, then T holds for n

Prof. S. P. Pingat, SKNCOE, Pune

 Mathematical induction review –
Example1

• Theorem: The sum of the first n natural

numbers is n*(n+1)/2

• Proof: by induction on n
1. Base case: If n=1, s(1)=1=1*(1+1)/2
2. Inductive step: We assume that s(n)=n*(n+1)/2,
and prove that this implies s(n+1)=(n+1)*(n+2)/2 ,
for all n>=1

s(n+1)=s(n)+(n+1)=n*(n+1)/2+(n+1)=(n+1)*(n+2)/2

Prof. S. P. Pingat, SKNCOE, Pune

 Mathematical induction review –
Example2
• Theorem: Every amount of postage that is at
least 12 cents can be made from 4-cent and
5-cent stamps.
• Proof: by induction on the amount of postage
• Postage (p) = m * 4 + n * 5
• Base case:
• Postage(12) = 3 * 4 + 0 * 5
• Postage(13) = 2 * 4 + 1 * 5
• Postage(14) = 1 * 4 + 2 * 5
• Postage(15) = 0 * 4 + 3 * 5

Prof. S. P. Pingat, SKNCOE, Pune

 Mathematical induction review –
Example2 (cont)
• Inductive step: We assume that we can construct
postage for every value from 12 up to k. We need to
show how to construct k + 1 cents of postage. Since
we have proved base cases up to 15 cents, we can
assume that k + 1 ≥ 16.
• Since k+1 ≥ 16, (k+1)−4 ≥ 12. So by the inductive
hypothesis, we can construct postage for (k + 1) −
4 cents: (k + 1) − 4 = m * 4+ n * 5
• But then k + 1 = (m + 1) * 4 + n * 5. So we can
construct k + 1 cents of postage using (m+1) 4-cent
stamps and n 5-cent stamps

Prof. S. P. Pingat, SKNCOE, Pune

 Correctness of algorithms
• Induction can be used for proving the correctness of
repetitive algorithms:
• Iterative algorithms:
• Loop invariants
• Induction hypothesis = loop invariant = relationships between the variables during loop
execution
• Recursive algorithms
• Direct induction
• Hypothesis = a recursive call itself ; often a case for applying strong induction

Prof. S. P. Pingat, SKNCOE, Pune

 Example: Correctness proof
for Decimal to Binary
Conversion
Algorithm Decimal_to_Binary

Input: n, a positive integer

Output: b, an array of bits, the bin repr. of n,
starting with the least significant bits

t:=n;
k:=0; It is a repetitive (iterative)
While (t>0) do
algorithm, thus we use loop
k:=k+1;
b[k]:=t mod 2; invariants and proof by induction
t:=t div 2;
end

Prof. S. P. Pingat, SKNCOE, Pune

 Example: Loop invariant for
Decimal to Binary Conversion
Algorithm Decimal_to_Binary

Input: n, a positive integer

Output: b, an array of bits, the bin repr. of n

t:=n;
k:=0;
At step k, b holds the k least
While (t>0) do significant bits of n, and the value
k:=k+1; of t, when shifted by k,
b[k]:=t mod 2; corresponds to the rest of the bits
t:=t div 2;
1 2 3 k
end

2 0 2 1 2 2 2k-1
Prof. S. P. Pingat, SKNCOE, Pune
 Example: Loop invariant for
Decimal to Binary Conversion
Algorithm Decimal_to_Binary

Input: n, a positive integer

Output: b, an array of bits, the bin repr. of n

t:=n; Loop invariant: If m is the

k:=0;
While (t>0) do
integer represented by array
k:=k+1; b[1..k], then n=t*2k+m
b[k]:=t mod 2;
t:=t div 2; 1 2 3 k
end
b

20 21 22 2k-1
Prof. S. P. Pingat, SKNCOE, Pune
 Example: Proving the
correctness of the
conversion algorithm
• Induction hypothesis=Loop
Invariant: If m is the integer represented
by array b[1..k], then n=t*2^k+m

• To prove the correctness of the

algorithm, we have to prove the 3
conditions:
1. Initialization: The hypothesis is true at the
beginning of the loop
2. Maintenance: If hypothesis is true for step k, then
it will be true for step k+1
3. Termination: When the loop terminates, the
hypothesis implies the correctness of the
algorithm Prof. S. P. Pingat, SKNCOE, Pune
 Example: Proving the
correctness of the
conversion algorithm (1)
• Induction hypothesis: If m is the integer
represented by array b[1..k], then
n=t*2^k+m
1. The hypothesis is true at the beginning of
the loop:
k=0, t=n, m=0(array is empty)
n=n*2^0+0

Prof. S. P. Pingat, SKNCOE, Pune

 Example: Proving the
correctness of the
conversion algorithm (2)
• Induction hypothesis: If m is the integer
represented by array b[1..k], then n=t*2^k+m
2. If hypothesis is true for step k, then it will be true
for step k+1
At the start of step k: assume that n=t*2^k+m, calculate the
values at the end of this step
If t=even then: t mod 2==0, m unchanged, t=t / 2, k=k+1=> (t /
2) * 2 ^ (k+1) + m = t*2^k+m=n
If t=odd then: t mod 2 ==1, b[k+1] is set to 1, m=m+2^k , t=(t-
1)/2, k=k+1 => (t-1)/2*2^(k+1)+m+2^k=t*2^k+m=n

Prof. S. P. Pingat, SKNCOE, Pune

 Example: Proving the
correctness of the
conversion algorithm (3)
• Induction hypothesis: If m is the integer
represented by array b[1..k], then
n=t*2^k+m
3. When the loop terminates, the hypothesis
implies the correctness of the algorithm
The loop terminates when t=0 =>
n=0*2^k+m=m
n==m, proved

Prof. S. P. Pingat, SKNCOE, Pune

 Proof of Correctness for
Recursive Algorithms
• In order to prove recursive algorithms, we
have to:
1. Prove the partial correctness (the fact that the
program behaves correctly)
• we assume that all recursive calls with arguments that
satisfy the preconditions behave as described by the
specification, and use it to show that the algorithm
behaves as specified
2. Prove that the program terminates
• any chain of recursive calls eventually ends and all loops, if
any, terminate after some finite number of iterations.

Prof. S. P. Pingat, SKNCOE, Pune

 Example - Merge Sort q r
MERGE-SORT(A,p,r) p
if p < r
q= (p+r)/2
MERGE-SORT(A,p,q)
MERGE-SORT(A,q+1,r)
MERGE(A,p,q,r)

Precondition:
Array A has at least 1 element between
indexes p and r (p<=r)
Postcondition:
The elements between indexes p and r are
sorted

Prof. S. P. Pingat, SKNCOE, Pune

 Correctness proofs
for recursive algorithms
RECURSIVE(n) is
if (n=small_value)
return ct
else
RECURSIVE(n1) n1, n2, … nr are some
… values smaller than n but
RECURSIVE(nr) bigger than small_value
some_code

• Base Case: Prove that RECURSIVE works for n = small_value

• Inductive Hypothesis:
• Assume that RECURSIVE works correctly for n=small_value, ..., k
• Inductive Step:
• Show that RECURSIVE works correctly for n = k + 1

Prof. S. P. Pingat, SKNCOE, Pune

• Proving that an algorithm is totally correct
means:
1.Proving that it will terminate
2.Proving that the list of actions applied to the
precondition imply the postcondition
• How to prove repetitive algorithms:
• Iterative algorithms: use Loop invariants, Induction
• Recursive algorithms: use induction using as
hypothesis the recursive call

Prof. S. P. Pingat, SKNCOE, Pune

THANK YOU

Prof. S. P. Pingat, SKNCOE, Pune