1.
Longest Common Subsequence using Dynamic
Programming
Aim: To find the Longest Common Subsequence of two strings using Dynamic Programming.
Algorithm:
1. Input two strings X and Y.
2. Create a table dp of size (m+1) × (n+1) initialized to 0.
3. Fill the table using recurrence:
if X[i-1] == Y[j-1]: dp[i][j] = dp[i-1][j-1] + 1
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
4. Trace back from dp[m][n] to construct one LCS string.
5. Display LCS length and the sequence.
Program (Python):
def lcs(X, Y):
m, n = len(X), len(Y)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if X[i-1] == Y[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
i, j = m, n
lcs_str = ""
while i > 0 and j > 0:
if X[i-1] == Y[j-1]:
lcs_str = X[i-1] + lcs_str
i -= 1
j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return dp[m][n], lcs_str
X = input("Enter first string: ")
Y = input("Enter second string: ")
length, seq = lcs(X, Y)
print("LCS length:", length)
print("LCS:", seq)
Sample Output:
Enter first string: ABCBDAB
Enter second string: BDCABA
LCS length: 4
LCS: BCAB
Conclusion: Longest Common Subsequence is obtained using Dynamic Programming.
Complexity (Observation):
Time Complexity: O(m × n)
Space Complexity: O(m × n)
2. N-Queens Problem using Backtracking
Aim: To place N queens on an N×N chessboard so that no two queens attack each other using
Backtracking.
Algorithm:
1. Input N (number of queens).
2. Place queens row by row using recursion.
3. Check if placing a queen at (row, col) is safe.
4. If safe, place queen and recur for next row.
5. If all queens placed, store solution.
6. Backtrack and print all valid configurations.
Program (Python):
def is_safe(board, row, col, n):
for i in range(row):
if board[i][col] == 1:
return False
if col - (row - i) >= 0 and board[i][col - (row - i)] == 1:
return False
if col + (row - i) < n and board[i][col + (row - i)] == 1:
return False
return True
def solve_nqueens(board, row, n, solutions):
if row == n:
sol = ["".join("Q" if c == 1 else "." for c in r) for r in board]
[Link](sol)
return
for col in range(n):
if is_safe(board, row, col, n):
board[row][col] = 1
solve_nqueens(board, row + 1, n, solutions)
board[row][col] = 0
n = int(input("Enter number of queens: "))
board = [[0]*n for _ in range(n)]
solutions = []
solve_nqueens(board, 0, n, solutions)
print("Total Solutions:", len(solutions))
for s in solutions:
for row in s:
print(row)
print()
Sample Output:
Enter number of queens: 4
Total Solutions: 2
.Q..
...Q
Q...
..Q.
..Q.
Q...
...Q
.Q..
Conclusion: All possible placements of N queens are obtained using Backtracking.
Complexity (Observation):
Time Complexity: O(N!)
Space Complexity: O(N²)
3. Graph Coloring Problem using Backtracking
Aim: To color a graph with minimum colors so that adjacent vertices do not share the same color
using Backtracking.
Algorithm:
1. Input number of vertices n and adjacency matrix.
2. Input number of colors m.
3. Assign colors to vertices using recursion.
4. Check if color assignment is safe for each vertex.
5. Recur for next vertex; if all colored, store solution.
6. Print all valid colorings.
Program (Python):
def is_safe(v, graph, color, c, n):
for i in range(n):
if graph[v][i] == 1 and color[i] == c:
return False
return True
def graph_coloring(graph, m, color, v, n, solutions):
if v == n:
[Link](color[:])
return
for c in range(1, m+1):
if is_safe(v, graph, color, c, n):
color[v] = c
graph_coloring(graph, m, color, v+1, n, solutions)
color[v] = 0
n = int(input("Enter number of vertices: "))
print("Enter adjacency matrix:")
graph = [list(map(int, input().split())) for _ in range(n)]
m = int(input("Enter number of colors: "))
color = [0]*n
solutions = []
graph_coloring(graph, m, color, 0, n, solutions)
print("Valid Colorings:")
for s in solutions:
print(s)
print("Total Colorings:", len(solutions))
Sample Output:
Enter number of vertices: 4
Enter adjacency matrix:
0 1 1 1
1 0 1 0
1 1 0 1
1 0 1 0
Enter number of colors: 3
Valid Colorings:
[1, 2, 3, 2]
[1, 3, 2, 3]
Total Colorings: 2
Conclusion: All valid graph colorings are generated using Backtracking.
Complexity (Observation):
Time Complexity: O(m■)
Space Complexity: O(n)