Analysis of Algorithms
SE – 4th (A) Spring - 22
Topic: Dynamic Programming & Backtracking
Presentation Supervised by: Dr, Shahzad Akbar
Presented by: Shayan Ahmed Shahid – 16998
Riphah College of Computing, Faisalabad
Table of contents
• Dynamic Programming
• Approaches of Dynamic Programming
• LCS – Longest Common Subsequence in Dynamic Programming
• Back Tracking
• Where it is used
• DFS – Depth First Search
Dynamic Programming
• Dynamic Programming is an algorithmic technique that Is almost near to divide and
conquer approach, However the divide and conquer has recursive nature. Dynamic
Programming refers to breaking down a big problem into simpler sub-problems in a
recursive manner in both contexts.
• Dynamic Programming have 2 types;
Dynamic
Programming Top Down
(Memorization &
Recursive)
Bottom Up (Tabulation
& Iterative)
Approaches of DP
• Top-down approach
The top-down approach follows the memorization technique.
It consists of two distinct events: recursion and caching.
‘Recursion’ represents the process of computation by calling
functions repeatedly, whereas ‘caching’ represents the storing
of intermediate results.
• Bottom-up approach
This approach uses the tabulation technique to implement the
dynamic programming solution. It addresses the same
problems as before, but without recursion. The recursion is
replaced with iteration in this approach. Hence, there is no
stack overflow error or overhead of recursive procedures. We
maintain a table to solve the problem in this method.
LCS – Longest Common Subsequence
• Given two sequences, find the length of the longest subsequence present in both of
them. A subsequence is sequence that appears in the same relative order, but not
necessarily Continuous. You can’t intercept the sequence.
• Problem Statement • Problem Statement
• String01: b d \0 • String01: s t o n e
• String02: a b c d \0 • String02: l o n g e s t
• Algorithm Top Down (Recursive) • Algorithm Bottom Up
int LCS(I,j) If(A[i]=B[i])
{
if(A[i]==‘\0’||B[j]==‘\0’) LCS[i,j] = 1 + LCS [i-1, j-1]
return 0;
elseif(A[i]==B[j]) Else
return 1+LCS(i+1,j+1);
else LCS[i,j] = max (LCS [i-1,j] LCS[i,j-1])
return max(LCS(i+1,j),LCS(I,j+1));
}
LCS – Using Top Down
A[0].B[0]
b,a=2
A[1],B[0] A[0],B[1]
d,a=1 b,b=2 A B C D \0
(Showing
Memorization)
A[2],B[0] A[1],B[1] A[1],B[2]
0 1 2 3 4
\0,a=0 d,b=1 d,c=1
B 0 2 2 - - -
A[2],B[1] A[1],B[2] A[2],B[3] A[1],B[3]
\0,b=0 d,c=1 \0,c=0 d,d=1 D 1 1 1 1 1 -
A[2],B[2] A[1],B[3] A[2],B[4] \0 2 0 0 0 - 0
\0,c=0 d,d=1 \0,\0=0
A[2],B[4]
\0,\0=0
LCS – Using Bottom Up
2D formation L O N G E S T
of LCS
0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
S 1 0 0 0 0 0 0 1 1
T 2 0 0 0 0 0 0 1 2
O 3 0 0 1 1 1 1 1 2
N 4 0 0 1 2 2 2 2 2
E 5 0 0 1 2 2 3 3 3
- - - - O N - E - -
The sequence we get from Stone & Longest is ONE, we got 3 by adding 2 from G, then we
got 2 by adding 1 in N from O, we got 1 in adding 1 in 0.
Complexity O(mn) m x n.
Backtracking
• A backtracking algorithm is a problem-solving algorithm that
uses a b1rute force approach for finding the desired output.
“The Brute force approach tries out all the possible solutions
and chooses the desired/best solutions”
• The term backtracking suggests that if the current solution is
not suitable, then backtrack and try other solutions.
• Backtracking is an idea which can be applied to any recursive
algorithm.
• State Space Tree
• A space state tree is a tree representing all the possible states
(solution or nonsolution) of the problem from the root as an
initial state to the leaf as a terminal state.
Where it is used?
• Where backtracking can be used?
• DFS (Graph Traversal)
• Brute Force Algorithms
• Recursive Formulation
• For now, We’ll discuss how backtracking works in DFS.
• Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree
structure, or graph. One starts at the root (selecting some node as the root in the graph
case) and explores as far as possible along each branch before backtracking.
DFS – Depth First Search
• A standard DFS implementation puts each vertex of the graph into one of two
categories:
1. Visited
2. Not Visited
• The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.
DFS – Depth First Search
DFS – Depth First Search
Thank You
If you have any queries, feel free
to ask!
Riphah College of Computing,
Faisalabad
