Click to edit Master title style
Chapter - 4
Dynamic programming
H a b t a m u W. ( M S c )
M a r c h , 2 012 5
Click to edit Master title style
Chapter 4 – Dynamic programming
• Introduction to Dynamic Programming
• Floyd-Warshall Algorithm - All pairs Shortest Path
• Shortest Path - Dijkstra Algorithm
• 0/1 Knapsack problem
• Depth First Search algorith
2
Click to edit Introduction to Dynamic Programming
Master title style
− Dynamic Programming (DP) is a method for solving complex problems by breaking
them down into simpler overlapping subproblems.
− It is used when a problem has overlapping subproblems and optimal substructure.
− Optimal Substructure: A problem exhibits optimal substructure: if an optimal
solution to the problem contains optimal solutions to its subproblems.
− Overlapping Subproblems: The same subproblems are solved multiple times.
− It is used in cases where the same subproblems occur multiple times, and the
results of subproblems are stored to avoid redundant work.
− It is mainly an optimization over plain recursion.
3
Dynamic
Click to edit Programming
Master title style vs. Divide and Conquer
Feature Dynamic Programming Divide and Conquer
Subproblem Solves subproblems once and stores Solves subproblems recursively
Solving results without storing
Example Merge Sort, Quick Sort, Binary
Fibonacci, Knapsack, Shortest Path
Algorithms Search
Bottom-up or Top-down
Approach Top-down (Recursion)
(Memoization)
4
Tabulation
Click to edit vs Memoization
Master title style
− Tabulation and Memoization are two techniques used to implement dynamic
programming.
− Both techniques are used when there are overlapping subproblems (same
subproblem is executed multiple times):
1. Top-down (Memoization): Solve the problem recursively, but store the results of
subproblems to avoid recomputing them.
Memoization is a programming technique that speeds up programs by caching the
results of expensive function calls.
2. Bottom-up (Tabulation): faster, Build a solution iteratively from the smallest
subproblems and store their solutions in a table. 5
Introduction
Click to Dynamic
to edit Master Programming: example
title style
Example
− Fibonacci Sequence: is a sequence where the next term is the sum of the previous
two terms. i.e f(n) = f(n-1) + f(n-2)
− The first two terms of the Fibonacci sequence are 0 followed by 1. The Fibonacci
sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21
− Using dynamic programming, we store the results of previously calculated
Fibonacci numbers to avoid recalculating them.
6
Introduction
Click to Dynamic
to edit Master Programming: example
title style
We can use recursion to solve this problem because any Fibonacci number n depends
on previous two Fibonacci numbers. Therefore, this approach repeatedly breaks
down the problem until it reaches the base cases.
7
Introduction
Click to Dynamic
to edit Master Programming: example
title style
− Solves the Fibonacci problem by storing previously calculated Fibonacci numbers,
avoiding the repeated calculations of the recursive approach. Instead of breaking
down the problem recursively, it iteratively builds up the solution by calculating
Fibonacci numbers from the bottom-up.
8
Floyd-Warshall
Click Algorithm
to edit Master - All Pairs Shortest Path
title style
The Floyd-Warshall is a dynamic programming algorithm used to find the shortest
paths between all pairs of nodes in a graph.
− unlike Dijkstra and Bellman-Ford which are single source shortest path algorithms.
− It works for both positive and negative weights but assumes no negative weight
cycles (where you can loop forever, reducing the total distance).
How it works:
− The algorithm consider every possible pair of nodes and tries to improve the
shortest path between them by using an intermediate node.
− It repeatedly updates the shortest distance between each pair if going through an
intermediate node offers a shorter path. 9
Floyd-Warshall
Click Algorithm
to edit Master - All Pairs Shortest Path
title style
Note: It does not work for the graphs with negative cycles (where the sum of the
edges in a cycle is negative).
Idea Behind Floyd Warshall Algorithm:
Suppose we have a graph graph[][] with V vertices from 0 to V-1. Now we have to
evaluate a dist[][] where dist[i][j] represents the shortest path between vertex i to j.
Let us assume that vertices i to j have intermediate nodes. The idea behind Floyd
Warshall algorithm is to treat each and every vertex k from 0 to V-1 as an
intermediate node one by one. When we consider the vertex k, we must have
considered vertices from 0 to k-1 already. So we use the shortest paths built by
previous vertices to build shorter paths with vertex k included. 10
Floyd-Warshall
Click Algorithm
to edit Master - All Pairs Shortest Path
title style
11
Floyd-Warshall
Click Algorithm
to edit Master - All Pairs Shortest Path
title style
− The algorithm relies on the principle of optimal substructure, meaning:
− If the shortest path from i to j passes through some vertex k, then the path from i
to k and the path from k to j must also be shortest paths.
− The iterative approach ensures that by the time vertex k is considered, all shortest
paths using only vertices 0 to k-1 have already been computed.
− By the end of the algorithm, all shortest paths are computed optimally because
each possible intermediate vertex has been considered.
12
Floyd-Warshall
Click Algorithm:
to edit Master Dense Vs Sparse Graphs
title style
− Dense Graph: A graph in which the number of edges are significantly much higher
than the number of vertices.
− Sparse Graph: A graph in which the number of edges are very much low.
− No matter how many edges are there in the graph the Floyd Warshall Algorithm
runs for O(V3) times; therefore it is best suited for Dense graphs.
− In the case of sparse graphs, Johnson’s Algorithm is more suitable.
13
Realto
Click World
edit Applications of Floyd-Warshall Algorithm
Master title style
− In computer networking, the algorithm can be used to find the shortest path
between all pairs of nodes in a network. This is termed as network routing.
− Flight Connectivity In the aviation industry to find the shortest path between the
airports.
− GIS(Geographic Information Systems) applications often involve analyzing spatial
data, such as road networks, to find the shortest paths between locations.
14
Floyd-Warshall
Click Algorithm
to edit Master - All Pairs Shortest Path: Example
title style
15
Floyd-Warshall
Click Algorithm
to edit Master - All Pairs Shortest Path
title style
16
Floyd-Warshall
Click Algorithm
to edit Master - All Pairs Shortest Path
title style
17
Floyd-Warshall
Click Algorithm
to edit Master - All Pairs Shortest Path
title style
18
Floyd-Warshall
Click Algorithm
to edit Master - All Pairs Shortest Path
title style
19
Floyd-Warshall
Click Algorithm
to edit Master - All Pairs Shortest Path
title style
20
Floyd-Warshall
Click Algorithm
to edit Master - All Pairs Shortest Path
title style
21
Floyd-Warshall
Click Algorithm
to edit Master - All Pairs Shortest Path
title style
22
Shortest
Click Path
to edit - Dijkstra
Master Algorithm
title style
− Refer chapter 3 for brief understanding.
23
0/1 Knapsack
Click Problem
to edit Master title style
− Given N items where each item has some weight and profit associated with it and
also given a bag/Knapsack with maximum capacity W, [i.e., the bag can hold at
most W weight in it].
− The task is to put the items into the bag such that the sum of profits associated
with them is the maximum possible.
− The "0/1" means you either include an item in the knapsack or exclude it (no
partial items allowed).
24
0/1 Knapsack
Click Problem
to edit Master title–style
Example
Input: N = 3, W = 4, profit[] = {1, 2, 3}, weight[] = {4, 5, 1}
Output: 3
Explanation: There are two items which have weight less than or equal to 4.
If we select the item with weight 4, the possible profit is 1. And if we select the item
with weight 1, the possible profit is 3. So, the maximum possible profit is 3.
Note that we cannot put both the items with weight 4 and 1 together as the capacity
of the bag is 4.
Exercise Input: N = 3, W = 3, profit[] = {1, 2, 3}, weight[] = {4, 5, 6}
Output: ?
25
0/1 Knapsack
Click Problem
to edit Master title–style
Example
You are given a set of items, each with a weight and a value. You have a knapsack
that can hold up to W = 7 units of weight. Determine the maximum total value you
can carry in the knapsack?
Item Weight (w) Value (v)
1 1 1
2 3 4
3 4 5
4 5 7
26
0/1 Knapsack
Click Problem
to edit Master title–style
Example
Step 1: Create the DP Table
We will create a table with dimension of (number of items +1) × (knapsack capacity
+1), where:
− Rows (i) represent the number of items considered (including 0 items).
− Columns (w) represent the knapsack's current weight capacity (0 to W).
Items ↓ / Weight → 0 1 2 3 4 5 6 7
0 Items 0 0 0 0 0 0 0 0
Item 1 (w=1, v=1) - - - - - - - -
Item 2 (w=3, v=4) - - - - - - - -
Item 3 (w=4, v=5) - - - - - - - -
Item 4 (w=5, v=7) - - - - - - - - 27
0/1 Knapsack
Click Problem
to edit Master title–style
Example
Step 2: Fill the Table Row by Row
− We fill each cell dp[i][w] based on whether we include the current item or not.
Item 1: (w=1, v=1)
− For each capacity w, we check if we can include this item.
Items ↓ / Weight → 0 1 2 3 4 5 6 7
0 Items 0 0 0 0 0 0 0 0
Item 1 (w=1, v=1) 0 1 1 1 1 1 1 1
− For w = 1, we can include item 1 → dp[1][1] = max(0, 1) = 1
− For w = 2 to 7, since we can still include item 1, the value remains 1.
28
0/1 Knapsack
Click Problem
to edit Master title–style
Example
Step 2: Fill the Table Row by Row
Item 2: (w=3, v=4)
Items ↓ / Weight → 0 1 2 3 4 5 6 7
0 Items 0 0 0 0 0 0 0 0
Item 1 (w=1, v=1) 0 1 1 1 1 1 1 1
Item 2 (w=3, v=4) 0 1 1 4 5 5 5 5
− For w < 3, can’t include item 2, so so dp[2][1] = dp[1][1] = 1.
− For w = 3, include item 2 → dp[2][3] = max(dp[1][3], 4) = 4.
− For w = 4, we take the max value: So, dp[2][4] = 5
− Similarly, dp[2][5] to dp[2][7] = 5 since adding item 2 is better.
29
0/1 Knapsack
Click Problem
to edit Master title–style
Example
Step 2: Fill the Table Row by Row
Item 3: (w=4, v=5) Items ↓ / Weight → 0 1 2 3 4 5 6 7
0 Items 0 0 0 0 0 0 0 0
Item 1 (w=1, v=1) 0 1 1 1 1 1 1 1
Item 2 (w=3, v=4) 0 1 1 4 5 5 5 5
Item 3 (w=4, v=5) 0 1 1 4 5 6 6 9
− For w < 4, can’t include item 3, cannot be included, so dp[3][w] = dp[2][w].
− For w = 4, include item 3 → dp[3][4] = max(dp[2][3], 5) = 5.
− For w = 5, include item 3 → dp[3][5] = value[3] + dp[2][1] = 5 + 1 = 6.
− For W = 6, include item 3 → dp[3][6] = value[3] + dp[2][2] = 5 + 1 = 6.
− For W = 7, include item 3 → dp[3][7] = value[3] + dp[2][3] = 5 + 1 = 9. 30
0/1 Knapsack
Click Problem
to edit Master title–style
Example
Step 2: Fill the Table Row by Row Items ↓ / Weight → 0 1 2 3 4 5 6 7
0 Items 0 0 0 0 0 0 0 0
Item 4: (w=5, v=7)
Item 1 (w=1, v=1) 0 1 1 1 1 1 1 1
Item 2 (w=3, v=4) 0 1 1 4 5 5 5 5
Item 3 (w=3, v=4) 0 1 1 4 5 6 6 9
Item 4 (w=5, v=7) 0 1 1 4 5 7 8 9
− For w < 5, can’t include item 4, cannot be included, so dp[4][w] = dp[3][w].
− For w = 5, include item 4 → dp[4][5] = max(dp[3][5], 7 + dp[3][5-5]) = max(6, 7) =
7.
− For w = 6, include item 4 → dp[4][6] = value[4] + dp[3][1] = 7 + 1 = 8.
− For W = 7, include item 4 → dp[4][7] = value[4] + dp[3][2] = 7 + 1 = 6, but 9 > 8;
i.e we don’t update, and keep dp[4][7] = 9.
31
Depth
Click to First Search title
edit Master (DFS)style
− It is a recursive algorithm for traversing or searching through graph and tree data
structures.
− There fore, we traverse all adjacent vertices one by one.
− It explores as far as possible along one branch before backtracking.
− DFS is used for various purposes like pathfinding, avoiding cycles, and solving
puzzles (like mazes).
− A standard DFS implementation puts each vertex of the graph into visited and Not
visited categories.
− How?
32
Depth
Click to First Search title
edit Master (DFS)style
1. Start at the root or a starting node.
2. Explore each branch or edge as far as possible before moving to the next
unexplored node (backtrack if necessary).
3. Mark nodes as visited to avoid cycles.
33
Depth
Click to First Search title
edit Master (DFS)style
- Example
34