BVRITHYDERABAD COLLEGE OF ENGINEERING

FOR WOMEN
ADVANCED ALGORITHMS
[Link] (1ST YEAR 2ND SEM)
STUDENT LAB MANUAL
CYCLE-2

-JHANSI RENUKA.T
ASSISTANT PROFESSOR
DEPARTMENT OF CSE

1|Page
6. Implement Warshall algorithm

def warshall(graph):
V = len(graph)
closure = [row[:] for row in graph] # Create a copy of the graph

for k in range(V):
for i in range(V):
for j in range(V):
closure[i][j] = closure[i][j] or (closure[i][k] and closure[k][j])

return closure

# Example usage:
graph = [
[1, 1, 0, 1],
[0, 1, 1, 0],
[0, 0, 1, 1],
[0, 0, 0, 1]
]

closure = warshall(graph)
for row in closure:
print(row)

OUTPUT:

[1, 1, 1, 1]
[0, 1, 1, 1]
[0, 0, 1, 1]
[0, 0, 0, 1]

2|Page
7. Implement the Rabin Karp algorithm.

def rabin_karp_search(text: str, pattern: str, d: int = 256, q: int = 101):

"""Find and print all starting indices of pattern in text."""
n, m = len(text), len(pattern)
if m > n:
return

h = pow(d, m - 1, q) # Value for highest-order digit

p_hash = 0 # Hash value for pattern
t_hash = 0 # Hash value for text window

# Initial hash computation

for i in range(m):
p_hash = (d * p_hash + ord(pattern[i])) % q
t_hash = (d * t_hash + ord(text[i])) % q

for i in range(n - m + 1):

# If hashes match, verify substring
if p_hash == t_hash:
if text[i:i + m] == pattern:
print(f"Pattern found at index {i}")

# Compute next window hash

if i < n - m:
t_hash = (d * (t_hash - ord(text[i]) * h) + ord(text[i + m])) % q
if t_hash < 0:
t_hash += q

if __name__ == "__main__":
txt = "THIS IS A TEST TEXT"
pat = "TEST"
rabin_karp_search(txt, pat)
print("---")
txt2 = "AABAACAADAABAABA"
pat2 = "AABA"
rabin_karp_search(txt2, pat2)

OUTPUT:

Pattern found at index 10

---
Pattern found at index 0
Pattern found at index 9
Pattern found at index 12

3|Page
8. Implement the KMP algorithm.

def compute_lps(pat: str) -> list[int]:

"""Compute the LPS (Longest Proper Prefix which is also Suffix) array."""
m = len(pat)
lps = [0] * m
length = 0 # length of the previous longest prefix suffix
i=1

while i < m:
if pat[i] == pat[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
# don't increment i here
else:
lps[i] = 0
i += 1
return lps

def kmp_search(txt: str, pat: str) -> list[int]:

"""Return list of start indices where pat is found in txt."""
n, m = len(txt), len(pat)
if m == 0:
return list(range(n + 1))
if m > n:
return []

lps = compute_lps(pat)
matches = []

i = j = 0 # pointers for txt and pat

while i < n:
if txt[i] == pat[j]:
i += 1
j += 1

if j == m:
[Link](i - j)
j = lps[j - 1]
else:
if j != 0:
j = lps[j - 1]
else:
i += 1

return matches

4|Page
if __name__ == "__main__":
text1 = "THIS IS A TEST TEXT"
pattern1 = "TEST"
print("Matches in text1:", kmp_search(text1, pattern1))

text2 = "AABAACAADAABAABA"
pattern2 = "AABA"
print("Matches in text2:", kmp_search(text2, pattern2))

OUTPUT:

Matches in text1: [10]

Matches in text2: [0, 9, 12]

5|Page
9. Implement Harspool algorithm

def preprocess_shift(pat: str, sigma: int = 256) -> list[int]:

"""Build shift table for Horspool algorithm."""
m = len(pat)
table = [m] * sigma
for i in range(m - 1):
table[ord(pat[i])] = m - 1 - i
return table

def horspool_search(text: str, pat: str) -> list[int]:

"""
Return list of starting indices where `pat` occurs in `text`
using Horspool's algorithm.
"""
n, m = len(text), len(pat)
if m == 0:
return list(range(n + 1))
if m > n:
return []

shift = preprocess_shift(pat)
matches = []
i=0
while i <= n - m:
# Compare from end of pattern backwards
k=m-1
while k >= 0 and pat[k] == text[i + k]:
k -= 1
if k < 0:
[Link](i)
# Determine shift amount: use char following the window
next_char = text[i + m - 1]
i += shift[ord(next_char)]
return matches

if __name__ == "__main__":
t1 = "THIS IS A TEST TEXT"
p1 = "TEST"
print("Matches in t1:", horspool_search(t1, p1))

t2 = "AABAACAADAABAABA"
p2 = "AABA"
print("Matches in t2:", horspool_search(t2, p2))

OUTPUT:

Matches in t1: [10]

Matches in t2: [0, 9, 12]

6|Page
10. Implement max-flow problem.

from collections import deque

def bfs(rgraph, s, t, parent):

visited = [False] * len(rgraph)
queue = deque([s])
visited[s] = True

while queue:
u = [Link]()
for v, cap in enumerate(rgraph[u]):
if not visited[v] and cap > 0:
[Link](v)
visited[v] = True
parent[v] = u
if v == t:
return True
return False

def ford_fulkerson(graph, source, sink):

# Initialize residual graph
rgraph = [row[:] for row in graph]
parent = [-1] * len(graph)
max_flow = 0

# Augment while a path exists

while bfs(rgraph, source, sink, parent):
path_flow = float('inf')
v = sink
while v != source:
u = parent[v]
path_flow = min(path_flow, rgraph[u][v])
v=u

# Add path flow to total flow

max_flow += path_flow

# Update residual capacities

v = sink
while v != source:
u = parent[v]
rgraph[u][v] -= path_flow
rgraph[v][u] += path_flow
v=u

return max_flow

if __name__ == "__main__":
graph = [

7|Page
 [0, 16, 13, 0, 0, 0],
[0, 0, 10, 12, 0, 0],
[0, 4, 0, 0, 14, 0],
[0, 0, 9, 0, 0, 20],
[0, 0, 0, 7, 0, 4],
[0, 0, 0, 0, 0, 0]
]
source, sink = 0, 5
result = ford_fulkerson(graph, source, sink)
print("The maximum possible flow is:", result)

OUTPUT:

The maximum possible flow is: 23

8|Page
 Additional Programs
11. Develop a program to find the shortest path from a single source to all other nodes
in a weighted graph using Dijkstra’s algorithm.

import heapq

def dijkstra(graph: dict, start: str):

"""
Returns two dicts:
- distances[v]: shortest distance from start to v
- parents[v]: immediate predecessor of v along the shortest path
"""
distances = {node: float('inf') for node in graph}
distances[start] = 0
parents = {node: None for node in graph}
pq = [(0, start)]

while pq:
current_dist, u = [Link](pq)
if current_dist > distances[u]:
continue

for v, weight in graph[u]:

distance_through_u = current_dist + weight
if distance_through_u < distances[v]:
distances[v] = distance_through_u
parents[v] = u
[Link](pq, (distance_through_u, v))

return distances, parents

def reconstruct_path(parents: dict, target: str) -> list[str]:

"""Rebuilds path from start to target using the parents dict."""
path = []
while target is not None:
[Link](target)
target = parents[target]
return path[::-1]

if __name__ == "__main__":
# Example graph as adjacency list: node -> list of (neighbor, weight)
graph = {
'A': [('B', 1), ('C', 4)],
'B': [('C', 2), ('D', 5)],
'C': [('D', 1)],
'D': []
}
source = 'A'
distances, parents = dijkstra(graph, source)
9|Page
 print(f"Shortest distances from {source}:")
for node, dist in [Link]():
print(f" {node}: {dist}")

print("\nShortest paths from source:")

for node in graph:
path = reconstruct_path(parents, node)
print(f" {source} -> {node}: {' -> '.join(path)}")

OUTPUT:

Shortest distances from A:

A: 0
B: 1
C: 3
D: 4

Shortest paths from source:

A -> A: A
A -> B: A -> B
A -> C: A -> B -> C
A -> D: A -> B -> C -> D

10 | P a g e
12. Implement the Boyer Moore string matching algorithm.

NO_OF_CHARS = 256

def bad_character_heuristic(pat: str) -> list[int]:

"""Build the last-occurrence table for pattern."""
bad = [-1] * NO_OF_CHARS
for i, ch in enumerate(pat):
bad[ord(ch)] = i
return bad

def boyer_moore_search(txt: str, pat: str) -> list[int]:

"""Return starting indices of all occurrences of pat in txt."""
n, m = len(txt), len(pat)
if m == 0 or m > n:
return []

bad = bad_character_heuristic(pat) # Preprocessing

matches = []
s = 0 # shift

while s <= n - m:
j=m-1

# Compare from right to left

while j >= 0 and pat[j] == txt[s + j]:
j -= 1

if j < 0:
[Link](s)
# Shift by full pattern or by last occurrence
s += m - bad[ord(txt[s + m])] if s + m < n else 1
else:
# Shift based on bad character rule
shift = max(1, j - bad[ord(txt[s + j])])
s += shift

return matches

if __name__ == "__main__":
text1 = "THIS IS A TEST TEXT"
pattern1 = "TEST"
print("Matches in text1:", boyer_moore_search(text1, pattern1))

text2 = "AABAACAADAABAABA"
pattern2 = "AABA"
print("Matches in text2:", boyer_moore_search(text2, pattern2))

11 | P a g e
OUTPUT:

Matches in text1: [10]

Matches in text2: [0, 9, 12]

12 | P a g e
13. Implementation of the 0/1 Knapsack problem using dynamic programming (bottom-
up tabulation). It outputs the maximum profit and the items chosen:
def knap_sack(wt: list[int], val: list[int], W: int):
n = len(val)
# DP table: (n+1) x (W+1)
dp = [[0] * (W + 1) for _ in range(n + 1)]

# Build table
for i in range(1, n + 1):
for w in range(1, W + 1):
if wt[i - 1] <= w:
dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]],
dp[i - 1][w])
else:
dp[i][w] = dp[i - 1][w]

# Maximum value is dp[n][W]

max_value = dp[n][W]

# Reconstruct which items were taken

taken = []
w=W
for i in range(n, 0, -1):
# if current row value differs from the one above, item is taken
if dp[i][w] != dp[i - 1][w]:
[Link](i - 1)
w -= wt[i - 1]

[Link]()
return max_value, taken

13 | P a g e
if __name__ == "__main__":
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50

max_val, items = knap_sack(weights, values, capacity)

print(f"Maximum value in knapsack = {max_val}")
print("Items taken (0‑based indices):", items)
print(" (weight, value):",
[ (weights[i], values[i]) for i in items ])

OUTPUT:
Maximum value in knapsack = 220
Items taken (0-based indices): [1, 2]
(weight, value): [(20, 100), (30, 120)]

14 | P a g e
14. Implementation of the graph coloring problem using backtracking.
def is_safe(vertex, graph, color, c):
for i in range(len(graph)):
if graph[vertex][i] == 1 and color[i] == c:
return False
return True

def graph_coloring_util(graph, m, color, vertex):

if vertex == len(graph):
return True

for c in range(1, m + 1):

if is_safe(vertex, graph, color, c):
color[vertex] = c
if graph_coloring_util(graph, m, color, vertex + 1):
return True
color[vertex] = 0
return False

def graph_coloring(graph, m):

color = [0] * len(graph)
if not graph_coloring_util(graph, m, color, 0):
print("Solution does not exist.")
return False

print("Solution Exists: Following are the assigned colors:")

for c in color:
print(c, end=' ')
print()
return True

15 | P a g e
# Example usage:
graph = [
[0, 1, 1, 1],
[1, 0, 1, 0],
[1, 1, 0, 1],
[1, 0, 1, 0]
]
m = 3 # Number of colors
graph_coloring(graph, m)

OUTPUT:
Solution Exists: Following are the assigned colors:
1232
True

16 | P a g e