Amity School of Engineering & Technology

Module-1
Design and Analysis of
Algorithm
CSE 703
Advanced Problem Solving
Techniques

By: Dr. Ghanshyam Prasad Dubey

Associate Professor (CSE-ASET, AUMP)
 Amity School of Engineering & Technology

Syllabus
• Course Objective: (CSE703)
• To impart the basic concepts of data structures
and algorithms and understand about writing
step by step approach in solving problems with
the help of appropriate data structures also
improve problem solving skills in operating
system and database management.
 Amity School of Engineering & Technology

• Module I: Design and Analysis of Algorithm: (6

Hours)
– Introduction: Algorithms, Analyzing Algorithms, Complexity
of Algorithms, Growth of Functions, Performance
Measurements, Asymptotic Notations. Recurrences-
substitution method, recursion tree method, master method
– Types of algorithm: Divide and Conquer with Examples Such
as Sorting, Matrix Multiplication, Convex Hull and Searching.
Greedy Methods with Examples Such as Optimal Reliability
Allocation, Knapsack, Minimum Spanning Trees – Prim’s and
Kruskal’s Algorithms, Single Source Shortest Paths – Dijkstra’s
and Bellman Ford Algorithms. Dynamic Programming with
Examples Such as Knapsack. All Pair Shortest Paths –
Warshal’s and Floyd’s Algorithms, Resource Allocation
Problem. Backtracking, Branch and Bound with Examples
Such as Travelling Salesman Problem, Graph Coloring, n-
Queen Problem, Hamiltonian Cycles and Sum of Subsets.
 Amity School of Engineering & Technology

• Module II: Operating System-I

– Processes and Scheduling policies :Introduction to
processes management, operating system views of
processes, various process transition states, Introduction
to Processor scheduling, Introduction to various types of
schedulers, Performance criteria in scheduling algorithms,
Concept of FCFS scheduling algorithm, Concept of priority
scheduling algorithm like SJF, Concept of non-preemptive
and preemptive algorithms, Concept of round-robin
scheduling algorithm, , Concept of multi-level queues,
feedback queues.
– Interprocess Communication: Introduction to
Interprocess Communication and Synchronization, Critical
regions and Conditional critical regions in a Semaphore.
Introduction to monitors, various modes of monitors,
Issues in message implementation, Concept of mutual
exclusion with messages.
 Amity School of Engineering & Technology

Module III: Operating System-II:

• Dead Locks: Concept of Deadlocks, issues related to its
prevention, avoidance and detection/recovery, Concept of
deadlock prevention and its avoidance, Concept of deadlock
detection and recovery.
• Memory Management: Need of Memory management and
its requirements, paging, segmentation, concept of
fragmentation. Characteristics of contiguous & non-
contiguous allocation techniques, Detail study of
fragmentation, Virtual memory management, introduction to
page-replacement, Need of various page-replacement
policies, Concept of FIFO and optimal page-replacement
algorithms, Concept of LRU approximation and its page-
replacement algorithm,
 Amity School of Engineering & Technology
• Module IV: Database Management System-I:
– Data Modeling using the Entity Relationship Model: ER
model concepts, notation for ER diagram, mapping
constraints, keys, Concepts of Super Key, candidate key,
primary key, Generalization, aggregation, reduction of an ER
diagrams to tables, extended ER model, relationships of
higher degree.
– Relational data Model and Language: Relational data
model concepts, integrity constraints: entity integrity,
referential integrity, Keys constraints, Domain constraints,
relational algebra, relational calculus, tuple and domain
calculus.
– Introduction to SQL: Characteristics of SQL. Advantage of
SQL. SQL data types and literals. Types of SQL commands.
SQL operators and their procedure. Tables, views and
indexes. Queries and sub queries. Aggregate functions.
Insert, update and delete operations. Joins, Unions,
Intersection, Minus, Cursors in SQL.
 Amity School of Engineering & Technology

• Module V: Database Management System-II:

– Data Base Design & Normalization: Functional
dependencies, normal forms, first, second, third normal
forms, BCNF, inclusion dependences, loss less join
decompositions, normalization using FD, MVD, and JDs,
alternative approaches to database design. Transaction
Processing Concepts: Transaction system, Testing of
serializability, Serializability of schedules, conflict & view
serializable schedule, recoverability, Recovery from
transaction failures, log based recovery, checkpoints,
deadlock handling.
– Concurrency Control Techniques: Concurrency control,
locking Techniques for concurrency control, Time
stamping protocols for concurrency control, validation
based protocol, multiple granularity, Multi version
schemes, Recovery with concurrent transaction.
 Amity School of Engineering & Technology

Course Outcomes:
• Able to analyze algorithms and determine their
complexity.
• Ability to apply the algorithms and design techniques
to solve problems.
• Ability to understand various views and management
policies adopted by O.S. as pertaining with processes ,
Deadlock , memory , File and I/O operations.
• Ability to understand the concepts of relational data
model, entity-relationship model, relational database
design, relational algebra and SQL.
• Ability to improve the database design by
normalization.
 Amity School of Engineering & Technology

• Text: Reference books

• E. Horowitz & S Sahni, "Fundamentals of Computer Algorithms",
• Thomas H. Coreman, Charles E. Leiserson and Ronald L.
Rivest, “Introduction to Algorithms”, Printice Hall of India.
• A. Silberschatz, P.B. Galvin “Operating System Concepts”, John
Willey & son
• Korth, Silberschatz, “Database System Concepts”, 4th Ed., TMH,
2000.
• Elmasri, Navathe, “ Fundamentals of Database Systems”,
Addision Wesley
• Reference:
• Aho, Hopcraft, Ullman, “The Design and Analysis of Computer
Algorithms” Pearson Education, 2008.
• Milenekovic, “Operating System Concepts”, McGraw Hill
• Date C. J., “An Introduction to Database Systems”, 7th Ed.,
Narosa Publishing.
 Amity School of Engineering & Technology

Algorithm
• An algorithm is a set of commands that must be
followed for a computer to perform calculations
or other problem-solving operations.
• According to its formal definition, an algorithm is
a finite set of instructions carried out in a specific
order to perform a particular task.
 Amity School of Engineering & Technology

• key characteristics of an algorithm:

– Finite Steps: An algorithm must have a clear and
finite number of steps.
– Well-Defined Instructions: Each step in an algorithm
must be precisely defined and unambiguous.
– Input: Algorithms usually take some input data to
work with.
– Output: After processing the input, the algorithm
produces an output.
– Deterministic: In most cases, an algorithm will
produce the same output for a given input every time
it is run. However, there are also probabilistic
algorithms that can give different outputs for the same
input.
 Amity School of Engineering & Technology

Analyzing Algorithms
• Algorithms are analyzed through their complexity
analysis.
• Complexity analysis is defined as a technique to
measure how long an algorithm would take to complete
given an input of size n; independent of the machine,
language, and compiler. It is used for evaluating the
variations of execution time/memory space on different
algorithms.
• Complexity Analysis is Required?
– It gives you an estimated time and space required to
execute a program.
– It is used for comparing different algorithms for different
input sizes.
– It helps to determine the difficulty of a problem.
 Amity School of Engineering & Technology

Asymptotic Notations
• The study of the variations in the performance of the
algorithm with the change in the order of the input size is
called Asymptotic Analysis.
• Asymptotic notations are mathematical notations to
describe the running time of an algorithm when the input
tends towards a particular value or a limiting value.
• In other words, it defines the mathematical limits of its
run-time performance.
• There are mainly three asymptotic notations for the
complexity analysis of algorithms. They are as
follows:
– Big-O notation
– Omega notation
– Theta notation
 Amity School of Engineering & Technology

Big O notation (O-notation)

• Big O notation symbolizes the upper bound of the
running time of an algorithm or the algorithm's longest
amount of time to complete its operation. Therefore, it
gives the worst-case complexity of an algorithm.
• Mathematically: O(g(n)) = { f(n): there exist positive
constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all
n ≥ n0 }
• In above expression, a function f(n) belongs to the
set O(g(n)) if there exists a positive constant c such
that it lies between 0 and cg(n), for sufficiently large n.
For any value of n, the running time of an algorithm
does not cross the time provided by O(g(n)).
 Amity School of Engineering & Technology

Omega notation (Ω-notation)

• Omega notation symbolizes the lower bound of the
running time of an algorithm. Thus, it provides the
best-case complexity of an algorithm. It determines
the fastest time that an algorithm can run.
• Mathematically: Ω(g(n)) = { f(n): there exist
positive constants c and n0 such that 0 ≤ cg(n) ≤
f(n) for all n ≥ n0 }
• In the above expression, a function f(n) belongs to
the set Ω(g(n)) if there exists a positive
constant c such that it lies above cg(n), for
sufficiently large n. For any value of n, the minimum
time required by the algorithm is given by Omega
Ω(g(n)).
 Amity School of Engineering & Technology

Theta Notation (Θ-notation)

• Theta notation symbolizes the upper and the lower bound
of the running time of an algorithm. In real-world problems,
an algorithm does not perform worst or best, it fluctuates
between the worst-case and best-case, and this gives us
the average case complexity of an algorithm.
• Mathematically: Θ(g(n)) = { f(n): there exist positive
constants c1, c2 and n0 such that 0 ≤ c1g(n) ≤ f(n) ≤
c2g(n) for all n ≥ n0 }
• In the above expression, a function f(n) belongs to the
set Θ(g(n)) if there exist positive constants c1 and c2 such
that it can be sandwiched between c1g(n) and c2g(n), for
sufficiently large n. If a function f(n) lies anywhere in
between c1g(n) and c2g(n) for all n ≥ n0, then f(n) is said
to be asymptotically tight bound.
 Amity School of Engineering & Technology

Parameters to Measure Complexities

• Time Complexity
• It is the amount of time taken by an algorithm to
execute each statement of the code till its
completion.
• The time taken here is for the function of the length
of the input and not the actual execution time of the
machine on which the algorithm is running.
• The time complexity of algorithms is commonly
expressed using the Big O notation.
• To calculate the time complexity, total the cost of
each fundamental instruction and the number of
times the instruction is executed.
 Amity School of Engineering & Technology

• Space Complexity
• Space complexity is the amount of memory space an
algorithm or a problem takes during the execution of that
particular problem/algorithm.
• Here, the space used includes both, the variables and
the input values. Space complexity is the combination or
sum up of the auxiliary space and the space used by
input values.
• Auxiliary space is the temporary space required by an
algorithm/problem during the execution of that
algorithm/problem.
• Space Complexity = Auxiliary Space + Space used
for input values. It is frequently represented using Big
O notation, just like time complexity, to describe the
maximum amount of memory utilization.
 Amity School of Engineering & Technology

Algorithm cases
• Worst-Case: The maximum time or space an
algorithm can take, providing an upper bound.
• Average-Case: The expected time or space an
algorithm takes, averaged over all possible
inputs.
• Best-Case: The minimum time or space an
algorithm can take, providing a lower bound.
 Amity School of Engineering & Technology

How to optimize an Algorithm?

• We can optimize a solution using both time and
space optimization. To optimize a program,
Reduce the time taken to run the program and
increase the space occupied.
• Reduce the memory usage of the program and
increase its total run time.
• Reduce both time and space complexity by
deploying relevant algorithms.
 Amity School of Engineering & Technology

Complexity Analysis of Algorithms

 Amity School of Engineering & Technology

Recurrences- substitution method

• Whenever any function makes a recursive call to itself, its
time can be computed by a Recurrence Relation.
• Recurrence Relation is simply a mathematical relation/
equation that can give the value of any term in terms of
some previous smaller terms.
• Linear Recurrence Relation: In case of Linear Recurrence
Relation every term is dependent linearly on its previous
term. Example of Linear Recurrence Relation can be T(n) =
T(n-1) + T(n-2) + T(n-3)
• Divide and Conquer Recurrence Relation: It the type of
Recurrence Relation which is obtained from Divide and
Conquer Algorithm. Example of such recurrence relation can
be T(n) = 3T(n/2) + 9n
 Amity School of Engineering & Technology

• First Order Recurrence Relation: It is the type of

recurrence relation in which every term is dependent on
just previous term. Example of this type of recurrence
relation can be- T(n) = T(n-1)2
• Higher Order Recurrence Relation– It is the type of
recurrence relation where one term is not only
dependent on just one previous term but on multiple
previous terms. If it will be dependent on two previous
term then it will be called to be second order. Similarly,
for three previous term its will be called to be of third
order and so on. Let us see example of an third order
Recurrence relation T(n) = 2T(n-1)2 + KT(n-2) +
T(n-3)
 Amity School of Engineering & Technology

Substitution Method
• The Substitution Method Consists of two main steps:
– Guess the Solution.
– Use the mathematical induction to find the boundary condition
and shows that the guess is correct.
• For Example Solve the equation by Substitution
Method. T (n) = T (n/2)+ n We have to show that it is
asymptotically bound by O (log n).
• Solution:
– For T (n) = O (log n) We have to show that for some constant c
– T (n) ≤c logn.
– Put this in given Recurrence Equation.
– T (n) ≤c log (n/2)+ 1 ≤c log(n/2)+ 1 = c logn-clog2 2+1 ≤c logn for
c≥1
– Thus T (n) =O logn.
 Amity School of Engineering & Technology

• Example 2: consider eq. T (n) = 2T(n/2)+ n n>1

Find an Asymptotic bound on T.
• Solution:
• We guess the solution is O (n (logn)).
• Thus for constant 'c'. T (n) ≤c n logn
• Put this in given Recurrence Equation. Now,
• T (n) ≤ 2c (n/2) log(n/2) +n ≤ cn log n – cn
log2+n =cn logn-n (clog2-1) ≤cn logn for (c≥1)
• Thus T (n) = O (n logn).
 Amity School of Engineering & Technology

Iteration Methods
• Consider the Recurrence
• T (n) = 1 if n=1
= 2T (n-1) if n>1
 Amity School of Engineering & Technology

• T (n) = 2T (n-1)
• = 2[2T (n-2)] = 22T (n-2)
• = 4[2T (n-3)] = 23T (n-3)
• = 8[2T (n-4)] = 24T (n-4) …………….(Eq.1)

• Repeat the procedure for i times

T (n) = 2i T (n-i)
• Put n-i=1 or i= n-1 in (Eq.1)
• T (n) = 2n-1 T (1) = 2n-1 .1 {T (1) =1 .....given}
= 2n-1
= O(2n )
 Amity School of Engineering & Technology

Consider the Recurrence

T (n) = T (n-1) +1 and T (1) = θ (1).
• T (n) = T (n-1) +1
• = (T (n-2) +1) +1
• = (T (n-3) +1) +1+1
• = T (n-4) +4
• = T (n-5) +1+4 = T (n-5) +5
• = T (n-k) + k
• Where k = n-1 ,T (n-k) = T (1) = θ (1)
• T (n) = θ (1) + (n-1) = 1+n-1=n= θ (n).
 Amity School of Engineering & Technology

Recursion Tree Method

1. Recursion Tree Method is a pictorial
representation of an iteration method which
is in the form of a tree where at each level
nodes are expanded.
2. In general, we consider the second term
in recurrence as root.
3. It is useful when the divide & Conquer
algorithm is used.
 Amity School of Engineering & Technology

4. It is sometimes difficult to come up with a

good guess. In Recursion tree, each root and
child represents the cost of a single
subproblem.
5. We sum the costs within each of the levels of
the tree to obtain a set of per-level costs and
then sum all per-level costs to determine the
total cost of all levels of the recursion.
6. A Recursion Tree is best used to generate a
good guess, which can be verified by the
Substitution Method.
 Amity School of Engineering & Technology

• Consider T (n) = 2T(n/2) + n2

Amity School of Engineering & Technology
 Amity School of Engineering & Technology

Answer: O(n2 )
 Amity School of Engineering & Technology

• Consider the recurrence relation,

T(n) = T(n/4) + T(n/2) + cn2
 Amity School of Engineering & Technology

• To know the value of T(n), we need to

calculate the sum of tree nodes level by
level. If we sum the above tree level by
level, we get the following series
T(n) = c(n^2 + 5(n^2)/16 + 25(n^2)/256) +
….
• The above series is a geometrical
progression with a ratio of 5/16.
• To get an upper bound, we can sum the
infinite series. We get the sum as (n2)/(1 –
5/16) which is O(n2)
 Amity School of Engineering & Technology

Assignment-1
Consider the following recurrence
T (n) = 4T(n/2) +n

T(n)= 3 T(n/4) +n2

Obtain the asymptotic bound using recursion

tree, Substitution methods.
 Amity School of Engineering & Technology

Master Method
• It is a direct way to get the solution. The master
method works only for the following type of
recurrences or for recurrences that can be
transformed into the following type.
T(n) = aT(n/b) + f(n)
where a >= 1 and b > 1
There are the following three cases:
• If f(n) = O(nc) where c < Logba then T(n) =
Θ(nLogba)
• If f(n) = Θ(nc) where c = Logba then T(n) = Θ(ncLog
n)
• If f(n) = Ω(nc) where c > Logba then T(n) = Θ(f(n))
 Amity School of Engineering & Technology

Working
• The master method is mainly derived from the
recurrence tree method.
• If we draw the recurrence tree of
T(n) = aT(n/b) + f(n),
• we can see that the work done at the root is f(n),
and work done at all leaves is Θ(nc)
where c is Logba. And the height of the
recurrence tree is Logbn
Amity School of Engineering & Technology
 Amity School of Engineering & Technology

• In the Recurrence Tree Method, we calculate

the total work done.
• If the work done at leaves is polynomial more,
then leaves are the dominant part, and our result
becomes the work done at leaves (Case 1).
• If work done at leaves and root is asymptotically
the same, then our result becomes height
multiplied by work done at any level (Case 2).
• If work done at the root is asymptotically more,
then our result becomes work done at the root
(Case 3).
 Amity School of Engineering & Technology

What is the time complexity of Tower of

Hanoi problem?
Tower of Hanoi is a
mathematical puzzle
where we have three rods
(A, B, and C) and N disks.
Initially, all the disks are stacked in decreasing value of diameter i.e.,
the smallest disk is placed on the top and they are on rod A. The
objective of the puzzle is to move the entire stack to another rod
(here considered C), obeying the following simple rules:
Only one disk can be moved at a time.
Each move consists of taking the upper disk from one of the stacks
and placing it on top of another stack i.e. a disk can only be moved if
it is the uppermost disk on a stack.
No disk may be placed on top of a smaller disk.
 Amity School of Engineering & Technology

• Solution: For Tower of Hanoi, T(n) =

2T(n-1) + c for n>1 and T(1) = 1. Solving
this,
• T(n) = 2T(n-1) + c
• = 2(2T(n-2)+ c) + c
• = 2^2*T(n-2) + (c + 2c)
• = 2^k*T(n-k) + (c + 2c + .. kc)
Substituting k = (n-1), we get
• T(n) = 2^(n-1)*T(1) + (c + 2c + (n-1)c)
• = O(2^n)
 Amity School of Engineering & Technology

Algorithm Design Techniques

• Selecting a proper designing technique for an
algorithm is the most difficult and important task.
Most of the programming problems may have more
than one solution.
• Data structure is a particular way of storing and
organizing data so that it can be used efficiently.
Arrays, trees, linked lists, stacks, graphs, etc. are all
data structures and each of them allows us to
perform different operations on data.
• No matter which programming language you use for
programming, it is important to learn algorithm
design techniques in data structures in order to be
able to build scalable systems.
 Amity School of Engineering & Technology

• Selecting a proper design technique for

algorithms is a complex but important task.
Following are some of the main algorithm
design techniques:
– Brute-force or exhaustive search
– Divide and Conquer
– Greedy Algorithms
– Dynamic Programming
– Branch and Bound Algorithm
– Randomized Algorithm
– Backtracking
 Amity School of Engineering & Technology

Brute-force or exhaustive search

• In computer science, brute-force search or
exhaustive search, also known as generate and
test, is a very general problem-solving technique
and algorithmic paradigm that consists of
systematically enumerating all possible candidates
for the solution and checking whether each
candidate satisfies the problem's statement.
• In order to apply brute-force search to a specific
class of problems, one must implement
four procedures, first, next, valid, and output.
• These procedures should take as a parameter the
data P for the particular instance of the problem that
is to be solved, and should do the following:
 Amity School of Engineering & Technology

• first (P): generate a first candidate solution for P.

• next (P, c): generate the next candidate for P after the
current one c.
• valid (P, c): check whether candidate c is a solution
for P.
• output (P, c): use the solution c of P as appropriate to
the application.
• Algorithm:
c ← first(P)
while c ≠ Λ do
if valid(P,c)
then output(P, c)
c ← next(P, c)
end while
 Amity School of Engineering & Technology
Travelling salesman Problem Statement
• A traveler needs to visit all the cities from a list,
where distances between all the cities are known
and each city should be visited just once. What is
the shortest possible route that he visits each city
exactly once and returns to the origin city?
Amity School of Engineering & Technology
 Amity School of Engineering & Technology

• For each route, we sum the edge

weights based on the graph:
• Route 1: 1 → 2 → 3 → 4 → 1
– Distance: 10+9+12+8= 39
• Route 2: 1 → 2 → 4 → 3 → 1
– Distance: 10+10+9+6 = 35
• Route 3: 1 → 3 → 2 → 4 → 1
– Distance: 15+13+10+8 = 46
 Amity School of Engineering & Technology

• Route 4: 1 → 3 → 4 → 2 → 1
– Distance: 15+12+8+5=40
• Route 5: 1 → 4 → 2 → 3 → 1
– Distance: 20+8+9+6=43
• Route 6: 1 → 4 → 3 → 2 → 1
– Distance: 20+9+13+5=47
 Amity School of Engineering & Technology

• Travelling salesman problem is the

computational problem. We can use brute-force
approach to evaluate every possible tour and
select the best one. For n number of vertices in
a graph, there are (n - 1)! number of
possibilities.

• Minimum Cost =35

 Amity School of Engineering & Technology

Divide and Conquer

• A typical Divide and Conquer algorithm solves a
problem using following three steps.
1. Divide: Break the given problem into sub-problems of same
type. This step involves breaking the problem into smaller sub-
problems. Sub-problems should represent a part of the original
problem. This step generally takes a recursive approach to divide
the problem until no sub-problem is further divisible.
2. Conquer: Recursively solve these subproblems. This step
receives a lot of smaller sub-problems to be solved.
Generally, at this level, the problems are considered 'solved'
on their own.
3. Combine: Appropriately combine the answers. When the
smaller sub-problems are solved, this stage recursively
combines them until they formulate a solution of the original
problem.
 Amity School of Engineering & Technology

• Following are some standard algorithms

that are of the Divide and Conquer
algorithms variety.
• Binary Search
• Quicksort
• Merge Sort
• Median Finding
• Min and Max finding
• Closest Pair of Points
• Strassen’s Algorithm (Matrix Multiplication)
• Cooley–Tukey Fast Fourier Transform (FFT)
algorithm
• The Karatsuba algorithm
 Amity School of Engineering & Technology

Divide the array into smaller subparts

 Amity School of Engineering & Technology

Combine the subparts

Amity School of Engineering & Technology
 Amity School of Engineering & Technology

Examples
 Amity School of Engineering & Technology

Dynamic Programming
• Dynamic programming is an optimization technique,
which divides the problem into smaller sub-problems
and after solving each sub-problem, dynamic
programming combines all the solutions to get
ultimate solution.
• Unlike divide and conquer method, dynamic
programming reuses the solution to the sub-
problems many times.
• Application of Dynamic programming:
– Matrix Chain Multiplication
– Longest Common Subsequence
– Travelling Salesman Problem
– 0/1 Knapsack Problem
 Amity School of Engineering & Technology

Applications of Dynamic Programming

Approach
• Matrix Chain Multiplication
• Longest Common Subsequence
• Travelling Salesman Problem
• 0/1 Knapsack Problem
 Amity School of Engineering & Technology

Branch and Bound

• A branch and bound algorithm is an optimization
technique to get an optimal solution to the problem.
• It looks for the best solution for a given problem in
the entire space of the solution.
• The bounds in the function to be optimized are
merged with the value of the latest best solution.
• It allows the algorithm to find parts of the solution
space completely.
 Amity School of Engineering & Technology

Randomized Algorithm
• An algorithm that uses random numbers to
decide what to do next anywhere in its
logic is called Randomized Algorithm.
• For example, in Randomized Quick Sort,
we use random number to pick the next
pivot (or we randomly shuffle the array).
• Example:
• Randomized Binary Search Algorithm
• Randomized Quick Sort Algorithm
 Amity School of Engineering & Technology

Backtracking Algorithm
• Backtracking is an optimization technique to
solve combinational problems. It is applied to
both programmatic and real-life problems.
• In backtracking, we start with a possible solution,
which satisfies all the required conditions.
• Then we move to the next level and if that level
does not produce a satisfactory solution, we
return one level back and start with a new
option.
 Amity School of Engineering & Technology

Example
 Amity School of Engineering & Technology

Binary Search
• Binary search compares the target value to the
middle element of the array.
• If they are not equal, the half in which the target
cannot lie is eliminated and the search continues
on the remaining half, again taking the middle
element to compare to the target value, and
repeating this until the target value is found.
• If the search ends with the remaining half being
empty, the target is not in the array.
 Amity School of Engineering & Technology

Calculating Time complexity:

At each iteration, the array is divided by half.
So let’s say the length of array at any iteration
is n
• At Iteration 1,Length of array = n
• At Iteration 2,Length of array = n⁄2
• At Iteration 3,Length of array = n⁄22
• Therefore, after Iteration k, Length of array =
n⁄ k
2
 Amity School of Engineering & Technology

Assume After k divisions, the length of

array becomes 1
Therefore Length of array = n⁄2k = 1 => n =
2k
Applying log function on both sides:
=> log2 (n) = log2 (2k)
log2 (n) = k log2 (2)
Therefore, k = log2 (n)
Hence, the time complexity of Binary
Search is
log2 (n)
 Amity School of Engineering & Technology
Time complexity Of Binary
Search

Worst-case performance O(log n)

Best-case performance O(1)

Average performance O(log n)

 Amity School of Engineering & Technology

Quick Sort
• Quicksort is a sorting algorithm.
• The algorithm picks a pivot element,
rearranges the array elements in such a
way that all elements smaller than the
picked pivot element move to left side of
pivot, and all greater elements move to
right side.
• Finally, the algorithm recursively sorts the
subarrays on left and right of pivot
element.
Amity School of Engineering & Technology
 Amity School of Engineering & Technology
Time complexity Of Quick Sort

2
Worst-case performance O( n )

Best-case performance O(nlog n)

Average performance O(nlog n)

 Amity School of Engineering & Technology

Merge Sort
• Merge Sort is a Divide and Conquer algorithm.
• It divides input array in two halves, calls itself for
the two halves and then merges the two sorted
halves.
• The merge() function is used for merging two
halves.
• The merge(arr, l, m, r) is key process that
assumes that arr[l..m] and arr[m+1..r] are sorted
and merges the two sorted sub-arrays into one.
Amity School of Engineering & Technology
 Amity School of Engineering & Technology

Time complexity

T(n)=2T(n/2) + O(n)

So, T(n) = O(n log n) for each case

 Amity School of Engineering & Technology
Time complexity Of Merge Sort

Worst-case performance O(nlog n)

Best-case performance O(nlog n)

Average performance O(nlog n)

 Amity School of Engineering & Technology

Strassen’s Matrix Multiplication

• Given two square matrices A and B of size N x N each,
find their multiplication matrix. (Naive Method)
void multiply(int A[][N], int B[][N], int C[][N])
{ for (int i = 0; i < N; i++)
{ for (int j = 0; j < N; j++)
{ C[i][j] = 0;
for (int k = 0; k < N; k++)
{ C[i][j] += A[i][k]*B[k][j];
}
}
}
} Time Complexity of above method is O(N3).
 Amity School of Engineering & Technology

Divide and Conquer

• Following is simple Divide and Conquer
method to multiply two square matrices.
• Divide matrices A and B in 4 sub-matrices
of size N/2 x N/2 as shown in the below
diagram.
 Amity School of Engineering & Technology

• In the above method, we do 8 multiplications for

matrices of size N/2 x N/2 and 4 additions.
Addition of two matrices takes O(N2) time. So
the time complexity can be written as
T(N) = 8T(N/2) + O(N2)
time complexity of above method is O(N3) which is
unfortunately same as the above naive method.
In the above divide and conquer method, the main
component for high time complexity is 8 recursive
calls.
The idea of Strassen’s method is to reduce the
number of recursive calls to 7.
 Amity School of Engineering & Technology

• Strassen’s method is similar to above simple

divide and conquer method in the sense that this
method also divide matrices to sub-matrices of
size N/2 x N/2 as shown in the above diagram,
but in Strassen’s method, the four sub-matrices
of result are calculated using following formulae.
 Amity School of Engineering & Technology

P = (A11+ A22) *(B11+B22)

Q = (A21 + A22) * B11
R = A11 * (B12 - B22)
S = A22 * (B21 - B11)
T= (A11 + A12) * B22
U = (A21 - A11) * (B11 + B12)
V= (A12 - A22) * (B21 + B22)

C11 = P + S - T+ V
C12 = R+ T
C21 = Q + S
C22 = P + R - Q + U
 Amity School of Engineering & Technology

Time Complexity of Strassen’s Method

• Addition and Subtraction of two matrices takes

O(N2) time. So time complexity can be written as

T(N) = 7T(N/2) + O(N2)

time complexity of above method is O(Nlg7) which

is approximately O(N2.8074)
 Amity School of Engineering & Technology

Answer
 Amity School of Engineering & Technology

Answer
 Amity School of Engineering & Technology

Greedy Approach
Greedy algorithms build a solution part by part,
choosing the next part in such a way, that it gives an
immediate benefit.
This approach never reconsiders the choices taken
previously.
This approach is mainly used to solve optimization
problems.
Greedy method is easy to implement and quite
efficient in most of the cases.
Hence, we can say that Greedy algorithm is an
algorithmic paradigm based on heuristic that follows
local optimal choice at each step with the hope of
finding global optimal solution.
 Amity School of Engineering & Technology

Huffman Coding
• Huffman Coding is a famous Greedy Algorithm.
• It is used for the lossless compression of data.
• It uses variable length encoding.
• It assigns variable length code to all the
characters.
• The code length of a character depends on how
frequently it occurs in the given text.
• The character which occurs most frequently gets
the smallest code.
• The character which occurs least frequently gets
the largest code.
• It is also known as Huffman Encoding.
 Amity School of Engineering & Technology

Prefix Rule
• Huffman Coding implements a rule known
as a prefix rule.
• This is to prevent the ambiguities while
decoding.
• It ensures that the code assigned to any
character is not a prefix of the code
assigned to any other character.
 Amity School of Engineering & Technology

Steps in Huffman Coding

• Building a Huffman Tree from the input
characters.
• Assigning code to the characters by traversing
the Huffman Tree.
Step-01:
• Create a leaf node for each character of the text.
• Leaf node of a character contains the occurring
frequency of that character.
Step-02:
• Arrange all the nodes in increasing order of their
frequency value.
 Amity School of Engineering & Technology

Step-03:
Considering the first two nodes having minimum
frequency,
• Create a new internal node.
• The frequency of this new node is the sum of
frequency of those two nodes.
• Make the first node as a left child and the other
node as a right child of the newly created node.
Step-04:
• Keep repeating Step-02 and Step-03 until all the
nodes form a single tree.
• The tree finally obtained is the desired Huffman
Tree.
 Amity School of Engineering & Technology

Total number of bits in Huffman encoded message

= Total number of characters in the message x
Average code length per character
= ∑ ( frequencyi x Code lengthi )
 Amity School of Engineering & Technology

Problem
A file contains the following characters with the frequencies as
shown. If Huffman Coding is used for data compression,
determine-
• Length of Huffman encoded message (in bits)
• Huffman Code for each character
• Average code length Characters Frequencies
a 10
e 15
i 12
o 3
u 4
s 13
t 1
 Amity School of Engineering & Technology

Solution
• Step-01

• Step-02
 Amity School of Engineering & Technology

• Step -03
 Amity School of Engineering & Technology

• Step -04
 Amity School of Engineering & Technology

• Step -05
 Amity School of Engineering & Technology

• Step -06
 Amity School of Engineering & Technology

• Step -07
 Amity School of Engineering & Technology

• Step -08
 Amity School of Engineering & Technology

• Step -09
 Amity School of Engineering & Technology

• Step- 10
 Amity School of Engineering & Technology

Now,
• We assign weight to all the edges of the
constructed Huffman Tree.
• Let us assign weight ‘0’ to the left edges and
weight ‘1’ to the right edges.
 Amity School of Engineering & Technology

Rule
• If you assign weight ‘0’ to the left edges, then
assign weight ‘1’ to the right edges.
• If you assign weight ‘1’ to the left edges, then
assign weight ‘0’ to the right edges.
• Any of the above two conventions may be
followed.
• But follow the same convention at the time of
decoding that is adopted at the time of encoding.
Amity School of Engineering & Technology
 Amity School of Engineering & Technology

1. Huffman Code For Characters-

• The Huffman Code for each character is-
• a = 111
• e = 10
• i = 00
• o = 11001
• u = 1101
• s = 01
• t = 11000
 Amity School of Engineering & Technology

2. Average Code Length-

Average code length
= ∑ ( frequencyi x code lengthi ) / ∑ (
frequencyi )
= { (10 x 3) + (15 x 2) + (12 x 2) + (3 x 5) +
(4 x 4) + (13 x 2) + (1 x 5) } / (10 + 15 + 12 +
3 + 4 + 13 + 1)
= 2.52
3. Length of Huffman Encoded Message-
• 146
 Amity School of Engineering & Technology

Problem-1
Amity School of Engineering & Technology
 Amity School of Engineering & Technology

Knapsack Problem
The problem states-
Which items should be placed into the knapsack
such that-
• The value or profit obtained by putting the items
into the knapsack is maximum.
• The weight limit of the knapsack does not exceed.
Knapsack problem has the following two variants-

• Fractional Knapsack Problem

• 0/1 Knapsack Problem
 Amity School of Engineering & Technology

In Fractional Knapsack Problem,

• We can even put the fraction of any item into the
knapsack if taking the complete item is not possible.
• It is solved using Greedy Method.
Step-01:
For each item, compute its value / weight ratio.
Step-02:
Arrange all the items in decreasing order of their value
/ weight ratio.
Step-03:
• Start putting the items into the knapsack beginning
from the item with the highest ratio.
• Put as many items as you can into the knapsack.
 Amity School of Engineering & Technology

Problem - 1
• For the given set of items and knapsack capacity
= 60 kg, find the optimal solution for the
fractional knapsack problem making use of
greedy approach.
 Amity School of Engineering & Technology

Solution
Step-01:
Compute the value / weight ratio for each item-
 Amity School of Engineering & Technology
Step-02:
Sort all the items in decreasing order of their value /
weight ratio-
I1 I2 I5 I4 I3
(6) (4) (3.6) (3.5) (3)
Step-03:
Start filling the knapsack by putting the items into
it one by one.
 Amity School of Engineering & Technology

Now,
• Knapsack weight left to be filled is 20 kg but
item-4 has a weight of 22 kg.
• Since in fractional knapsack problem, even the
fraction of any item can be taken.
• So, knapsack will contain the following items-
• < I1 , I2 , I5 , (20/22) I4 >
Total cost of the knapsack
= 160 + (20/22) x 77
= 160 + 70
= 230 units
 Amity School of Engineering & Technology

Problem-2
Consider 5 items along their respective
weights and values: -
I = (I1,I2,I3,I4,I5)
w = (5, 10, 20, 30, 40)
P = (30, 20, 100, 90,160)
The capacity of knapsack W = 60

Answer: 270
 Amity School of Engineering & Technology

Prim’s Algorithm
• Prim’s Algorithm is a famous greedy
algorithm.
• It is used for finding the Minimum
Spanning Tree (MST) of a given
graph.
• To apply Prim’s algorithm, the given
graph must be weighted, connected
and undirected.
 Amity School of Engineering & Technology

Step-01:
Randomly choose any vertex.
• The vertex connecting to the edge having least weight
is usually selected.
Step-02:
Find all the edges that connect the tree to new vertices.
• Find the least weight edge among those edges and
include it in the existing tree.
• If including that edge creates a cycle, then reject that
edge and look for the next least weight edge.
Step-03:
• Keep repeating step-02 until all the vertices are
included and Minimum Spanning Tree (MST) is
obtained.
 Amity School of Engineering & Technology

Problem-01
 Amity School of Engineering & Technology

Solution

• Now, Cost of Minimum Spanning Tree

• = Sum of all edge weights
• = 10 + 25 + 22 + 12 + 16 + 14
• = 99 units
 Amity School of Engineering & Technology

Problem-02
 Amity School of Engineering & Technology

• Now, Cost of Minimum Spanning Tree

• = Sum of all edge weights
• = 1 + 4 + 2 + 6 + 3 + 10
• = 26 units
 Amity School of Engineering & Technology

Kruskal’s Algorithm
• Kruskal’s Algorithm is a famous greedy
algorithm.
• It is used for finding the Minimum
Spanning Tree (MST) of a given graph.
• To apply Kruskal’s algorithm, the given
graph must be weighted, connected and
undirected.
 Amity School of Engineering & Technology

Kruskal’s Algorithm Implementation

Step-01:
Sort all the edges from low weight to high weight.
Step-02:
Take the edge with the lowest weight and use it to
connect the vertices of graph.
• If adding an edge creates a cycle, then reject that
edge and go for the next least weight edge.
Step-03:
• Keep adding edges until all the vertices are
connected and a Minimum Spanning Tree (MST) is
obtained.
 Amity School of Engineering & Technology

Problem
 Amity School of Engineering & Technology

Solution
 Amity School of Engineering & Technology

Dijkstra Algorithm
• Dijkstra Algorithm is a very famous
greedy algorithm.
• It is used for solving the single source
shortest path problem.
• It computes the shortest path from
one particular source node to all other
remaining nodes of the graph.
 Amity School of Engineering & Technology

Conditions
It is important to note the following points regarding Dijkstra
Algorithm-
• Dijkstra algorithm works only for connected graphs.
• Dijkstra algorithm works only for those graphs that do not
contain any negative weight edge.
• The actual Dijkstra algorithm does not output the
shortest paths.
• It only provides the value or cost of the shortest paths.
• By making minor modifications in the actual algorithm,
the shortest paths can be easily obtained.
• Dijkstra algorithm works for directed as well as
undirected graphs.
 Amity School of Engineering & Technology

Dijkstra Algorithm have following steps-

Step-01:
• In the first step. two sets are defined-
• One set contains all those vertices which
have been included in the shortest path tree.
• In the beginning, this set is empty.
• Other set contains all those vertices which
are still left to be included in the shortest path
tree.
• In the beginning, this set contains all the
vertices of the given graph.
 Amity School of Engineering & Technology

Step-02:
For each vertex of the given graph,
two variables are defined as-
• Π[v] which denotes the predecessor
of vertex ‘v’
• d[v] which denotes the shortest path
estimate of vertex ‘v’ from the source
vertex.
 Amity School of Engineering & Technology

Initially, the value of these variables is

set as-
• The value of variable ‘Π’ for each
vertex is set to NIL i.e. Π[v] = NIL
• The value of variable ‘d’ for source
vertex is set to 0 i.e. d[S] = 0
• The value of variable ‘d’ for remaining
vertices is set to ∞ i.e. d[v] = ∞
 Amity School of Engineering & Technology

Step-03:

• The following procedure is repeated until

all the vertices of the graph are processed-
• Among unprocessed vertices, a vertex
with minimum value of variable ‘d’ is
chosen.
• Its outgoing edges are relaxed.
• After relaxing the edges for that vertex, the
sets created in step-01 are updated.
 Amity School of Engineering & Technology

Edge Relaxation

• Here, d[a] and d[b] denotes the shortest

path estimate for vertices a and b
respectively from the source vertex ‘S’.
 Amity School of Engineering & Technology

Now,

If d[a] + w < d[b]

then d[b] = d[a] + w and Π[b] = a

This is called as edge relaxation.

 Amity School of Engineering & Technology

Problem
 Amity School of Engineering & Technology

Solution
Step-01:
The following two sets are created-
• Unvisited set : {S , a , b , c , d , e}
• Visited set : { }
Step-02:
The two variables Π and d are created
for each vertex and initialized as-
• Π[S] = Π[a] = Π[b] = Π[c] = Π[d] = Π[e] = NIL
• d[S] = 0
• d[a] = d[b] = d[c] = d[d] = d[e] = ∞
 Amity School of Engineering & Technology

Step-03:
Vertex ‘S’ is chosen.
• This is because shortest path
estimate for vertex ‘S’ is least.
• The outgoing edges of vertex ‘S’ are
relaxed.
 Amity School of Engineering & Technology

• Before Edge Relaxation

• After edge relaxation, our shortest path

tree is
 Amity School of Engineering & Technology

Now, the sets are updated as-

• Unvisited set : {a , b , c , d , e}
• Visited set : {S}

Step-04:
Vertex ‘a’ is chosen.
• This is because shortest path estimate for
vertex ‘a’ is least.
• The outgoing edges of vertex ‘a’ are
relaxed.
 Amity School of Engineering & Technology

Before Edge Relaxation

 Amity School of Engineering & Technology

After edge relaxation, our shortest

path tree is-
 Amity School of Engineering & Technology

• Now Follow steps until all nodes are

visited.
Shortest path tree
 Amity School of Engineering & Technology

Bellman-Ford algorithm
• The Bellman-Ford algorithm is a suitable
alternative to Dijkstra’s algorithm as it
accommodates negative edge weights.
• Step – 1 Initialize the distance to the source
vertex as 0, and the distance to all other vertices
as infinity.
• Step – 2 Relax all edges in the graph |V| – 1
times, where |V| is the number of vertices in the
graph. For each edge (u, v) with weight w, check
if the distance from the source vertex to v can be
reduced by going through u. If so, update the
distance to v to the new, shorter distance.
 Amity School of Engineering & Technology

• Step – 3 Check for negative weight cycles.

If there is a negative weight cycle in the
graph, the algorithm will never converge
and will keep reducing the distance to
some vertices with each iteration. To
detect such cycles, repeat step 2 one
more time. If any distance is updated in
this extra iteration, there must be a
negative weight cycle in the graph.
• Step – 4 If there is no negative weight
cycle, the shortest distance to each vertex
from the source vertex has been found.
 Amity School of Engineering & Technology

Negative cycles
What is the shortest path from a to e?

1
1 B D

5
A
10 -10
E
C
3
a. 7
b. 5
 Amity School of Engineering & Technology

Bellman-Ford algorithm
10 How many edges is
S A
the shortest path
8 1
from s to:
-4 B
G A:
2
1 1

-2
F C

-1 3
E D
-1
 Amity School of Engineering & Technology

Bellman-Ford algorithm
10 How many edges is
S A
the shortest path
8 1
from s to:
-4 B
G A: 3
2
1 1

-2
F C

-1 3
E D
-1
 Amity School of Engineering & Technology

Bellman-Ford algorithm
10 How many edges is
S A
the shortest path
8 1
from s to:
-4 B
G A: 3
2
1 1

-2
C B:
F
-1 3
E D
-1
 Amity School of Engineering & Technology

Bellman-Ford algorithm
10 How many edges is
S A
the shortest path
8 1
from s to:
-4 B
G A: 3
2
1 1

-2
C B: 5
F
-1 3
E D
-1
 Amity School of Engineering & Technology

Bellman-Ford algorithm
10 How many edges is
S A
the shortest path
8 1
from s to:
-4 B
G A: 3
2
1 1

-2
C B: 5
F
-1 3
E D D:
-1
 Amity School of Engineering & Technology

Bellman-Ford algorithm
10 How many edges is
S A
the shortest path
8 1
from s to:
-4 B
G A: 3
2
1 1

-2
C B: 5
F
-1 3
E D D: 7
-1
 Amity School of Engineering & Technology

Bellman-Ford algorithm
0 
10
S A Iteration: 0
8 1


 G -4 B
2
1 1

-2 
F C


-1 3
E D
-1
 
 Amity School of Engineering & Technology
Bellman-Ford algorithm
0 10
10
S A Iteration: 1
8 1


8 -4 B
G
2
1 1

-2 
F C


-1 3
E D
-1
 
 Amity School of Engineering & Technology
Bellman-Ford algorithm
0 10
10
S A Iteration: 2
8 1


8 -4 B
G
2
1 1

-2 
F C
9

-1 3
E D
-1
12 
 Amity School of Engineering & Technology
Bellman-Ford algorithm
0 5
10
S A Iteration: 3
8 1
10

8 G -4 B A has the correct

2 distance and path
1 1

-2 
F C
9

-1 3
E D
-1
8 
 Amity School of Engineering & Technology
Bellman-Ford algorithm
0 5
10
S A Iteration: 4
8 1
6

8 -4 B
G
2
1 1

-2 11
F C
9

-1 3
E D
-1
7 
 Amity School of Engineering & Technology
Bellman-Ford algorithm
0 5
10
S A Iteration: 5
8 1
5

8 G -4 B B has the correct

2 distance and path
1 1

-2 7
F C
9

-1 3
E D
-1
7 14
 Amity School of Engineering & Technology
Bellman-Ford algorithm
0 5
10
S A Iteration: 6
8 1
5

8 -4 B
G
2
1 1

-2 6
F C
9

-1 3
E D
-1
7 10
 Amity School of Engineering & Technology
Bellman-Ford algorithm
0 5
10
S A Iteration: 7
8 1
5

8 G -4 B D (and all other

2 nodes) have the
1 1 correct distance
and path
-2 6
F C
9

-1 3
E D
-1
7 9
 Amity School of Engineering & Technology

Convex Hull
• In computational geometry, a convex hull is the
smallest convex polygon that contains a given
set of points. It is a fundamental concept with
applications in various fields such as computer
graphics, robotics, and image processing.
 Amity School of Engineering & Technology

Convexity
 A set C  R2 is convex if for all two points
p,qC the line segment pq is fully contained
in C.

convex non-convex
 Amity School of Engineering & Technology

Convex Hull
 The convex hull CH(P) of a point set P  R2 is the
smallest convex set C  P. In other words CH(P) =
C. CP
C convex

P
 Amity School of Engineering & Technology

Convex Hull
 Observation: CH(P) is the unique convex polygon whose
vertices are points of P and which contains all points of P.
 We represent the convex hull as the sequence of
points on the convex hull polygon (the boundary of the
convex hull), in counter-clockwise order.
4
5 3

6
2

0 1
 Amity School of Engineering & Technology

Convex Hull: Runtime

 Runtime Recurrence:
T(n) = 2 T(n/2) + cn
 Solves to T(n) = (n log n)
1. Divide: Divide set of points in half.
2. Conquer: Recursively compute convex hulls of 2
halves.
3. Combine: Linear-time merge.

T(n) = 2 T(n/2) + O(n)

subproblem size work dividing and

# subproblems combining
 Amity School of Engineering & Technology

Recurrence (cont’d)

(1) if n = 1;
T(n) =
2T(n/2) + (n) if n > 1.

• How do we solve T(n)? I.e., how do

we find out if it is O(n) or O(n2) or …?
 Amity School of Engineering & Technology

Recursion tree
Solve T(n) = 2T(n/2) + dn, where d > 0 is constant.
T(n)
 Amity School of Engineering & Technology

Recursion tree
Solve T(n) = 2T(n/2) + dn, where d > 0 is constant.
dn

T(n/2) T(n/2)
 Amity School of Engineering & Technology

Recursion tree
Solve T(n) = 2T(n/2) + dn, where d > 0 is constant.
dn
dn/2 dn/2

T(n/4) T(n/4) T(n/4) T(n/4)

 Amity School of Engineering & Technology

Recursion tree
Solve T(n) = 2T(n/2) + dn, where d > 0 is constant.
dn

dn/2 dn/2

dn/4 dn/4 dn/4 dn/4

(1)
 Amity School of Engineering & Technology

Recursion tree
Solve T(n) = 2T(n/2) + dn, where d > 0 is constant.
dn

dn/2 dn/2
h = log n dn/4 dn/4 dn/4 dn/4

(1)
 Amity School of Engineering & Technology

Recursion tree
Solve T(n) = 2T(n/2) + dn, where d > 0 is constant.
dn dn

dn/2 dn/2
h = log n dn/4 dn/4 dn/4 dn/4

(1)
 Amity School of Engineering & Technology

Recursion tree
Solve T(n) = 2T(n/2) + dn, where d > 0 is constant.
dn dn

dn/2 dn/2 dn
h = log n dn/4 dn/4 dn/4 dn/4

(1)
 Amity School of Engineering & Technology

Recursion tree
Solve T(n) = 2T(n/2) + dn, where d > 0 is constant.
dn dn

dn/2 dn/2 dn
h = log n dn/4 dn/4 dn/4 dn/4 dn

…
(1)
 Amity School of Engineering & Technology

Recursion tree
Solve T(n) = 2T(n/2) + dn, where d > 0 is constant.
dn dn

dn/2 dn/2 dn
h = log n dn/4 dn/4 dn/4 dn/4 dn

…
(1) #leaves = n (n)
 Amity School of Engineering & Technology

Recursion tree
Solve T(n) = 2T(n/2) + dn, where d > 0 is constant.
dn dn

dn/2 dn/2 dn
h = log n dn/4 dn/4 dn/4 dn/4 dn

…
(1) #leaves = n (n)
Total (n log n)
 Amity School of Engineering & Technology
Job Sequencing With Deadlines
The sequencing of jobs on a single processor
with deadline constraints is called as Job
Sequencing with Deadlines.
Here-
• You are given a set of jobs.
• Each job has a defined deadline and some
profit associated with it.
• The profit of a job is given only when that job is
completed within its deadline.
• Only one processor is available for processing
all the jobs.
• Processor takes one unit of time to complete a
job.
 Amity School of Engineering & Technology

• The problem states-

“How can the total profit be maximized
if only one job can be completed at a
time?”
 Amity School of Engineering & Technology

Approach to Solution
• A feasible solution would be a subset of
jobs where each job of the subset gets
completed within its deadline.
• Value of the feasible solution would be the
sum of profit of all the jobs contained in
the subset.
• An optimal solution of the problem would
be a feasible solution which gives the
maximum profit.
 Amity School of Engineering & Technology

Greedy Algorithm-
Step-01:
Sort all the given jobs in decreasing order of their
profit.
Step-02:
Check the value of maximum deadline.
• Draw a Gantt chart where maximum time on
Gantt chart is the value of maximum deadline.
Step-03:
• Pick up the jobs one by one.
• Put the job on Gantt chart as far as possible
from 0 ensuring that the job gets completed
before its deadline.
 Amity School of Engineering & Technology

Problem
• Given the jobs, their deadlines and
associated profits as shown-

Jobs J1 J2 J3 J4 J5 J6

Deadlines 5 3 3 2 4 2

Profits 200 180 190 300 120 100

 Amity School of Engineering & Technology

Answer the following questions-

• Write the optimal schedule that gives
maximum profit.
• Are all the jobs completed in the optimal
schedule?
• What is the maximum earned profit?
 Amity School of Engineering & Technology

Solution
Step-01:
Sort all the given jobs in decreasing order of
their profit-

Jobs J4 J1 J3 J2 J5 J6
Deadlines 2 5 3 3 4 2

Profits 300 200 190 180 120 100

 Amity School of Engineering & Technology

• Step-02:
• Value of maximum deadline = 5.
• So, draw a Gantt chart with maximum time on
Gantt chart = 5 units as shown-

Now,
• We take each job one by one in the order they
appear in Step-01.
• We place the job on Gantt chart as far as
possible from 0.
 Amity School of Engineering & Technology

Step-03:
We take job J4. Since its deadline is 2, so we
place it in the first empty cell before deadline 2
as-

Step-04:
• We take job J1. Since its deadline is 5, so we
place it in the first empty cell before deadline
5 as-
 Amity School of Engineering & Technology

Step-05:
• We take job J3.
• Since its deadline is 3, so we place it in
the first empty cell before deadline 3 as-
 Amity School of Engineering & Technology

Step-06:
• We take job J2.
• Since its deadline is 3, so we place it in
the first empty cell before deadline 3.
• Since the second and third cells are
already filled, so we place job J2 in the
first cell as-
 Amity School of Engineering & Technology

Step-07:
• Now, we take job J5.
• Since its deadline is 4, so we place it in
the first empty cell before deadline 4 as-

Now,
• The only job left is job J6 whose deadline is 2.
• All the slots before deadline 2 are already
occupied.
• Thus, job J6 can not be completed.
 Amity School of Engineering & Technology

• Part-01:
• The optimal schedule is-
J2 , J4 , J3 , J5 , J1
• This is the required order in which the jobs
must be completed in order to obtain the
maximum profit.
Part-02:
All the jobs are not completed in optimal
schedule.
• This is because job J6 could not be
completed within its deadline.
 Amity School of Engineering & Technology

Part-03:
Maximum earned profit
= Sum of profit of all the jobs in optimal
schedule
= Profit of job J2 + Profit of job J4 + Profit of
job J3 + Profit of job J5 + Profit of job J1
= 180 + 300 + 190 + 120 + 200
= 990 units
 Amity School of Engineering & Technology

Problem-1

Job J1 J2 J3 J4 J5

Deadline 2 1 3 2 1

Profit 60 100 20 40 20
 Amity School of Engineering & Technology

Solution
• The solution is the sequence of jobs (J2,
J1, J3), which are being executed within
their deadline and gives maximum profit.

• Total profit of this sequence is 100 + 60 +

20 = 180.
 Amity School of Engineering & Technology

Problem-2
• JobID Deadline Profit
a 4 20
b 1 10
c 1 40
d 1 30

Answer: c, a
 Amity School of Engineering & Technology

Problem-3
JobID Deadline Profit
a 2 100
b 1 19
c 2 27
d 1 25
e 3 15

Answer: c, a, e
 Amity School of Engineering & Technology

All pair shortest path( Floyd-

Warshall algorithm)
The Floyd Warshall Algorithm is for solving
the All Pairs Shortest Path problem.
The problem is to find shortest distances
between every pair of vertices in a given
edge weighted directed Graph.
 Amity School of Engineering & Technology

Algorithm
FLOYD - WARSHALL (W)
n ← rows [W].
D0 ← W
for k ← 1 to n
do for i ← 1 to n
do for j ← 1 to n
do dij(k) ← min (dij(k-1),dik(k-1)+dkj(k-1) )
return D(n)
 Amity School of Engineering & Technology
Problem

• Using Floyd Warshall Algorithm, find the

shortest path distance between every pair
of vertices.
 Amity School of Engineering & Technology

Step-01:
• Remove all the self loops and parallel edges (keeping the
lowest weight edge) from the graph.
• In the given graph, there are neither self edges nor
parallel edges.
Step-02:
• Write the initial distance matrix.
• It represents the distance between every pair of vertices
in the form of given weights.
• For diagonal elements (representing self-loops), distance
value = 0.
• For vertices having a direct edge between them, distance
value = weight of that edge.
• For vertices having no direct edge between them,
distance value = ∞.
 Amity School of Engineering & Technology

• Initial distance matrix for the given graph

is-
 Amity School of Engineering & Technology

Step-03:
Using Floyd Warshall Algorithm, write the following 4
matrices-
 Amity School of Engineering & Technology

The last matrix D4 represents the shortest path

distance between every pair of vertices.
 Amity School of Engineering & Technology

Problem
 Amity School of Engineering & Technology

Problem
 Amity School of Engineering & Technology

Problem
 Amity School of Engineering & Technology

Problem
 Amity School of Engineering & Technology

0/1 knapsack problem

In 0/1 Knapsack Problem,
• As the name suggests, items are indivisible
here.
• We can not take the fraction of any item.
• We have to either take an item completely
or leave it completely.
• It is solved using dynamic programming
approach.
 Amity School of Engineering & Technology

Find the optimal solution for the 0/1

knapsack problem making use of dynamic
programming approach. Consider-
n=4
C= 8kg
P= (1,2,5,6)
W= (2,3, 4, 5)
 Amity School of Engineering & Technology

0/1 Knapsack Problem Using Dynamic

Programming
Step-01:
• Draw a table say ‘T’ with (n+1) number of
rows and (C+1) number of columns.
• Fill all the boxes of 0th row and 0th column
with zeroes as shown-
Amity School of Engineering & Technology
 Amity School of Engineering & Technology

Step-02:
• Start filling the table row wise top to bottom
from left to right.
• Use the following formula-

T (i , j) = max { T ( i-1 , j ) , valuei + T( i-1 , j –

weighti ) }
Here, T(i , j) = maximum value of the selected items
if we can take items 1 to i and have weight
restrictions of j.
 Amity School of Engineering & Technology

Step-03:
To identify the items that must be put into the
knapsack to obtain that maximum profit,
• Consider the last column of the table.
• Start scanning the entries from bottom to top.
• On encountering an entry whose value is not
same as the value stored in the entry
immediately above it, mark the row label of
that entry.
• After all the entries are scanned, the marked
labels represent the items that must be put
into the knapsack.
 Amity School of Engineering & Technology

Problem-2
Find the optimal solution for the 0/1 knapsack
problem making use of dynamic programming
approach. Consider-
n=4
C= 5 kg
(w1, w2, w3, w4) = (2, 3, 4, 5)
(b1, b2, b3, b4) = (3, 4, 5, 6)
 Amity School of Engineering & Technology

https://www.gatevidyalay.com/0-1-knapsack-problem-using-dynamic-
programming-approach/
Amity School of Engineering & Technology
 Amity School of Engineering & Technology

Problem-3
Find the optimal solution for the 0/1
knapsack problem making use of dynamic
programming approach. Consider-
n=5
C= 11 kg
(w1, w2, w3, w4,w5) = (1,2,5,6,7)
(p1,p2,p3,p4,p5) = (1,6,18,22,28)
 Amity School of Engineering & Technology

Answer
• Max profit-40
• (0,0,1,1,0)
 Amity School of Engineering & Technology

Backtracking
• Backtracking is a problem-solving algorithmic technique
that involves finding a solution incrementally by
trying different options and undoing them if they lead
to a dead end.
• It is commonly used in situations where you need to
explore multiple possibilities to solve a problem, like
searching for a path in a maze or solving puzzles like
Sudoku.
• Problems associated with backtracking can be
categorized into 3 categories:
– Decision Problems: Here, we search for a feasible solution.
– Optimization Problems: For this type, we search for the best
solution.
– Enumeration Problems: We find set of all possible feasible
solutions to the problems of this type.
 Amity School of Engineering & Technology

• Problem: You want to find all the possible ways of

arranging 2 boys and 1 girl on 3 benches. Constraint:
Girl should not be on the middle bench.
• Solution: There are a total of 3! = 6 possibilities. We will
try all the possibilities and get the possible solutions. We
recursively try all the possibilities.
• All the possibilities are:
 Amity School of Engineering & Technology

State tree with all the solutions

 Amity School of Engineering & Technology

N-Queens Problem
• N - Queens problem is to place n - queens
in such a manner on an n x n chessboard
that no queens attack each other by being
in the same row, column or diagonal.
• It can be seen that for n =1, the problem
has a trivial solution, and no solution exists
for n =2 and n =3. So first we will consider
the 4 queens problem and then generate it
to n - queens problem.
 Amity School of Engineering & Technology

• Since, we have to place 4 queens such as

q1 q2 q3 and q4 on the chessboard, such that no
two queens attack each other. In such a
conditional each queen must be placed on a
different row, i.e., we put queen "i" on row "i.“
• The implicit tree for 4 - queen problem for a
solution (2, 4, 1, 3) is as follows:
Amity School of Engineering & Technology
 Amity School of Engineering & Technology

Hamiltonian Circuit Problems

• A Hamiltonian Cycle or Circuit is a path
in a graph that visits every vertex exactly
once and returns to the starting vertex,
forming a closed loop.
• A graph is said to be a Hamiltonian
graph only when it contains a hamiltonian
cycle, otherwise, it is called non-
Hamiltonian graph.
 Amity School of Engineering & Technology

• Suppose the given undirected graph G(V, E) and

its adjacency matrix are as follows −

• The backtracking algorithm can be used to find a

Hamiltonian path in the above graph. If found,
the algorithm returns the path. If not, it returns
false. For this case, the output should be (0, 1,
2, 4, 3, 0).
 Amity School of Engineering & Technology

• The naive way to solve Hamiltonian cycle problem is by

generating all possible configurations of vertices and
checking if any configuration satisfies the given
constraints. However, this approach is not suitable for
large graphs as its time complexity will be (O(N!)).
• The following steps explain the working of backtracking
approach −
– First, create an empty path array and add a starting vertex
0 to it.
– Next, start with vertex 1 and then add other vertices one
by one.
– While adding vertices, check whether a given vertex is
adjacent to the previously added vertex and hasn't been
added already.
– If any such vertex is found, add it to the path as part of the
solution, otherwise, return false.
 Amity School of Engineering & Technology

Sum of Subsets
• You will be given a set of non-negative integers
and a value of variable sum, and you must
determine if there is a subset of the given set
with a sum equal to a given sum.
• For the recursion based approach, you will look
at two scenarios:
– Start with the last element and work your way up to
the goal sum by subtracting the value of the 'last'
element from the total number of elements.
– 'Final' element will be removed, and the required sum
will equal the target sum, with the number of elements
equal to the total elements minus 1.
Amity School of Engineering & Technology
 Amity School of Engineering & Technology

Graph Coloring
• Graph Coloring is the process of assigning colors to
the vertices of a graph in such a way that no two
adjacent vertices have the same color, while
minimizing the total number of colors used.
• This is also called the vertex coloring problem. If
coloring is done using at most m colors, it is called
m-coloring.
 Amity School of Engineering & Technology

Chromatic Number
• The minimum number of colors needed to color a
graph is called its chromatic number. For example,
the following can be colored a minimum of 2 colors.
 Amity School of Engineering & Technology

• The problem of finding a chromatic number of

a given graph is NP-complete.
• Graph coloring problem is both, a decision
problem as well as an optimization
problem.
• A decision problem is stated as, “With given
M colors and graph G, whether a such color
scheme is possible or not?”.
• The optimization problem is stated as, “Given
M colors and graph G, find the minimum
number of colors required for graph coloring.”
 Amity School of Engineering & Technology

Thanks
Further Study:
1. E. Horowitz & S Sahni, "Fundamentals of Computer
Algorithms",
2. Thomas H. Coreman, Charles E. Leiserson and Ronald
L. Rivest, “Introduction to Algorithms”, Printice Hall of
India.
3. www.geeksforgeeks.org
4. https://Javatpoint.com
5. https://www.gatevidyalay.com/
6. https://www.tutorialspoint.com/