MODULE 3
Dynamic Programming
CONTENTS
• Dynamic Programming
The General method.
All pairs shortest path.
Traveling salesperson problem.
Reliability Design.
DYNAMIC PROGRAMMING
• Method of solving complex problems by breaking them down into smaller sub-problems, solving
each of those sub-problems just once, and storing their solutions.”
• The problem solving approach looks like Divide and conquer approach.(which is not true).
GENERAL METHOD
• Dynamic Programming algorithm is designed using the following four steps:
Characterize the structure of an optimal solution.
Recursively define the value of an optimal solution.
Compute the value of an optimal solution, typically in a bottom-up fashion.
Construct an optimal solution from the computed information.
• Dynamic programming can be implemented using two main approaches:
• Top-down approach (Memoization): Start with the original problem and recursively break it down into
subproblems, storing the results of each subproblem to avoid recomputation. Uses Top down approach and
uses recursive function.
• Bottom-up approach: Solve the smallest subproblems first and build up to the solution of the original
problem, storing the results of each subproblem as you go. Uses bottom up approach and uses iteration
function.
Dynamic Programming (DP) Greedy Approach
Solves problems by breaking into overlapping Makes the locally optimal choice at each step, hoping it
subproblems and solving each subproblem only once leads to a global optimum.
(memoization or tabulation).
Solves all subproblems and combines them to get the Solves the problem by making one decision at a time.
optimal solution.
solves the same subproblems multiple times but stores No overlapping subproblems; solves each subproblem
results to avoid recomputation. once.
Always gives an optimal solution (if applicable). Only gives optimal solution for problems that satisfy the
"Greedy Choice Property."
Principle of optimality:
The optimal solution to a dynamic optimization problem can be found by combining
the optimal solutions to its sub-problems.
ALL PAIR SHORTEST PATH
• The All-Pairs Shortest Path (APSP) problem is about finding the shortest paths between
every pair of vertices in a given weighted graph.
Floyd’s Algorithm Warshall’s Algorithm
Computes shortest path distances between all pairs of Computes transitive closure (reachability) between all
vertices. pairs of vertices.
Solves the All-Pairs Shortest Path problem (with Solves reachability (boolean matrix) or connectivity
weights). (without weights).
Weighted graphs (positive or negative edge weights, no Unweighted graphs (only checks if a path exists between
negative cycles). two nodes).
Iteratively updates the shortest distance matrix by Iteratively updates reachability matrix by checking
considering each vertex as an intermediate. intermediate connections.
Finding shortest paths in weighted graphs like road Finding connectivity or path existence in social
networks. networks, web graphs.
Can handle negative edge weights but not negative Not applicable (deals with unweighted edges).
cycles.
WARSHALL’S ALGORITHM
WARSHALL’S ALGORITHM
WARSHALL’S ALGORITHM
FLYOD’S ALGORITHM
FLYOD’S ALGORITHM
FLYOD’S ALGORITHM
• Time Complexity for Flyod and warshall is O(n3).
TRAVELLING SALESMAN
PROBLEM
• The Travelling Salesman Problem (TSP) is an optimization problem where the goal is to find
the shortest possible route that visits each city exactly once and returns to the starting city.
• Using dynamic programming, the problem can be approached by breaking it down into
smaller subproblems. The dynamic programming solution involves using a recursive
function to calculate the minimum cost of visiting all cities
USING MEMORIZATION BY USING
FORMULA
1 2 3 4
1 0 10 15 20
2 5 0 9 10
3 6 13 0 12
4 8 8 9 0
RELIABILITY DESIGN
• The problem is to design a system which is composed of several devices connected
in series.
• Let ri be the reliability of device Di; (i.e. ri is the probability that device i will
function properly).
• Then, the reliability of the entire system is Пri
• Even if the individual devices are very reliable (i.e. ri is very close to 1) the
relaiblility of the system may not be very good. E.g. if n =10, ri = 0.99 for i = 1 to
10, then Пri = 0.904
RELIABILITY DESIGN
• It is desirable to duplicate devices.
• Multiple copies of the same device type are connected in parallel through the use of
switching circuits. The switching circuits determine which devices in any given
group are functioning properly. They then make use of one such device at each stage.
• Link to problem:
[Link]
/