Longest common subsequence using dynamic programming (tabular method)
YT: https://www.youtube.com/watch?v=MNykgz1_ONQ
NOTE ⚠️: This is a Bottom Up DP Approach. Top Down approach through recursion is possible (using recursion)!
# 1. Longest Common Subsequence using Dynamic Programming (Tabular Method)
def longest_common_subsequence(str1: str, str2: str) -> str:
"""
Find the longest common subsequence of two strings using dynamic programming.
Args:
str1 (str): First string
str2 (str): Second string
Returns:
str: The longest common subsequence
"""
n = len(str1)
m = len(str2)
# Create DP table
dp = [[0] * (m + 1) for _ in range(n + 1)] #O(m*n)
# Fill the dp table
for i in range(1, n + 1): #O(m)
for j in range(1, m + 1): #O(n)
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# return dp[n][m] to return the length of longest common subsequence
# if sequence is asked follow below code
# Reconstruct the LCS
lcs = ""
i, j = n, m
while i > 0 and j > 0: #O(m + n)
if str1[i - 1] == str2[j - 1]:
lcs = str1[i - 1] + lcs
i -= 1
j -= 1
elif dp[i - 1][j] > dp[i][j - 1]:
i -= 1
else:
j -= 1
return lcs
# Overall Complexity: O(m*n)
# Example usage
text1 = "ABCBDAB"
text2 = "BDCABA"
print(longest_common_subsequence(text1, text2))
Matrix chain multiplication problem using dynamic programming (tabular method)
YT: https://www.youtube.com/watch?v=pDCXsbAw5Cg
import math
def matrix_chain_multiplication(dimensions: list[int]) -> tuple[int, list[tuple[int, int, int]]]:
"""
Finds the minimum number of scalar multiplications needed to multiply a chain of matrices
and the optimal parenthesization.
Args:
dimensions: A list of integers representing the dimensions of the matrices.
If the matrices are A1, A2, ..., An, then dimensions will be
[p0, p1, p2, ..., pn], where Ai has dimensions pi-1 x pi.
Returns:
A tuple containing:
- The minimum number of scalar multiplications (int).
- A list of tuples representing the optimal split points for parenthesization.
Each tuple (i, j, k) would indicate that the optimal split for the
matrix chain from Ai to Aj occurs at Ak.
"""
n = len(dimensions) - 1 # Number of matrices
dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
S = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
# l is chain length
for l in range(2, n + 1):
for i in range(1, n - l + 2):
j = i + l - 1
dp[i][j] = float('inf')
for k in range(i, j):
# q = cost of multiplying matrices i through k + cost of multiplying matrices k+1 through j
# + cost of multiplying the two resulting matrices
q = dp[i][k] + dp[k + 1][j] + dimensions[i - 1] * dimensions[k] * dimensions[j]
if q < dp[i][j]:
dp[i][j] = q
S[i][j] = k
# Collect the splitting points
split_points = []
def collect_splits(i, j):
if i != j:
k = S[i][j]
split_points.append((i, j, k))
collect_splits(i, k)
collect_splits(k + 1, j)
collect_splits(1, n)
return dp[1][n], split_points
if __name__ == '__main__':
print(matrix_chain_multiplication([10,20,30,40]))
Huffman coding (Greedy technique)
YT: https://www.youtube.com/watch?v=L5MloiCxHPk
# 3. Huffman Coding (Greedy Technique)
def generate_huffman_codes(text: str) -> tuple[dict[str, str], dict[str, int]]:
"""
Generates Huffman codes for the characters in the input text using a greedy approach.
Args:
text: The input string.
Returns:
A tuple:
- Dictionary mapping each character to its Huffman code.
- Dictionary mapping each character to its frequency.
"""
class Node:
def __init__(self, char=None, freq=0):
self.char = char
self.freq = freq
self.left = None
self.right = None
def __lt__(self, other): # For sorting nodes
return self.freq < other.freq
if not text:
return {}, {}
# Step 1: Manually count character frequencies
frequency = {}
for char in text:
if char in frequency:
frequency[char] += 1
else:
frequency[char] = 1
# Step 2: Create a list of Nodes and sort it (acting as a manual min-heap)
nodes = []
for char in frequency:
nodes.append(Node(char, frequency[char]))
# Step 3: Build the Huffman Tree
while len(nodes) > 1:
# Sort nodes by frequency (like a min-heap)
nodes.sort(key=lambda x: x.freq)
# Pick two nodes with smallest frequencies
left = nodes.pop(0)
right = nodes.pop(0)
# Merge them into a new node
merged = Node(freq=left.freq + right.freq)
merged.left = left
merged.right = right
# Add the merged node back to the list
nodes.append(merged)
# Step 4: Traverse the tree to generate codes
root = nodes[0]
huffman_codes = {}
def generate_codes(node, code):
if node is not None:
if node.char is not None:
huffman_codes[node.char] = code
generate_codes(node.left, code + "0")
generate_codes(node.right, code + "1")
generate_codes(root, "")
return huffman_codes, frequency
# Example usage
text = "ABBCCCDDDDEEEEE"
codes = generate_huffman_codes(text)
print("Huffman Codes:", codes)
#VERSION 2 USING HEAPQ
import heapq
from collections import Counter
def generate_huffman_codes(text: str) -> tuple[dict[str, str], dict[str, int]]:
"""
Generates Huffman codes for the characters in the input text using a greedy approach with heapq.
Args:
text: The input string.
Returns:
A tuple:
- Dictionary mapping each character to its Huffman code.
- Dictionary mapping each character to its frequency.
"""
class Node:
def __init__(self, char=None, freq=0):
self.char = char
self.freq = freq
self.left = None
self.right = None
def __lt__(self, other):
return self.freq < other.freq
if not text:
return {}, {}
# Step 1: Count character frequencies using Counter
frequency = Counter(text)
# Step 2: Create a heap of nodes
heap = [Node(char, freq) for char, freq in frequency.items()]
heapq.heapify(heap)
# Step 3: Build the Huffman Tree using the heap
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
merged = Node(freq=left.freq + right.freq)
merged.left = left
merged.right = right
heapq.heappush(heap, merged)
# Step 4: Traverse the tree to generate codes
root = heap[0]
huffman_codes = {}
def generate_codes(node, code):
if node:
if node.char is not None:
huffman_codes[node.char] = code
generate_codes(node.left, code + "0")
generate_codes(node.right, code + "1")
generate_codes(root, "")
return huffman_codes, dict(frequency)
# Example usage
text = "ABBCCCDDDDEEEEE"
codes, freqs = generate_huffman_codes(text)
print("Huffman Codes:", codes)
print("Frequencies:", freqs)
Strassen's Method (Divide and Conquer) - Self-study
YT: https://www.youtube.com/watch?v=OSelhO6Qnlc
YT: https://www.youtube.com/watch?v=2IgZuVGwEb0
# Strassen's Method (Divide and Conquer)
import numpy as np
def strassen_matrix_multiply(A: np.ndarray, B: np.ndarray) -> np.ndarray:
"""
Multiplies two square matrices A and B using Strassen's divide and conquer method.
Assumes the dimensions of A and B are n x n, where n is a power of 2.
Args:
A: The first square matrix (NumPy array).
B: The second square matrix (NumPy array).
Returns:
The product of A and B as a NumPy array.
"""
n = A.shape[0]
# Base case: if the matrix is 1x1
if n == 1:
return A * B
# Divide matrices into quadrants
mid = n // 2
# Divide matrix A into 4 submatrices
A11 = A[:mid, :mid]
A12 = A[:mid, mid:]
A21 = A[mid:, :mid]
A22 = A[mid:, mid:]
# Divide matrix B into 4 submatrices
B11 = B[:mid, :mid]
B12 = B[:mid, mid:]
B21 = B[mid:, :mid]
B22 = B[mid:, mid:]
P1 = strassen_matrix_multiply(A11 + A22, B11 + B22)
P2 = strassen_matrix_multiply(A21 + A22, B11)
P3 = strassen_matrix_multiply(A11, B12 - B22)
P4 = strassen_matrix_multiply(A22, B21 - B11)
P5 = strassen_matrix_multiply(A11 + A12, B22)
P6 = strassen_matrix_multiply(A21 - A11, B11 + B12)
P7 = strassen_matrix_multiply(A12 - A22, B21 + B22)
# Calculate the quadrants of the result matrix
C11 = P1 + P4 - P5 + P7
C12 = P3 + P5
C21 = P2 + P4
C22 = P1 - P2 + P3 + P6
# Combine the quadrants into a single matrix
C = np.zeros((n, n))
C[:mid, :mid] = C11
C[:mid, mid:] = C12
C[mid:, :mid] = C21
C[mid:, mid:] = C22
return C
# Example usage
A = np.array([[1, 2], [3, 4]])
B = np.array([[5, 6], [7, 8]])
C = strassen_matrix_multiply(A, B)
print(C)
Karatsuba Integer multiplication (Divide and conquer): the integers will have at least 256 digits and be stored as strings.
YT: https://www.youtube.com/watch?v=yWI2K4jOjFQ
# Karatsuba Integer Multiplication (Divide and Conquer) for large numbers
def karatsuba_multiply(num1_str: str, num2_str: str) -> str:
"""
Multiplies two large integers (represented as strings) using the Karatsuba algorithm.
Args:
num1_str: The first large integer as a string.
num2_str: The second large integer as a string.
Returns:
The product of the two integers as a string.
"""
# Convert string to integers
num1 = int(num1_str)
num2 = int(num2_str)
# Base case for recursion
if num1 < 10 or num2 < 10:
return str(num1 * num2)
# Calculate the maximum number of digits
m = max(len(num1_str), len(num2_str))
m2 = m // 2
# Split the numbers
power = 10**m2
a = num1 // power
b = num1 % power
c = num2 // power
d = num2 % power
# Recursive steps
ac = int(karatsuba_multiply(str(a), str(c)))
bd = int(karatsuba_multiply(str(b), str(d)))
ad_plus_bc = int(karatsuba_multiply(str(a + b), str(c + d))) - ac - bd
# Return the combined result
result = ac * (10**(2*m2)) + ad_plus_bc * (10**m2) + bd
return str(result)
# Example usage
num1 = "314159265358979323"
num2 = "271828182845904523"
result = karatsuba_multiply(num1, num2)
print(result)
List all the possible solutions to the N-Queens problem using Backtracking
YT: https://www.youtube.com/watch?v=KTygpUDUJ6Q
# N-Queens problem using Backtracking
def solve_nqueens(n: int) -> list[list[int]]:
"""
Finds all possible solutions to the N-Queens problem using backtracking.
Args:
n: The size of the chessboard (N x N).
Returns:
A list of lists, where each inner list represents a valid board configuration.
Each inner list contains the column position of the queen in each row
(e.g., [1, 3, 0, 2] means a queen in column 1 of row 0, column 3 of row 1, etc.).
"""
solutions = []
def is_valid_candidate(state, col):
row = len(state) # Current row for new queen
for i in range(row):
if state[i] == col: # Column conflict
return False
if abs(state[i] - col) == abs(i - row): # Diagonal conflict
return False
return True
def get_candidates(state):
for col in range(n):
if is_valid_candidate(state, col):
yield col
def backtrack(state):
if len(state) == n: # All queens placed
solutions.append(state.copy())
return
for candidate in get_candidates(state):
state.append(candidate)
backtrack(state)
state.pop()
backtrack([])
return solutions
print(solve_nqueens(4))
Simplex Method for Solving Linear Programming Problem
YT: https://www.youtube.com/watch?v=9YKLXFqCy6E
NOTE: This is for maximization as per steps followed in class
import numpy as np
def simplex_method(tableau: np.ndarray) -> tuple[float, dict[str, float]]:
"""
Solves a maximization linear programming problem with a feasible solution
using the Simplex method. Assumes the input is an initial Simplex tableau.
"""
num_rows, num_cols = tableau.shape
num_cols -= 1 # Exclude RHS column for variable count
basic_vars = [num_cols - (num_rows - 1) + i for i in range(num_rows - 1)]
while True:
obj_row = tableau[-1, :-1]
if all(c <= 0 for c in obj_row): # Optimality check
break
enter = np.argmax(obj_row)
ratios = [row[-1] / row[enter] if row[enter] > 0 else float('inf') for row in tableau[:-1]]
leave = np.argmin(ratios)
if all(r == float('inf') for r in ratios): # Unbounded
return float('inf'), {}
pivot = tableau[leave][enter]
tableau[leave] = tableau[leave] / pivot
for i in range(num_rows):
if i != leave:
tableau[i] -= tableau[i][enter] * tableau[leave]
basic_vars[leave] = enter
solution = {f'x{i+1}': 0 for i in range(num_cols)}
for i, var in enumerate(basic_vars):
if var < num_cols:
solution[f'x{var+1}'] = tableau[i, -1]
return -tableau[-1, -1], solution
tableau = np.array([
[ 2, 6, 1, 0, 24], # Constraint 1
[ 6, 2, 0, 1, 24], # Constraint 2
[7, 3, 0, 0, 0] # Objective function
], dtype=float)
# Call the simplex method
optimal_value, solution = simplex_method(tableau)
# Print the result
print("Optimal Value:", optimal_value)
print("Optimal Solution:", solution)
Bellman-Ford Method (dynamic programming) - Graph Algorithm (Graphs will be given in the form of Adjacency Matrices)
YT: https://www.youtube.com/watch?v=obWXjtg0L64
YT: https://www.youtube.com/watch?v=ne9eZ4ezg0Y
import math
def bellman_ford(graph: list[list[float]], source: int) -> tuple[list[float], bool]:
"""
Finds the shortest path distances from a single source vertex to all other vertices
in a weighted directed graph using the Bellman-Ford algorithm.
Args:
graph: A list of lists representing the adjacency matrix of the graph.
graph[i][j] is the weight of the edge from vertex i to vertex j.
Use float('inf') to represent no edge.
source: The index of the source vertex.
Returns:
A tuple containing:
- A list of shortest path distances from the source to each vertex.
distances[i] is the shortest distance from the source to vertex i.
- A boolean indicating whether a negative cycle was detected (True if yes, False if no).
"""
# Number of vertices in the graph
V = len(graph)
# Initialize distances from source to all vertices as infinity
distances = [float('inf')] * V
distances[source] = 0
# Relax all edges |V| - 1 times
for _ in range(V - 1):
for u in range(V):
for v in range(V):
# If there is an edge from u to v
if graph[u][v] != float('inf') and graph[u][v] != 0:
# If there is a shorter path to v through u
if distances[u] != float('inf') and distances[u] + graph[u][v] < distances[v]:
distances[v] = distances[u] + graph[u][v]
# Check for negative weight cycles
negative_cycle = False
for u in range(V):
for v in range(V):
if graph[u][v] != float('inf') and graph[u][v] != 0:
if distances[u] != float('inf') and distances[u] + graph[u][v] < distances[v]:
negative_cycle = True
break
if negative_cycle:
break
return distances, negative_cycle
# Example usage
if __name__ == "__main__":
# math.inf means no edge
graph = [
[math.inf, 6, math.inf, 7, math.inf],
[math.inf, math.inf, 5, 8, -4],
[math.inf, -2, math.inf, math.inf, math.inf],
[math.inf, math.inf, -3, math.inf, 9],
[2, math.inf, 7, math.inf, math.inf]
]
source = 0
distances, has_negative_cycle = bellman_ford(graph, source)
print("Shortest distances from source vertex", source)
for i, dist in enumerate(distances):
print(f"To vertex {i}: {dist}")
print(f"Graph contains negative cycle: {has_negative_cycle}")
VERSION 2
import math
def bellman_ford(graph: list[list[float]], source: int) -> tuple[list[float], bool]:
"""
Finds the shortest path distances from a single source vertex to all other vertices
in a weighted directed graph using the Bellman-Ford algorithm.
Args:
graph: A list of lists representing the adjacency matrix of the graph.
graph[i][j] is the weight of the edge from vertex i to vertex j.
0 represents no edge between vertices.
source: The index of the source vertex.
Returns:
A tuple containing:
- A list of shortest path distances from the source to each vertex.
distances[i] is the shortest distance from the source to vertex i.
- A boolean indicating whether a negative cycle was detected (True if yes, False if no).
"""
# Number of vertices in the graph
V = len(graph)
# Initialize distances from source to all vertices as infinity
distances = [float('inf')] * V
distances[source] = 0
# Relax all edges |V| - 1 times
for _ in range(V - 1):
for u in range(V):
for v in range(V):
# If there is an edge from u to v (non-zero value)
if graph[u][v] != 0:
# If there is a shorter path to v through u
if distances[u] != float('inf') and distances[u] + graph[u][v] < distances[v]:
distances[v] = distances[u] + graph[u][v]
# Check for negative weight cycles
negative_cycle = False
for u in range(V):
for v in range(V):
if graph[u][v] != 0:
if distances[u] != float('inf') and distances[u] + graph[u][v] < distances[v]:
negative_cycle = True
break
if negative_cycle:
break
return distances, negative_cycle
# Example usage
if __name__ == "__main__":
# Example graph where 0 represents no edge
# Note: This approach assumes we can't have an actual edge with weight 0
graph = [
[0, 6, 0, 7, 0],
[0, 0, 5, 8, -4],
[0, -2, 0, 0, 0],
[0, 0, -3, 0, 9],
[2, 0, 7, 0, 0]
]
source = 0
distances, has_negative_cycle = bellman_ford(graph, source)
print("Shortest distances from source vertex", source)
for i, dist in enumerate(distances):
if dist == float('inf'):
print(f"To vertex {i}: Not reachable")
else:
print(f"To vertex {i}: {dist}")
print(f"Graph contains negative cycle: {has_negative_cycle}"
Made with ❤️ By V