Design and Analysis of

Algorithms

Instructor: Solomon (Ph.D)

 Chapter 4:
Dynamic Programming (DP)
 Dynamic Programming (DP)
• As the name implies, “dynamic” refers to making
decisions at various stages, while “programming”
involves determining or planning the most efficient
sequence of actions.

• DP is an algorithmic technique used for solving complex

problems by breaking them down into simpler
subproblems, solving each only once, and storing their
results to avoid redundant computation.

• Unlike Divide and Conquer, where subproblems are

independent, DP is used when subproblems overlap (i.e.,
they share smaller subproblems).
 Dynamic Programming (DP) …
• It is used for solving optimization problems. The
steps used are:
– Decompose the Problem: Break down the complex problem into
simpler subproblems.
– Solve Subproblems Optimally: Find the optimal solution for each
subproblem.
– Store Intermediate Results: Save the results of subproblems,
typically using a table or memoization.
– Avoid Recomputations: Reuse stored results to prevent solving the
same subproblem multiple times.
– Build Final Solution: Use the stored solutions to compute the optimal
result for the original complex problem.
 When to use DP?
• It is most effective when a problem exhibits two key
properties:
1) Optimal Substructure:
− A problem has optimal substructure if an optimal solution to the
entire problem can be constructed from optimal solutions to its
subproblems.
− Solve subproblems optimally and combine their solutions to build
the solution to the full problem.
− Example: Minimum Cost Path in a Graph
▪ Break the problem of finding the shortest path from source to
destination into:
✓ Finding shortest paths to intermediate nodes.
✓ Using those to compute the total shortest path to the
destination.
▪ The final path cost is derived from smaller optimal solutions.
 When to use DP? …
2) Overlapping Subproblems:
− A problem has overlapping subproblems if the same
subproblems are solved multiple times during the recursive
solution process.
− Store (memoize) the results of subproblems to avoid
redundant computation.
− Example: Fibonacci Sequence Computation
▪ To compute Fib(n), you calculate Fib(n-1) and Fib(n-2).
▪ But Fib(n-2) will also be recalculated when computing Fib(n-
1), leading to repeated work.
▪ Using DP, we store already computed Fibonacci numbers to
avoid repeated calls.
 Approaches of DP
• It can be implemented in two ways:
1) Top-Down Approach (Memoization)
− A recursive method where we solve the problem starting
from the main problem and break it down into subproblems.
− How it Works:
▪ Before making a recursive call, check if the result already exists
in the memoization table.
▪ If yes, reuse it.
▪ If not, compute the result and store it in the table for future
reference.
− Characteristics:
▪ Uses recursion with caching.
▪ Reduces redundant subproblem computations.
▪ May incur recursion stack overhead.
− Example:
▪ Recursive Fibonacci with memoization.
 Approaches of DP …
2) Bottom-Up Approach (Tabulation)
− An iterative method where we solve all subproblems first,
starting from the base case, and build up to the full solution.
− How it Works:
▪ Initialize a DP table with base cases.
▪ Use a loop to fill in the table using the recursive formula,
without making recursive calls.
− Characteristics:
▪ Avoids recursion, hence no stack overflow.
▪ Often more space-efficient and faster in practice.
▪ Suits problems with a clear progression from smaller to larger
subproblems.
− Example:
▪ Iterative Fibonacci using an array or just two variables.
 Approaches of DP …
• Choosing between Memoization and Tabulation:
Feature Top-Down (Memoization) Bottom-Up (Tabulation)

Method Recursive Iterative

Storage Memo (usually a map or array) DP Table (array/matrix)

Time Efficiency Good Better in some cases

Space Efficiency May use extra stack Avoids recursion stack

 Example of DP: Fibonacci Sequence
• Example: Consider the problem of finding the Fibonacci
sequence
– The Fibonacci sequence is defined as:
F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) for n  2
– Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
1) Brute Force Approach (Naive Recursion)
int fib(int n) {
if(n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}

▪ Time Complexity: Exponential

O(2n)
▪ Problem: Recomputes the same subproblems repeatedly (e.g.,
fib(n-2) is computed many times).
Example of DP: Fibonacci Sequence …
• Optimized with Dynamic Programming
2) Top-Down Approach (Memoization)
int fibMemo(int n, Map<Integer, Integer> memo) {
if([Link](n)) {
return [Link](n);
}
if(n <= 1) {
return n;
}
int res = fibMemo(n-1, memo) + fibMemo(n-2, memo);
[Link](n, res);
return res;
}

▪ Time Complexity: O(n)

Example of DP: Fibonacci Sequence …
3) Bottom-Up Approach (Tabulation)
int fibTab(int n) {
if (n <= 1) {
return n;
}
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;

for (int i = 2; i <= n; i++) {

dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}

▪ Time Complexity: O(n)

 Advantages & Disadvantages of DP
Advantages Disadvantages
Avoids redundant computations High memory usage due to storage of all
by storing intermediate results subproblem results.
(memoization/tabulation).
Improves time complexity over Not all problems are suitable - DP only
naive recursive methods. works with problems that have overlapping
subproblems and optimal substructure.
Ensures optimal solution by Complex to design - crafting DP recurrence
solving all subproblems exactly relations and table initialization can be tricky.
once.
Supports bottom-up (iterative) or Hard to debug due to lack of clear trace
top-down (recursive + memo) (especially in iterative tabulation).
approaches.
Widely used in real-world May still lead to exponential space/time in
applications like routing, resource worst-case scenarios (e.g., multiple
allocation, and scheduling. dimensions).
 Applications of DP
• Problems solvable using DP are:
✓ Fibonacci Number Series
✓ 0/1 Knapsack Problem
✓ All Pairs Shortest Paths Problem
✓ Single Source Shortest Paths Problem
✓ Optimal Binary Search Tree
✓ Travelling Salesman Problem
0/1 Knapsack Problem
 0/1 Knapsack Problem
• Given n items where each item has some weight and profit
associated with it and also given a bag with 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.
• Note: The constraint here is we can either put an item
completely into the bag or cannot put it at all [It is not
possible to put a part of an item into the bag].
• Example: Let us consider that the capacity of the knapsack is
W = 8 and the items are as shown in the following table.
Item 1 2 3 4
Profit (Pi) 2 3 1 4
Weight (Wi) 3 4 6 5
▪ Goal: Select items such that the total profit is maximized and the total weight ≤ W.
 0/1 Knapsack Problem …
i 0 1 2 3 4 5 6 7 8
Pi Wi 0 0 0 0 0 0 0 0 0 0
2 3 1 0 0 0 2 2 2 2 2 2
3 4x 2 0 0 0 2 3 3 3 5 5
4 5 3 0 0 0 2 3 4 4 5 6
1 6x 4 0 0 0 2 3 4 4 5 6

Note: Consider the given weights = {3, 4, 6, 5}. Max. Profit

xi = {_, _, 0, _}; 6 is not selected (0 will be the 3rd item).

xi = {_, _, 0, 1}; 5 is selected (1 will be the 4th item) and profit = 4, the
remaining profit = 6-4 = 2.
xi = {1, _, 0, 1}; 3 is selected (1 will be the 1st item) and profit = 2, then the
remaining profit = 2-2= 0.
xi = {1, 0, 0, 1}; Since the remaining profit is 0, then the rest items will be
0s.
All Pairs Shortest Path Problem
 All Pairs Shortest Path Problem
(Floyd-Warshall Algorithm)
• Given a matrix dist[][] of size n x n, where dist[i][j]
represents the weight of the edge from node i to node j. If
there is no direct edge, dist[i][j] is set to represent infinity.
The diagonal entries dist[i][i] are 0, since the distance from a
node to itself is zero. The graph may contain negative edge
weights, but it does not contain any negative weight cycles.
• Your task is to determine the shortest path distance between
all pair of nodes i and j in the graph.
• Example: Let’s walk through an example using a simple
graph with 3 nodes (1, 2, 3) and the following weighted
edges:
 All Pairs Shortest Path Problem
(Floyd-Warshall Algorithm) …
• The graph can be represented as an adjacency matrix:

• Ak[i,j] = min{Ak-1[i,j], Ak-1[i,k]+Ak-1[k,j]}

• Interpretation:
– Shortest path from 1 to 2: 4
– Shortest path from 1 to 3: 6
– Shortest path from 2 to 1: 5
– Shortest path from 2 to 3: 2
– Shortest path from 3 to 1: 3
– Shortest path from 3 to 2: 7
Single Source Shortest Paths
Problem (SSSP)
 Single Source Shortest Paths Problem
(SSSP) - Bellman-Ford Algorithm
• It involves finding the shortest paths from a source vertex
to all other vertices in a weighted graph.
• The graph may be directed or undirected and may
contain positive or negative edge weights (but no
negative cycles).
• DP can be effectively used in solving the SSSP problem,
especially in cases like Bellman-Ford algorithm, which is
a classic DP-based method.
– The Bellman-Ford algorithm solves the SSSP problem using a
dynamic programming approach.
– It works on graphs with negative weights, unlike Dijkstra’s
algorithm which only works correctly with non-negative edge
weights.
 Single Source Shortest Paths Problem
(SSSP) - Bellman-Ford Algorithm …
• Algorithm Steps:
– Given:
▪ Graph G = (V, E).
▪ Source vertex src.
− Step 1: Initialize Distances
▪ Set dist[src] = 0
▪ Set dist[v] = ∞ for all v ∈ V, v ≠ src
− Step 2: Relax All Edges (|V|-1) Times (where |V| = number of
vertices)
▪ For each edge in the graph, update the distance to v if a shorter path
through u is found.
If dist[u]+w < dist[v], then update: dist[v] = dist[u]+w
− Step 3: Check for Negative Weight Cycles
▪ Do one more pass over all edges. If we can still relax any edge, then
there is a negative weight cycle.
− Step 4: Return the Final Distance Array
▪ dist[v] now holds the shortest distance from src to each vertex v ∈ V.
 Single Source Shortest Paths Problem
(SSSP) - Bellman-Ford Algorithm …
• Example - Let us consider a directed graph with 7 vertices
(V = {A, B, C, D, E, F, G}) and the following weighted
edges:
 Single Source Shortest Paths Problem
(SSSP) - Bellman-Ford Algorithm …
• Step 1: Initialization
– Start with the source vertex A.
– Set the distance to A as 0 and all other vertices to infinity.
• Step 2: Relax all edges |V|-1 times (in this case, 7-1 = 6
times)
▪ E(G) = { <A,B>, <A,C>, <A,D>, <B,E>, <C,B>, <C,E>, <D,C>,
<D,F>, <E,G>, <F,G>}
– Iteration 1:
▪ dist[B] = 3, dist[C] = 3, dist[D] = 5, dist[E] = 5, dist[F] = 4, dist[G] = 7.
− Iteration 2:
▪ dist[B] = 1, dist[C] = 3, dist[D] = 5, dist[E] = 2, dist[F] = 4, dist[G] = 5.
− Iteration 3:
▪ dist[B] = 1, dist[C] = 3, dist[D] = 5, dist[E] = 0, dist[F] = 4, dist[G] = 3.
 Single Source Shortest Paths Problem
(SSSP) - Bellman-Ford Algorithm …
− Iteration 4 to 6:
▪ Repeat relaxation, but no further updates occur. The distance array
remains the same:
✓ dist[B] = 1, dist[C] = 3, dist[D] = 5, dist[E] = 0, dist[F] = 4, dist[G] = 3.

• Step 3: Check for negative-weight cycles

− Run one more pass: no further relaxation is possible → No negative
weight cycle.
• Step 4: Return final shortest distances from A:
dist[B] = 1,
dist[C] = 3,
dist[D] = 5,
dist[E] = 0,
dist[F] = 4, • Time Complexity:
dist[G] = 3. ✓ O(E × |V|-1) = O(E × |V|)
 Exercise
• Consider a directed graph consisting of 4 vertices (V =
{A, B, C, D}) along with the corresponding weighted
edges listed below:
 Introduction to Graphs
• A graph is a non-linear data structure consisting of a set
of nodes (vertices) and edges that connect pairs of nodes.
– A non-linear data structure is a type of data structure where data
elements are not arranged in a sequential or linear order.
– Instead, the elements form a hierarchical or networked
relationship. This allows for more complex relationships among
data items.
• It is widely used to represent real-world problems
involving networks, such as computer networks, social
networks, transportation systems, and web page linking.
• Definition:
▪ A Graph G = (V, E) where:
− V is a finite set of vertices.
− E is a finite set of edges (pairs of vertices, which may be ordered or
unordered).
 Introduction to Graphs …
• The following figure shows three graphs: G1, G2 and G3.
The graphs G1 and G2 are undirected; G3 is a directed
graph. Sometimes an edge has a third component, known as
either a weight or a cost. This one is called weighted graph.

• The set representations of these graphs are:

– V(G1) = {1,2,3,4,5}
– V(G2) = {1,2,3,4,5,6}
– V(G3) = {1,2,3,4}
– E(G1) = {(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)}
– E(G2) = {(1,2),(1,3),(2,4),(2,5),(3,6)}
– E(G3) = {<1,2>,<1,3>,<1,4>,<4,1>,<2,4>,<4,2>,<3,4>}
 Introduction to Graphs …
• We observe that the edges of the directed graph (G3) are
drawn with an arrow from the tail to the head. The graph
G2 is a tree; the graphs G1 and G3 are not.
• Graph Terminologies:
– Vertex (Node): A fundamental unit in a graph representing an entity.
E.g. In a social network, a person is a vertex.
– Edge (Arc): A connection between two vertices. E.g. A friendship
between two people.
– Adjacent Vertices: Two vertices connected directly by an edge. E.g.
In A — B, A and B are adjacent.
– Degree: Number of edges connected to that vertex. E.g. A vertex with
3 connections has a degree of 3.
– Path: A sequence of vertices connected by edges. E.g. A → B → C is
a path from A to C.
– Cycle: A path that starts and ends at the same vertex without repeating
an edge. E.g. A → B → C → A is a cycle.
 Types of Graphs
Type Description
Directed Graph
(Digraph) Edges have direction (from one node to another).

Undirected Graph Edges have no direction.

Weighted Graph Each edge carries a weight or cost.
Unweighted Graph Edges have no weight.
Cyclic Graph Contains at least one cycle.
Contains no cycles (e.g., trees, Directed Acyclic
Acyclic Graph
Graphs (DAGs)).
A path exists between every pair of vertices (for
Connected Graph
undirected graphs).
Disconnected Graph Not all nodes are connected.
 Common Operations on Graphs
• Add/Delete Vertex
• Add/Delete Edge
• Graph Traversals:
– Breadth-First Search (BFS)
– Depth-First Search (DFS)
• Check if path exists between nodes
• Detect cycles
 Applications of Graphs
• Social networks (friendship/follower relationships)
• Routing algorithms (e.g., Google Maps)
• Network flows (Internet traffic, Logistics)
• Job scheduling (DAGs)
• Web page ranking (PageRank Algorithm)
 Graph Traversals
• A primary problem concerning the graphs is the
reachability. A number of graph problems involves
traversal of a graph.
• Traversal of a graph means visiting each of its nodes
exactly once. This is accomplished by visiting the
nodes in a systematic manner.
• Two commonly used techniques of graph traversal
are:
– Breadth First Search (BFS)
– Depth First Search (DFS)
 Breadth First Search (BFS)
• It is a graph traversal algorithm that explores all neighbors
at the present depth before moving on to the next depth
level.
• It uses a FIFO (First-In-First-Out) approach, typically
implemented using a queue.
• How BFS Works:
– Start from the source node.
– Visit and enqueue all unvisited neighbors.
– Dequeue the next node and repeat the process.
– Continue until all reachable nodes are visited.
 Breadth First Search (BFS) …
• Example: BFS on an Undirected Graph

• Queue: A B D C F G E
• Result: A B D C F G E

• Time Complexity: O(E+|V|)

 Depth First Search (DFS)
• It is an algorithm used to explore all the vertices and edges
in a graph by starting at a chosen node and going as deep
as possible into the graph before coming back
(backtracking) to explore other branches.
• It uses the LIFO (Last-In-First-Out) principle, typically
implemented via recursion or a stack.
• How DFS Works:
– DFS explores:
▪ Start at the source node.
▪ Mark it as visited.
▪ Go to one of its unvisited neighbors.
▪ Repeat the process for that neighbor.
▪ When you reach a node with no unvisited neighbors, backtrack to
the previous node.
▪ Continue until all reachable nodes are visited.
 Depth First Search (DFS) …
• Example: DFS on an Undirected Graph

• Stack:

• Result: A B D C E G F
• Time Complexity: O(E+|V|)
Thank You!