hat is Dynamic Programming?
W
● Dynamic Programmingis a method for solving problemsbybreaking them into
overlapping subproblems, solving each subproblem justonce, and storing its result to avoid
recomputation.
Key Concepts of DP:
1. Optimal Substructure:
○ A problem hasoptimal substructureif its optimalsolution can be built from optimal
solutions of its subproblems.
2. Overlapping Subproblems:
○ A problem exhibitsoverlapping subproblemsif thesame subproblem is solved multiple
times.
General method:-
Problem
|
V
Break into Subproblems (Overlapping)
|
V
Solve Subproblem and Store in Table
|
V
Combine Subproblem Solutions
|
V
Optimal Solution
hat are Multistage Graphs?
W
● Amultistage graphis a type of graph where the vertices(nodes) are organized into
multiple layers.
● In a multistage graph, each node connects only to the nodes in the next layer, representing a
sequential process or a pipeline.
● The goal is to find the optimal path through these nodes with the minimum cost.
● Often used inproject scheduling, logistics, transportationplanning, andprocess
optimization.
dvantages of Using Multistage Graphs
A
1. Efficiency
● Reduces the complexity of sequential processes withdynamic programmingtechniques.
2. Scalability
● Easily scalable to more complex networks and processes.
3. Optimal Resource Allocation
● Helps in minimizing costs and optimizing resources across layers.
What is the Floyd-Warshall Algorithm?
TheFloyd-Warshall algorithmis a fundamental algorithmin graph theory that finds theshortest
paths between every pair of verticesin aweightedgraph(both directed and undirected).
It is particularly well-suited fordense graphs(graphswith a large number of edges). It handles
bothpositive and negative edge weights, making itvery versatile.
. Initialize the Distance Matrix
1
Create a 2-dimensional matrix distof size V×VV \timesVV×V representing the shortest distance
between each pair of vertices.
For a graph with VVV vertices:
● Set dist[i][j]dist[i][j]dist[i][j] to the weight of the edge between iii and jjj.
● If there is no edge between iii and jjj, set dist[i][j]=∞dist[i][j] = \inftydist[i][j]=∞.
● For every vertex iii, set the diagonal element dist[i][i]=0dist[i][i] = 0dist[i][i]=0.
Initial Distance Matrix Example:
For a graph with 4 vertices A,B,C,DA, B, C, DA,B,C,D:
A B C D
. Iteratively Update the Distance Matrix
2
● The core of the Floyd-Warshall algorithm updates the shortest paths by considering each
vertex kkk as anintermediate node.
● For every pair of vertices (i,j)(i, j)(i,j):
Update Rule:
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])dist[i][j] = \min(dist[i][j], dist[i][k] +
dist[k][j])dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
● For each possible intermediate node kkk:
○ For every pair of nodes (i,j)(i, j)(i,j), check if the path through kkk is shorter than the direct
path from iii to jjj.
3. Repeat Until All Nodes Are Considered
● Continue considering each node kkk as an intermediate node in turn (i.e., for all nodes k=1k
= 1k=1 to VVV).
● For every node kkk, update the matrix for all pairs (i,j)(i, j)(i,j).
✅ Advantage❌ Disadvantage
to implement with a clear matrix approacomplexity O(V3)O(V^3)O(V3) for large g
esboth directed and undirected graphsry-intensive with O(V2)O(V^2)O(V2) sto
vely computes all-pairs shortest paths even withnegicient for very large sparse gr
weights
hat are Optimal Binary Search Trees?
W
AnOptimal Binary Search Treeminimizes thesearch,insert, and delete costsin a binary
search tree (BST) by ensuring that the tree is structured in such a way that these operations are as
fast and efficient as possible.
● In a normal binary search tree, the tree may becomeunbalanced, leading to inefficient
operations (up to O(V)O(V)O(V) time complexity).
● In anOptimal BST, the tree isbalanced and well-structured,reducing the height and
ensuring better average search times.
Problem Statement
Given:
● A set ofkeysK1,K2,...,KnK_1, K_2, ..., K_nK1,K2,...,Kn.
● For each key KiK_iKi:
○ pip_ipi: the probability of accessing the key KiK_iKi.
○ qiq_iqi: the probability of accessing a non-existent key in between KiK_iKiand
Ki+1K_{i+1}Ki+1(representing gaps).
Objective:Construct a binary search tree with a structurethat minimizes theexpected search
📘
✅
cost.
Steps to Construct an Optimal BST
Step 1: Define the Probabilities
For a set ofn keysK1,K2,...,KnK_1, K_2, ..., K_nK1,K2,...,Kn:
● pip_ipi: Probability of accessing key KiK_iKi.
✅ ● qiq_iqi: Probability of accessing anon-existentkeybetween KiK_iKiand Ki+1K_{i+1}Ki+1.
Step 2: Define the Cost Formula
Let e[i][j]e[i][j]e[i][j] be thecost of the optimalBST containing keys from iii to jjj(i.e., KiK_iKito
KjK_jKj).
Cost Recurrence Formula:
e[i][j]=mini≤r≤j(e[i][r−1]+e[r+1][j]+w[i][j])e[i][j] = \min_{i \leq r \leq j} \left( e[i][r-1] + e[r+1][j] + w[i][j]
\right)e[i][j]=i≤r≤jmin(e[i][r−1]+e[r+1][j]+w[i][j])
Where:
● rrr is the root of the tree in the subtree containing iii to jjj.
● w[i][j]w[i][j]w[i][j] is the sum of the probabilities of accessing the keys and the gaps between
them:
w[i][j]=∑k=ijpk+∑k=i−1jqkw[i][j] = \sum_{k=i}^j p_k + \sum_{k=i-1}^j q_kw[i][j]=k=i∑jpk+k=i−1∑jqk
✅
Step 3: Initialize the Cost Matrices
1. For a single key KiK_iKi, the cost e[i][i]e[i][i]e[i][i] is just the probability of accessing KiK_iKi:
e[i][i]=pi+qi−1e[i][i] = p_i + q_{i-1}e[i][i]=pi+qi−1
✅
Step 4: Use Dynamic Programming to Build Subproblems
● Build the matrix e[i][j]e[i][j]e[i][j] iteratively from smaller subtrees to larger ones (bottom-up
approach).
● For every possible subtree size j−i+1j - i + 1j−i+1, try every possible root rrr and compute the
cost using the recursive formula.
✅
Step 5: Reconstruct the Optimal Tree
Once the matrix e[i][j]e[i][j]e[i][j] is filled, you can backtrack to reconstruct the structure of the
optimal tree.
🔹
Example
Let’s consider an example with3 keys:
Given Probabilities:
● Keys: K1,K2,K3K_1, K_2, K_3K1,K2,K3
● p1=0.1p_1 = 0.1p1=0.1, p2=0.5p_2 = 0.5p2=0.5, p3=0.2p_3 = 0.2p3=0.2
● Gaps: q0=0.05q_0 = 0.05q0=0.05, q1=0.1q_1 = 0.1q1=0.1
bjective:
O
Construct a tree that minimizes the search cost using the dynamic programming approach.
1. Initialize a cost matrix e[i][j]e[i][j]e[i][j].
2. Use the recurrence formula to fill in the costs for all nodes by trying different roots.
3. Reconstruct the tree according to the optimal choices for the roots.
✅ Advantages of Optimal BST
✅
Advantages
nt Search Operations
es average search, insert, and delete costs.
memory management and lookup efficiency.
predictable time complexity,close to O(logn)O(\log
gn).
hat is String Editing?
W
● TheString Editing probleminvolves transforming onestring into another with a series of
operations, such asInsertion, Deletion, and Substitution.
● Commonly known as theEdit Distance ProbleminDynamicProgramming.
Operations:
1. Insertion: Add a character to the string.
2. Deletion: Remove a character from the string.
3. Substitution: Replace one character with another.
Dynamic Programming Approach
● Create a2-dimensional tableto represent the editdistance between each pair of characters
in the two strings.
● Let’s say we have two stringsAAA and BBB:
○ dp[i][j]dp[i][j]dp[i][j] stores the minimum number of operations required to convert the firstiii
characters of string AAA to the firstjjjcharactersof string BBB.
Time Complexity:
📌 ● For strings of length mmm and nnn, the time complexity is O(m×n)O(m \times n)O(m×n).
Applications of String Editing
● Spell Checking
● DNA sequence analysis
● Text comparison and version control
● Data cleaning and transformation
