ITT304 Algorithm Analysis and Design

Dr. Visakh R.
Assistant Professor, Dept. of Information Technology
Government Engineering College Barton Hill

Module 3

February 27, 2026

Outline

1 Greedy Algorithm Design

Basics

2 Minimum-Cost Spanning Tree

MST Concept
Prim’s Algorithm
Kruskal’s Algorithm

3 Job Sequencing with Deadlines

4 Knapsack Problem

5 0/1 Knapsack Problem

6 Longest Common Subsequence Problem

 Greedy Algorithm Design
Minimum-Cost Spanning Tree
Job Sequencing with Deadlines
Basics
Knapsack Problem
0/1 Knapsack Problem
Longest Common Subsequence Problem

Basics

Given a problem having n inputs, we have to obtain a subset

that satisfies some constraints

Any subset that satisfies those constraints is called a feasible

solution

We need to find a feasible solution that either maximizes or

minimizes a given objective function

A feasible solution that does this is called an optimal solution

There is an obvious way to determine a feasible solution but

not necessarily an optimal solution

3 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
Job Sequencing with Deadlines
Basics
Knapsack Problem
0/1 Knapsack Problem
Longest Common Subsequence Problem

Basics (Contd.)

A greedy algorithm works in stages, considering one input at a

time
At each stage, a decision is made regarding whether a
particular input is in an optimal solution
This is done by considering the inputs in some order
This order is determined by some selection procedure
If the inclusion of the next input into the partially constructed
optimal solution will result in an infeasible solution, then this
input is not added to the partial solution; otherwise, it is
added

4 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
Job Sequencing with Deadlines
Basics
Knapsack Problem
0/1 Knapsack Problem
Longest Common Subsequence Problem

Basics (Contd.)

5 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
Job Sequencing with Deadlines
Basics
Knapsack Problem
0/1 Knapsack Problem
Longest Common Subsequence Problem

Typical Problems Using Greedy Design

Fractional Knapsack
Minimum Spanning Tree
Job Sequencing with Deadlines

6 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
MST Concept
Job Sequencing with Deadlines
Prim’s Algorithm
Knapsack Problem
Kruskal’s Algorithm
0/1 Knapsack Problem
Longest Common Subsequence Problem

Minimum-Cost Spanning Tree

Given a connected, undirected graph G (V , E ), where V is the

set of vertices, E is the set of possible interconnections
between pairs of vertices, and for each edge (u, v ) ∈ E , we
have a weight w (u, v ) specifying the cost to connect u and v
We then wish to find an acyclic subset T ⊆ E that connects
all of the vertices and whose total weight is minimized
Since T is acyclic and connects all of the vertices, it must
form a tree, which we call a spanning tree since it “spans” the
graph G

7 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
MST Concept
Job Sequencing with Deadlines
Prim’s Algorithm
Knapsack Problem
Kruskal’s Algorithm
0/1 Knapsack Problem
Longest Common Subsequence Problem

MST (Contd.)

8 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
MST Concept
Job Sequencing with Deadlines
Prim’s Algorithm
Knapsack Problem
Kruskal’s Algorithm
0/1 Knapsack Problem
Longest Common Subsequence Problem

Prim’s Algorithm

For Prim’s algorithm, we can start creating the tree from any
arbitrary vertex and no edge
Then, go on adding the edges one by one following three rules
The rules are:
1 Adding an edge should not lead to a cycle
2 Always add the least cost edge which is adjacent to any of the
vertices already in the tree
3 We stop when exactly |V | − 1 edges have been added

9 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
MST Concept
Job Sequencing with Deadlines
Prim’s Algorithm
Knapsack Problem
Kruskal’s Algorithm
0/1 Knapsack Problem
Longest Common Subsequence Problem

Prim’s Algorithm (Contd.)

An example to illustrate Prim’s algorithm

10 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
MST Concept
Job Sequencing with Deadlines
Prim’s Algorithm
Knapsack Problem
Kruskal’s Algorithm
0/1 Knapsack Problem
Longest Common Subsequence Problem

Prim’s Algorithm (Contd.)

11 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
MST Concept
Job Sequencing with Deadlines
Prim’s Algorithm
Knapsack Problem
Kruskal’s Algorithm
0/1 Knapsack Problem
Longest Common Subsequence Problem

Kruskal’s Algorithm

For Kruskal’s algorithm, we can start creating the tree from

the edge having least cost
The rules are the same, except that we need not always
choose an adjacent edge
At any time, the edges added can form a collection of trees
(often termed as a forest) instead of a single tree
1 Adding an edge should not lead to a cycle
2 We stop when exactly |V | − 1 edges have been added

12 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
MST Concept
Job Sequencing with Deadlines
Prim’s Algorithm
Knapsack Problem
Kruskal’s Algorithm
0/1 Knapsack Problem
Longest Common Subsequence Problem

Kruskal’s Algorithm (Contd.)

An example to illustrate Kruskal’s algorithm

13 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
MST Concept
Job Sequencing with Deadlines
Prim’s Algorithm
Knapsack Problem
Kruskal’s Algorithm
0/1 Knapsack Problem
Longest Common Subsequence Problem

Kruskal’s Algorithm (Contd.)

14 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
Job Sequencing with Deadlines
Knapsack Problem
0/1 Knapsack Problem
Longest Common Subsequence Problem

Job Sequencing with Deadlines

Given a set of n jobs to be processed by a computer

Each job i is associated with a deadline time di and profit pi
A job is said to be complete if it has successfully executed 1
unit of time on a computer within the deadline
A completed job earns its profit pi
Our aim is to maximize the profit earned

15 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
Job Sequencing with Deadlines
Knapsack Problem
0/1 Knapsack Problem
Longest Common Subsequence Problem

A job sequencing problem

Given a set of 4 jobs {j1 , j2 , j3 , j4 }. Their profits are given as
{p1 , p2 , p3 , p4 } = {100, 10, 15, 27} and deadline times
{d1 , d2 , d3 , d4 } = {2, 1, 2, 1}. Find the optimal solution.
Let us first enumerate all the feasible solutions

Out of this, the best one is {1, 4}

16 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
Job Sequencing with Deadlines
Knapsack Problem
0/1 Knapsack Problem
Longest Common Subsequence Problem

High-level JS pseudocode

17 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
Job Sequencing with Deadlines
Knapsack Problem
0/1 Knapsack Problem
Longest Common Subsequence Problem

JS Algorithm
Greedy algorithm for sequencing unit time jobs with deadlines and
profits

18 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
Job Sequencing with Deadlines
Knapsack Problem
0/1 Knapsack Problem
Longest Common Subsequence Problem

Knapsack Problem
We are given n and a knapsack or bag
Object i has a weight wi and the knapsack has a capacity m
If a fraction xi , 0 ≤ xi ≤ 1, of object i is placed into the
knapsack, then a profit of pi xi is earned
The objective is to obtain a filling of the knapsack that
maximizes the total profit earned
Since the knapsack has a total capacity of only m, we require
the total weight of all chosen objects be at most m

19 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
Job Sequencing with Deadlines
Knapsack Problem
0/1 Knapsack Problem
Longest Common Subsequence Problem

A fractional knapsack problem

Consider the following instance of the knapsack problem:

n = 3, m = 20, (p1 , p2 , p3 ) = (25, 24, 15), (w1 , w2 , w3 ) =
(18, 15, 10). Four feasible solutions are:

Of these four feasible solutions, solution 4 yields the maximum

profit

20 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
Job Sequencing with Deadlines
Knapsack Problem
0/1 Knapsack Problem
Longest Common Subsequence Problem

Fractional knapsack algorithm

21 / 28
DYNAMIC PROGRAMMING
� An algorithm design method that can be used when the solution
to a problem can be viewed as a result of a sequence of
decisions.
� It solves the problem by combining the solutions to
subproblems.
� It is used when subproblems share subsubproblems.
� A dynamic programming algorithm solves each subsubproblem
just once and then saves its answer in a table.
� Bottom up approach
� An optimal sequence of decision can be found by making the
decisions one at a time and never making an erroneous
decision.
DYNAMIC PROGRAMMING
� In dynamic programming, we start with the smallest and
hence the simplest sub instance.
� Solve the subinstance and stored the result or Memoized.
� By combining their solutions, we obtain the answers to
sub instances of increasing size.
� Finally, we arrive at the solution of the original instances.
DYNAMIC PROGRAMMING V/S
DIVIDE AND CONQUER
� Dynamic Programming � Divide and Conquer
� Solves problems by � Solves problems by
combining the solutions to combining the solutions to
subproblems. subproblems.
� Subproblems share subsub � Sub problems are disjoint.
problems. � Solves the subproblems
� Solves each subsub problem recursively and then
just once and then saves the combine their solutions to
answer in a table. solve the original
� No recomputing needed subproblem.
since the answer is saved in � Recomputes the answer of
the table. subproblems every time it
� Bottom up technique solves it.
� Top down technique.
AN EXAMPLE Fib(5)
+

Fib(4) Fib(3)
+ +

Fib(3) Fib(2) Fib(2) Fib(1)

+ + +

Fib(2) Fib(1) Fib(1) Fib(0) Fib(1) Fib(0)

+

Fib(1) Fib(0)
DYNAMIC PROGRAMMING VS
GREEDY STRATEGY
� Dynamic Programming � Greedy Strategy
� Dynamic programming can be � A greedy algorithm is one that at
thought of as 'smart' recursion., a given point in time, makes a
� Often requires one to break down local optimization.
a problem into smaller � Greedy algorithms have a local
components that can be cached. choice of the subproblem that
� Solve all dependent subproblems will lead to an optimal answer.
and then select one that would � A greedy algorithm is one which
lead to an optimal solution. finds optimal solution at each and
� Is applicable to problems that every stage with the hope of
exhibit Overlapping subproblems finding global optimum at the
and Optimal substructure end.
properties. � Only one decision sequence is
� Many decision sequences may be ever generated.
generated. � More efficient as compared,to
� Less efficient as compared to dynamic programming
greedy approach
PRINCIPLE OF OPTIMALITY
� “The principle of optimality states that an optimal
sequence of decisions has the property that whatever
the initial state and decision are, the remaining
decisions must constitute an optimal decision sequence
with regard to the state resulting from the first
decision.”
OPTIMAL SUBSTRUCTURE
� A problem has optimal substructure if an optimal
solution can be constructed efficiently from optimal
solution of its subproblems.
OR
� We can solve larger problems given the solutions of its
smaller subproblems.
Optimal Path
A C

A B C

If AC is optimal, the AB and BC are optimal

DEVELOPMENT OF A DYNAMIC
PROGRAMMING
� Characterize the structure of an optimal solution.
� Recursively define the values of an optimal solution.
� Compute the value of an optimal solution in a Bottom-up
fashion.
� Construct the optimal solution from computed information
TRAVELLING SALESMAN
PROBLEM
� Let G = (V, E) be a directed graph with edge costs ci,j.
� ci,j > 0 for all i and j
� ci,j = ∞ if<i, j> Є E
� Let |V| = n and n >1.
� A tour of G is a directed simple cycle that includes every
vertex in V.
� The cost of a tour is the sum of the cost of the edges on
the tour.
� The travelling salesman problem is to find a tour of
minimum cost.
APPLICATIONS
� Route of a postal van to pick up mails from mailboxes
located at n different sites. The route taken by the postal
van is a tour and we are interested in finding a tour of
minimum length.
� A robot arm to tighten the nuts on some piece of
machinery on an assembly line. The path of the arm is
clearly a tour on a graph in which vertices represent the
nuts. A minimum cost tour will minimize the time needed
for the arm to complete its task.
TRAVELLING SALESMAN
PROBLEM
� A tour is a simple path that starts and ends at vertex 1.
� Every tour consists of an edge <1, k> for some k Є V – {1}
and a path from vertex k to 1.
� The path from k to 1 goes through each vertex in V – {1, k}
exactly once.
� It is easy to see that if the tour is optimal, then the path from
k to 1 must be a shortest k to 1 path going through all
vertices in V – {1, k}.
� Hence the principle of optimality holds.
TRAVELLING SALESMAN
PROBLEM
� Let g(i, S) be the length of a shortest path starting at
vertex i, going through all vertices in S and terminating at
vertex 1.
� The function g(1, V – {1}) is the length of the optimal
salesman tour.
� From the principle of optimality, it follows that

� Generalizing, we obtain (for i Є S)

PROBLEM
TRAVELLING SALESMAN
PROBLEM
� J(i,S) be the value of the vertex that minimizes the cost.
� The optimal tour in the problem is 1,2,4,3,1 with length
35.
� The computing time of this algorithm is O(n22n).
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
Job Sequencing with Deadlines
Knapsack Problem
0/1 Knapsack Problem
Longest Common Subsequence Problem

0/1 Knapsack Problem

The 0/1 knapsack problem is similar to the fractional

knapsack problem except that the xi ’s are now restricted to
have a value of either 0 or 1
We can compute values for f1 , f2 , .., fn by using equation
fi (y ) = max{fi−1 (y ), fi−1 (y − wi ) + pi }
f0 (y ) = 0 for all y and fi (y ) = −∞ for all y < 0

22 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
Job Sequencing with Deadlines
Knapsack Problem
0/1 Knapsack Problem
Longest Common Subsequence Problem

0/1 Knapsack Algorithm

When both the pj ’s and wj ’s are integers, the time complexity of

DKP (excluding the time for TraceBack (O(n2 )) is
O(min{2n , nm}) 23 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
Job Sequencing with Deadlines
Knapsack Problem
0/1 Knapsack Problem
Longest Common Subsequence Problem

Longest Common Subsequence Problem

Biological applications need to compare the DNA of two (or

more) different organisms
DNA - a string of molecules called bases - adenine, guanine,
cytosine, and thymine
P
A DNA strand expressed as a string over = {A, G , C , T }
An example, consider two DNAs S1 =
ACCGGTCGAGTGCGCGGAAGCCGGCCGAA, and S2 =
GTCGTTCGGAATGCCGTTGCTCTGTAAA

24 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
Job Sequencing with Deadlines
Knapsack Problem
0/1 Knapsack Problem
Longest Common Subsequence Problem

LCS Problem

Determining how “similar” the two strands helps to measure

how closely related the two organisms are.
One way to measure the similarity of strands S1 and S2 is by
finding a third strand S3 in which the bases in S3 appear in
each of S1 and S2
These bases must appear in the same order, but not
necessarily consecutively
The longer the strand S3 we can find, the more similar S1 and
S2 are.
In our example, the longest strand S3 is
GTCGTCGGAAGCCGGCCGAA

25 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
Job Sequencing with Deadlines
Knapsack Problem
0/1 Knapsack Problem
Longest Common Subsequence Problem

Subsequence

A subsequence of a given sequence is just the given sequence

with zero or more elements left out
Formally, given a sequence X = {x1 , x2 ..., xm }, another
sequence Z = {z1 , z2 ..., zk } is a subsequence of X if there
exists a strictly increasing sequence {i1 , i2 , i3 , ..., ik } of indices
of X such that for all j = 1, 2, 3..., k, we have xi j = zj
For example, Z = {B, C , D, B} is a subsequence of
X = {A, B, C , B, D, A, B} with corresponding index sequence
{2, 3, 5, 7}

26 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
Job Sequencing with Deadlines
Knapsack Problem
0/1 Knapsack Problem
Longest Common Subsequence Problem

Common Subsequence and the LCS Problem

Given two sequences X and Y , we say a sequence Z is a

common subsequence of X and Y if Z is a subsequence of
both X and Y
For example, if X = {A, B, C , B, D, A, B} and
Y = {B, C , B, D, A, B} then the sequence {B, C , A} is a
common subsequence of X and Y
In the longest common subsequence problem, we are given
two sequences X = {x1 , x2 ..., xm }, and another sequence
Y = {y1 , y2 ..., yn }, wish to find a maximum- length common
subsequence of X and Y

27 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
Job Sequencing with Deadlines
Knapsack Problem
0/1 Knapsack Problem
Longest Common Subsequence Problem

LCS Dynamic Programming

LCS problem has an optimal-substructure property

an LCS of two sequences contains within it an LCS of prefixes
of the two sequences
This means, we can solve LCS problem by dynamic
programming matrix method

28 / 28
 Greedy Algorithm Design
Minimum-Cost Spanning Tree
Job Sequencing with Deadlines
Knapsack Problem
0/1 Knapsack Problem
Longest Common Subsequence Problem

LCS dynamic programming algorithm

29 / 29
References

1 Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran,

Fundamentals of Computer Algorithms, 2nd edition, Universities
Press (India) Pvt. Ltd., 2008
2 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford
Stein, Introduction to Algorithms, 3rd edition, The MIT Press,
Cambridge, 2009