Dynamic programming (DP) is an algorithmic technique used to solve complex problems by

breaking them down into smaller, overlapping subproblems. It's particularly effective when a
problem exhibits two key properties:
 Optimal Substructure:
 Overlapping Subproblems:
Optimal Substructure:
 This principle states that an optimal solution to a problem can be constructed
from optimal solutions to its subproblems.
 If a problem exhibits optimal substructure, it means that the global optimal
solution can be found by combining the optimal solutions of smaller,
independent parts of the problem.
 For example, in finding the shortest path in a graph, the shortest path from a
source to a destination via an intermediate node 'X' is composed of the shortest
path from the source to 'X' and the shortest path from 'X' to the destination.
 Overlapping Subproblems:
 This principle indicates that a problem can be divided into subproblems that are
reused multiple times throughout the computation.
 Instead of recomputing the solution to the same subproblem repeatedly,
dynamic programming stores the results of solved subproblems (using
techniques like memoization or tabulation) to avoid redundant calculations.
 A classic example is the Fibonacci sequence, where
calculating fib(n) requires fib(n-1) and fib(n-2), and these subproblems overlap
significantly in a naive recursive solution.
A Multistage Graph is a directed graph in which the nodes are divided into stages, and
every edge moves from one stage to the next stage only.
The goal is to find the minimum cost path from the source (first stage) to the destination
(last stage).
Characteristics
 The graph is divided into k stages.
 Each node in stage i connects only to nodes in stage i+1.
 Each edge has a cost.
 We find the minimum total cost path using the Forward Method.
Forward Method (Steps)
1. Start at the source node (stage 1).
2. Move forward stage by stage.
3. For each node, calculate the minimum cost to reach that node.
4. Continue until the last stage is reached.
5. Trace back the path that gives the minimum cost.
Example Multistage Graph
Stage-1 Stage-2 Stage-3 Stage-4
A → B C → D E → F
Edge Costs: A → B = 2A → C = 3B → D = 5B → E = 4C → D = 6C → E = 2D → F = 3E → F
=4
Step-by-Step Forward ComputationStage 3 → Stage 4Cost to reach F:Cost(D,F) =
3Cost(E,F) = 4Stage 2 → Stage 3Compute cost of B and C:Cost(A,B) + Cost(B,D) +
Cost(D,F)Cost(B) = 2 + 5 + 3 = 10Cost(A,B) + Cost(B,E) + Cost(E,F)Cost(B through E) = 2 + 4
+ 4 = 10So Cost(B) = minimum = 10Cost(C) through D = 3 + 6 + 3 = 12Cost(C) through E =
3 + 2 + 4 = 9So Cost(C) = 9Stage 1 → Stage 2Cost(A → B) = 10Cost(A → C) = 9So choose
the minimum:Best Cost = 9
Minimum Cost PathA → C → E → FMinimum Cost= 3 + 2 + 4= 9

The single-source shortest path problem in Data Structures and Algorithms (DSA) involves
finding the shortest paths from a designated source vertex to all other vertices in a given
graph. This problem is fundamental in many applications, such as network routing, GPS
navigation, and logistics.
Dijkstra's Algorithm (for non-negative edge weights):
Dijkstra's algorithm is a greedy algorithm commonly used to solve the single-source shortest
path problem in graphs where all edge weights are non-negative.
Example:
Consider a weighted, undirected graph representing cities and roads, where edge weights
represent distances.
Code
Graph:
A --(4)--> B
A --(2)--> C
B --(5)--> D
C --(1)--> D
C --(8)--> E
D --(3)--> E
Let's find the shortest paths from source vertex 'A' to all other vertices using Dijkstra's
algorithm.
 Initialization:
o distances = {A: 0, B: Infinity, C: Infinity, D: Infinity, E: Infinity}
o priorityQueue = [(0, A)] (stores tuples of (distance, vertex))
 Iteration:
 o Extract (0, A) from priorityQueue.
o For neighbors of A:
 B: distances[B] becomes 0 + 4 = 4. Add (4, B) to priorityQueue.
 C: distances[C] becomes 0 + 2 = 2. Add (2, C) to priorityQueue.
o Extract (2, C) from priorityQueue.
o For neighbors of C:
 D: distances[D] becomes 2 + 1 = 3. Add (3, D) to priorityQueue.
 E: distances[E] becomes 2 + 8 = 10. Add (10, E) to priorityQueue.
o Extract (3, D) from priorityQueue.
o For neighbors of D:
 B: distances[B] is 4. Path through D would be 3 + 5 = 8, which is not
shorter.
 E: distances[E] is 10. Path through D would be 3 + 3 = 6, which is
shorter. Update distances[E] to 6. Add (6, E) to priorityQueue.
o Extract (4, B) from priorityQueue.
o For neighbors of B:
 D: distances[D] is 3. Path through B would be 4 + 5 = 9, not shorter.
o Extract (6, E) from priorityQueue. No unvisited neighbors.
 Result: distances = {A: 0, B: 4, C: 2, D: 3, E: 6}
The All-Pairs Shortest Path (APSP) Floyd-Warshall
The All-Pairs Shortest Path (APSP) problem in Data Structures and Algorithms (DSA) involves

graph with 𝑁vertices, the goal is to determine the shortest path from vertex 𝑖 to vertex 𝑗for
finding the shortest path between every pair of vertices in a given graph. This means for a

all possible combinations of I and 𝑗

The Floyd-Warshall algorithm is a common dynamic programming approach to solve the APSP
problem. It iteratively updates a distance matrix, considering intermediate vertices to find
shorter paths.
Algorithm Steps:
 Initialization: Create a distance matrix, dist, where dist[i][j] initially stores the direct
edge weight between vertex i and j. If no direct edge exists, set dist[i][j] to infinity. Set
dist[i][i] to 0 for all vertices i.
 Iteration: For each vertex k from 0 to
If dist[i][k] + dist[k][j] < dist[i][j], then update dist[i][j] = dist[i][k] + dist[k][j]. This step
essentially checks if using k as an intermediate vertex provides a shorter path from i to
j.
Example:
Consider a graph with 4 vertices (0, 1, 2, 3) and the following initial adjacency matrix
representing direct edge weights:
Code dist = [ [0, 3, 6, 15], [INF, 0, -2, INF], [INF, INF, 0, 2], [1, INF, INF, 0]]
Iteration 1 (k = 0):
Consider paths using vertex 0 as an intermediate. For example, dist[1][3] (path from 1 to 3)
can potentially be shortened if dist[1][0] + dist[0][3] is less than the current dist[1][3].
Iteration 2 (k = 1):
Consider paths using vertex 1 as an intermediate.
Iteration 3 (k = 2):
Consider paths using vertex 2 as an intermediate.
After all iterations, the dist matrix will contain the shortest path distances between all pairs of
vertices.
Output (Final dist matrix after Floyd-Warshall):
Code dist = [[0, 3, 1, 3], [2, 0, -2, 0], [4, 2, 0, 2], [1, 4, 2, 0]]
This final matrix shows the shortest path from any vertex For instance, the shortest path from
vertex 0 to vertex 2 is 1 (via 0 -> 1 -> 2).

Binary Search Tree (BST)

A Binary Search Tree is a special type of binary tree in which each node contains a value
and follows a specific ordering property.
In a BST, each node has at most two children: a left child and a right child.
BST Property
For every node in the BST:
 The left subtree contains values less than the node’s value.
 The right subtree contains values greater than the node’s value.
 There are no duplicate values in the BST.
This property helps in fast searching, inserting and deleting operations.
Structure of a BST Node
Each node contains:
1. Data (value)
2. Pointer to left child
3. Pointer to right child
Example:
40
/ \
30 60
30 < 40 → goes to left
60 > 40 → goes to right
Insertion in BST
To insert a new value:
1. Compare the value with the root.
2. If the new value is smaller, go to the left subtree.
3. If the new value is larger, go to the right subtree.
4. Repeat this process until an empty position is found and place the new value there.
Example: Insert 25, 35, 50, 70 into BST
 40
/ \
30 60
/\ /\
25 35 50 70
Searching in BST
Searching follows the same rule:
 If the value is less than the current node → move left
 If greater → move right
 If equal → value found
This makes searching faster than in linear data structures.
Tree Traversals in BST
Traversals are used to visit all nodes:
1. Inorder (Left → Root → Right)
This prints the values in ascending order.
Example: 25, 30, 35, 40, 50, 60, 70
2. Preorder (Root → Left → Right)
Used to create a copy of the tree.
3. Postorder (Left → Right → Root)
Used to delete or free the tree.
Advantages of BST
1. Searching is fast because we avoid half of the tree at each step.
2. Easy insertion and deletion.
3. Inorder traversal gives sorted output.
Disadvantages of BST
1. Performance becomes poor if tree becomes skewed (like a linked list).
2. In worst case, time complexity becomes O(n).
Applications of BST
1. Used in search engines for quick lookup.
2. Used in database indexing.
3. Used in symbol tables in compilers.
4. Used in sorting and range searching.
Threaded Binary Search Tree
In a binary search tree, many nodes have NULL pointers for their left or right child,
especially the leaf nodes. These NULL pointers do not store any useful information. To make
use of these NULL pointers, the concept of Threaded Binary Tree is introduced.
A Threaded Binary Search Tree is a modified form of a binary search tree in which the
NULL pointers are replaced with special links called threads. These threads help in
making inorder traversal faster and do not require a stack or recursion.
Idea Behind Threading
In inorder traversal, after visiting a node, the next node to be visited is known as its
inorder successor.
Similarly, the previous node is known as the inorder predecessor.
In a Threaded BST:
 The right NULL pointer of a node is replaced with a thread pointing to its inorder
successor.
 The left NULL pointer can also be replaced with a thread pointing to its inorder
predecessor (if needed).
Types of Threaded Binary Trees
1. Single Threaded Binary Tree
Only one side (either left or right) NULL pointers are replaced with threads, usually the
right side.
2. Double Threaded Binary Tree
Both left and right NULL pointers are replaced with threads.
Left thread points to inorder predecessor, and right thread points to inorder
successor.
Example (Single Threaded)
Without threading (normal BST):
40
/ \
30 60
/
50
Node 30’s right pointer is NULL, but in inorder traversal, the next node after 30 is [Link]
instead of NULL, we thread 30 → 40.
Threaded representation concept:
40
/ \
30→ 60
/
50(Here, → indicates a thread link to inorder successor)
Advantages
1. Inorder traversal becomes faster.
2. No need for stack or recursion for traversal.
3. Makes better use of memory by replacing NULL pointers.
4. Traversing to next node takes constant time (O(1)).
Disadvantages
1. Insertion and deletion become more complex.
2. Thread links must be updated carefully after modifications.
Applications
 Used in situations where inorder traversal is very frequent.
  Helpful in memory-limited systems where stack us

Breadth First Search (BFS)

Breadth First Search is a graph traversal technique in which we visit nodes level by level.
It starts from a source node, visits all the nearest (adjacent) nodes first, and then moves
to the next level of nodes.
BFS uses a Queue data structure.
Algorithm (Idea):
1. Start from the source node and insert it into the queue.
2. Remove a node from the queue, visit it.
3. Insert all its unvisited adjacent nodes into the queue.
4. Repeat until the queue is empty.
Example Order:
If we start from A, and its neighbors are B and C, we visit:
A → B → C → next level…
Use of BFS:
 Finding the shortest path in an unweighted graph Level-wise traversal in trees
 Used in network broadcasting
Depth First Search (DFS)
Depth First Search is a graph traversal technique in which we go as deep as possible along
one path, and then backtrack.
It starts from a source node, moves to one adjacent node, then to that node’s adjacent, and
so on. DFS uses Stack (or recursion).
Algorithm (Idea):
1. Start from the source node.
2. Visit a node, move to one of its unvisited neighbors.
3. Continue going deeper until no more unvisited nodes remain.
4. Go back (backtrack) and explore remaining paths.
Example Order:
A → B → D → back → C → etc.
Use of DFS:
 Useful in maze and puzzle solving
 Used to find connected components in a graph
 Helpful in topological sorting