1) KNAPSAP PROBLEM-
Step 1 - Begin
Step 2 - If N = 0 OR C = 0 Then
(i) Print "Maximum value = 0"
(ii) Go to Step 7
Step 3 - i = N - 1 (Start from the last item)
Step 4 - If W[i] <= C Then
(i) val1 = V[i] + Knapsack(W, V, N-1, C - W[i]) (Include item i)
(ii) val2 = Knapsack(W, V, N-1, C) (Exclude item i)
(iii) MaxValue = Maximum of val1 and val2
(iv) Print "Maximum value = ", MaxValue
(v) Go to Step 7
Step 5 - Else
(i) MaxValue = Knapsack(W, V, N-1, C) (Exclude item i, as it’s too heavy)
(ii) Print "Maximum value = ", MaxValue
(iii) Go to Step 7
Step 6 - Print "No solution" (This won’t typically happen with valid inputs)
Step 7 – Exit
2) MATRIX CHAIN MULTIPLICATION –
Step 1 - Begin
Step 2 - If N = 1 Then
(i) Print "Cost = 0" (Single matrix, no multiplication)
(ii) Go to Step 7
Step 3 - i = 0 (Start index for splitting the chain)
Step 4 - Repeat Step 5 & 6 While i < N - 1
Step 5 - If i < N - 1 Then
(i) Cost1 = MCM(P, i + 1) (Cost of left part: P[0] to P[i])
(ii) Cost2 = MCM(P + i + 1, N - i - 1) (Cost of right part: P[i+1] to P[N-1])
(iii) CurrentCost = Cost1 + Cost2 + (P[0] * P[i + 1] * P[N]) (Total cost with split at i)
(iv) If i = 0 Then MinCost = CurrentCost
(v) Else If CurrentCost < MinCost Then MinCost = CurrentCost
(vi) i = i + 1
Step 6 - Print "Minimum cost = ", MinCost
Step 7 – Exit
3) PRIMS ALGORITHM-
Step 1 - Begin
Step 2 - i = 0 (Start from vertex 0)
Step 3 - Create Visited array, set Visited[i] = 1 (mark vertex 0 as visited), all others = 0
Step 4 - TotalCost = 0, EdgeCount = 0
Step 5 - Repeat Step 6 & 7 While EdgeCount < N - 1
Step 6 - (i) MinWeight = ∞, u = -1, v = -1
(ii) For each visited node j (Visited[j] = 1):
For each node k from 0 to N-1:
If Visited[k] = 0 AND G[j][k] < MinWeight Then
MinWeight = G[j][k]
u=j
v=k
(iii) If u ≠ -1 AND v ≠ -1 Then
(a) Print "Edge ", u, " - ", v, " with weight ", MinWeight
(b) TotalCost = TotalCost + MinWeight
(c) Visited[v] = 1 (Mark v as visited)
(d) EdgeCount = EdgeCount + 1
Step 7 - Print "Total cost of MST = ", TotalCost
Step 8 – Exit
4) KRUSKAL ALGORITHM-
Step 1 - Begin
Step 2 - i = 0 (Start index for edge list)
Step 3 - Sort G by weight (smallest first)
Step 4 - Create Parent array, set Parent[j] = j for j from 0 to N-1 (each vertex is its own set)
Step 5 - TotalCost = 0, EdgeCount = 0
Step 6 - Repeat Step 7 & 8 While i < E AND EdgeCount < N - 1
Step 7 - If Find(Parent, G[i][0]) ≠ Find(Parent, G[i][1]) Then
(i) Print "Edge ", G[i][0], " - ", G[i][1], " with weight ", G[i][2]
(ii) TotalCost = TotalCost + G[i][2]
(iii) Union(Parent, G[i][0], G[i][1]) (Merge the sets)
(iv) EdgeCount = EdgeCount + 1
(v) i = i + 1
Step 8 - i = i + 1 (Move to next edge if no union)
Step 9 - Print "Total cost of MST = ", TotalCost
Step 10 – Exit
5) DIJKSTRA ALGORITHM-
Step 1 - Begin
Step 2 - i = 0 (Index for initialization)
Step 3 - Create Distance array, set Distance[S] = 0, all others = ∞
Step 4 - Create Visited array, set all Visited[i] = 0 (unvisited)
Step 5 - Repeat Step 6 & 7 While i < N
Step 6 - (i) MinDist = ∞, u = -1
(ii) For j = 0 to N-1:
If Visited[j] = 0 AND Distance[j] < MinDist Then
MinDist = Distance[j]
u = j (Pick unvisited vertex with minimum distance)
(iii) If u = -1 Then Go to Step 8 (No more reachable vertices)
(iv) Visited[u] = 1 (Mark u as visited)
(v) For v = 0 to N-1:
If Visited[v] = 0 AND G[u][v] ≠ ∞ AND Distance[u] + G[u][v] < Distance[v] Then
Distance[v] = Distance[u] + G[u][v] (Update distance if shorter path found)
Step 7 - i = i + 1
Step 8 - For j = 0 to N-1:
Print "Distance from ", S, " to ", j, " = ", Distance[j]
Step 9 – Exit
6) GRAPH COLORING-
Step 1 - Begin
Step 2 - i = 0 (Start with the first vertex)
Step 3 - Create Color array, set all Color[i] = -1 (uncolored)
Step 4 - Repeat Step 5 & 6 While i < N
Step 5 - (i) Create Available array of size N, set all Available[c] = 1 (all colors available)
(ii) For j = 0 to N-1:
If G[i][j] = 1 AND Color[j] ≠ -1 Then
Available[Color[j]] = 0 (Mark color of adjacent vertex as unavailable)
(iii) c = 0 (Start with smallest color)
(iv) While Available[c] = 0:
c = c + 1 (Find the first available color)
(v) Color[i] = c (Assign the color to vertex i)
(vi) Print "Vertex ", i, " assigned color ", c
Step 6 - i = i + 1
Step 7 – Exit
7) TSP USING GREEDY METHOD-
Step 1 - Begin
Step 2 - i = 0 (Start from vertex 0)
Step 3 - Create Visited array, set Visited[i] = 1 (mark vertex 0 as visited), all others = 0
Step 4 - Tour = [0], TotalDistance = 0, Count = 1 (Tour starts at 0)
Step 5 - Repeat Step 6 & 7 While Count < N
Step 6 - (i) MinDist = ∞, Next = -1
(ii) For j = 0 to N-1:
If Visited[j] = 0 AND G[i][j] < MinDist Then
MinDist = G[i][j]
Next = j (Find nearest unvisited vertex)
(iii) If Next ≠ -1 Then
(a) Tour = Tour + [Next] (Add Next to tour)
(b) TotalDistance = TotalDistance + MinDist
(c) Visited[Next] = 1
(d) i = Next (Move to the next vertex)
(e) Count = Count + 1
Step 7 - If Count = N Then
(i) TotalDistance = TotalDistance + G[i][0] (Return to start)
(ii) Tour = Tour + [0] (Complete the cycle)
Step 8 - Print "Tour: ", Tour
Step 9 - Print "Total distance = ", TotalDistance
Step 10 – Exit
8) TSP USING DYNAMIC PROGRAMMING-
Step 1 - Begin
Step 2 - i = 0 (Start vertex, fixed as 0)
Step 3 - Create DP array of size 2^N by N, set all DP[mask][j] = -1 (uncomputed)
Step 4 - Mask = 1 (Binary 0001, only vertex 0 visited)
Step 5 - Repeat Step 6 & 7 While i < N
Step 6 - If DP[Mask][i] = -1 Then
(i) If Mask = (2^N - 1) Then (All vertices visited)
(a) DP[Mask][i] = G[i][0] (Return to start)
(b) Go to Step 8
(ii) MinCost = ∞
(iii) For j = 0 to N-1:
If (Mask AND (1 << j)) = 0 Then (j is unvisited)
(a) Cost = G[i][j] + TSP(G, N, j, Mask OR (1 << j)) (Visit j next)
(b) If Cost < MinCost Then MinCost = Cost
(iv) DP[Mask][i] = MinCost (Store result)
Step 7 - i = i + 1
Step 8 - Print "Minimum distance = ", DP[1][0] (Mask = 1 means only 0 visited initially)
Step 9 – Exit
9) FLOYD WARSHALL-
Step 1 - Begin
Step 2 - i = 0 (Start index for intermediate vertex)
Step 3 - Create Distance array as a copy of G (N x N matrix)
Step 4 - Repeat Step 5 & 6 While i < N
Step 5 - (i) For u = 0 to N-1:
For v = 0 to N-1:
If Distance[u][i] ≠ ∞ AND Distance[i][v] ≠ ∞ AND Distance[u][i] + Distance[i][v] <
Distance[u][v] Then
Distance[u][v] = Distance[u][i] + Distance[i][v] (Update if shorter path found via i)
Step 6 - i = i + 1
Step 7 - Print "Shortest distances between all pairs:"
Step 8 - For u = 0 to N-1:
For v = 0 to N-1:
Print "Distance from ", u, " to ", v, " = ", Distance[u][v]
Step 9 - Exit
10) N-QUEEN METHOD-
Step 1 - Begin
Step 2 - i = 0 (Start with row 0)
Step 3 - Create Board array of size N, set all Board[i] = -1 (no queen placed)
Step 4 - Repeat Step 5 & 6 While i < N
Step 5 - (i) col = Board[i] + 1 if Board[i] ≠ -1, else col = 0 (Start or continue column search)
(ii) While col < N:
If IsSafe(Board, i, col) Then
(a) Board[i] = col (Place queen)
(b) Go to Step 6 (Move to next row)
Else
col = col + 1 (Try next column)
(iii) If col = N Then
(a) Board[i] = -1 (Reset current row)
(b) If i > 0 Then
i = i - 1 (Backtrack to previous row)
Go to Step 5 (Retry previous row)
(c) Else
Print "No solution exists"
Go to Step 8
Step 6 - i = i + 1 (Move to next row)
Step 7 - Print "Queen positions (row, col):"
Step 8 - For r = 0 to N-1:
Print "(", r, ", ", Board[r], ")"
Step 9 - Exit
11) JOB SEQUENCING-
Step 1 - Begin
Step 2 - i = 0 (Start index for jobs)
Step 3 - Sort J by profit in descending order
Step 4 - MaxDeadline = 0
Step 5 - Repeat Step 6 & 7 While i < N
Step 6 - If J[i][1] > MaxDeadline Then
(i) MaxDeadline = J[i][1] (Update maximum deadline)
Step 7 - i = i + 1
Step 8 - Create Slot array of size MaxDeadline, set all Slot[i] = -1 (no job scheduled)
Step 9 - TotalProfit = 0, i = 0
Step 10 - Repeat Step 11 & 12 While i < N
Step 11 - (i) slot = J[i][1] - 1 (Start from latest slot before deadline)
(ii) While slot >= 0:
If Slot[slot] = -1 Then
(a) Slot[slot] = J[i][0] (Assign job to this slot)
(b) TotalProfit = TotalProfit + J[i][2]
(c) Go to Step 12
Else
slot = slot - 1 (Try earlier slot)
Step 12 - i = i + 1
Step 13 - Print "Scheduled jobs:"
Step 14 - For s = 0 to MaxDeadline - 1:
If Slot[s] ≠ -1 Then Print "Job ", Slot[s]
Step 15 - Print "Total profit = ", TotalProfit
Step 16 – Exit
12) Knuth-Morris-Pratt (KMP) algorithm –
KMP(T,N,P,M)
Where:
T = text array of length N
P = pattern array of length M
Step 1 - begin
Step 2 - i = 0 (position in text)
Step 3 - j = 0 (position in pattern)
Step 4 - Compute LPS array:
(i) lps[0] = 0
(ii) len = 0
(iii) k = 1
(iv) repeat while k < M:
(a) if P[k] = P[len] then
(1) len = len + 1
(2) lps[k] = len
(3) k = k + 1
(b) else
(1) if len ≠ 0 then
(i) len = lps[len - 1]
(2) else
(i) lps[k] = 0
(ii) k = k + 1
Step 5 - repeat step 6 while i < N:
Step 6 - if P[j] = T[i] then
(i) i = i + 1
(ii) j = j + 1
(iii) if j = M then
(a) print "Pattern found at index" (i - j)
(b) j = lps[j - 1]
Step 7 - else if P[j] ≠ T[i] then
(i) if j ≠ 0 then
(a) j = lps[j - 1]
(ii) else
(a) i = i + 1
Step 8 – exit
13) Bellman-Ford algorithm –
BellmanFord(G, V, E, S)
Where:
G = graph with vertices and edges
V = number of vertices
E = array of edges (source, destination, weight)
S = source vertex
Step 1 - begin
Step 2 - initialize distance[V] array
(i) for i = 0 to V-1
(a) distance[i] = infinity
(ii) distance[S] = 0
Step 3 - repeat step 4 for |V|-1 times
Step 4 - for each edge (u, v, w) in E
(i) if distance[u] + w < distance[v] then
(a) distance[v] = distance[u] + w
Step 5 - check for negative-weight cycles
(i) for each edge (u, v, w) in E
(a) if distance[u] + w < distance[v] then
(1) print "Graph contains negative weight cycle"
(2) go to step 7
Step 6 - print distance array as shortest paths from source
Step 7 – exit
14) Ford-Fulkerson algorithm-
FordFulkerson(G, V, S, T)
Where:
G = graph with capacity matrix G[V][V]
V = number of vertices
S = source vertex
T = sink vertex
Step 1 - begin
Step 2 - initialize flow matrix F[V][V] to 0
Step 3 - max_flow = 0
Step 4 - while there exists an augmenting path P from S to T
(i) find residual graph Rf where Rf[u][v] = G[u][v] - F[u][v]
(ii) use BFS or DFS to find path P from S to T in Rf
(iii) if no path exists then
(a) go to step 6
(iv) find bottleneck capacity (min residual capacity) in path P
(a) flow = minimum Rf[u][v] for all (u,v) in path P
(v) for each edge (u,v) in path P
(a) F[u][v] = F[u][v] + flow
(b) F[v][u] = F[v][u] - flow (reverse edge)
(vi) max_flow = max_flow + flow
Step 5 - repeat step 4
Step 6 - print "Maximum flow = " max_flow
Step 7 – exit
15) BFS-
BFS(G, V, S)
Where:
G = graph (adjacency list or matrix)
V = number of vertices
S = source vertex
Step 1 - begin
Step 2 - create queue Q
Step 3 - create visited array VISITED[V], set all to false
Step 4 - VISITED[S] = true
Step 5 - enqueue S into Q
Step 6 - repeat step 7 while Q is not empty
Step 7 -
(i) u = dequeue from Q
(ii) print u (or process vertex u)
(iii) for each vertex v adjacent to u
(a) if VISITED[v] = false then
(1) VISITED[v] = true
(2) enqueue v into Q
Step 8 – exit
16) DFS-
DFS(G, V, S)
Where:
G = graph (adjacency list or matrix)
V = number of vertices
S = source vertex
Step 1 - begin
Step 2 - create visited array VISITED[V], set all to false
Step 3 - call DFS-Visit(S)
Step 4 - procedure DFS-Visit(u):
(i) VISITED[u] = true true
(ii) print u (or process vertex u)
(iii) for each vertex v adjacent to u
(a) if VISITED[v] = false then
(1) call DFS-Visit(v)
Step 5 – exit
17) Bubble sort-
BubbleSort(LA, N)
Where:
LA = linear array to be sorted
N = number of elements in array
Step 1 - begin
Step 2 - i = 0
Step 3 - repeat step 4 while i < N-1
Step 4 -
(i) j = 0
(ii) repeat step (iii) while j < N-1-i
(iii) if LA[j] > LA[j+1] then
(a) swap LA[j] and LA[j+1]
(iv) j = j + 1
Step 5 - i = i + 1
Step 6 - print "Array is sorted"
Step 7 – exit
18) Insertion sort-
InsertionSort(LA, N)
Where:
LA = linear array to be sorted
N = number of elements in array
Step 1 - begin
Step 2 - i = 1
Step 3 - repeat step 4 while i < N
Step 4 -
(i) key = LA[i]
(ii) j = i - 1
(iii) repeat step (iv) while j >= 0 AND LA[j] > key
(iv)
(a) LA[j + 1] = LA[j]
(b) j = j - 1
(v) LA[j + 1] = key
Step 5 - i = i + 1
Step 6 - print "Array is sorted"
Step 7 – exit
19) Selection sort-
SelectionSort(LA, N)
Where:
LA = linear array to be sorted
N = number of elements in array
Step 1 - begin
Step 2 - i = 0
Step 3 - repeat step 4 while i < N-1
Step 4 -
(i) min_idx = i
(ii) j = i + 1
(iii) repeat step (iv) while j < N
(iv) if LA[j] < LA[min_idx] then
(a) min_idx = j
(v) j = j + 1
(vi) if min_idx ≠ i then
(a) swap LA[i] and LA[min_idx]
Step 5 - i = i + 1
Step 6 - print "Array is sorted"
Step 7 – exit
20) Merge sort-
MergeSort(LA, N)
Where:
LA = linear array to be sorted
N = number of elements in array
Step 1 - begin
Step 2 - if N <= 1 then
(i) go to step 7
Step 3 - mid = N / 2
Step 4 -
(i) L = left half of LA from 0 to mid-1
(ii) R = right half of LA from mid to N-1
(iii) call MergeSort(L, mid)
(iv) call MergeSort(R, N - mid)
Step 5 - merge procedure:
(i) i = 0 (index for L)
(ii) j = 0 (index for R)
(iii) k = 0 (index for LA)
(iv) repeat while i < mid AND j < N-mid
(a) if L[i] <= R[j] then
(1) LA[k] = L[i]
(2) i = i + 1
(b) else
(1) LA[k] = R[j]
(2) j = j + 1
(c) k = k + 1
(v) while i < mid
(a) LA[k] = L[i]
(b) i = i + 1
(c) k = k + 1
(vi) while j < N-mid
(a) LA[k] = R[j]
(b) j = j + 1
(c) k = k + 1
Step 6 - print "Array is sorted"
Step 7 – exit
21) Quick sort-
QuickSort(LA, N)
Where:
LA = linear array to be sorted
N = number of elements in array
Step 1 - begin
Step 2 - if N <= 1 then
(i) go to step 7
Step 3 - call QuickSortProcedure(LA, 0, N-1)
Step 4 - procedure QuickSortProcedure(LA, low, high):
(i) if low < high then
(a) pivot_idx = call Partition(LA, low, high)
(b) call QuickSortProcedure(LA, low, pivot_idx - 1)
(c) call QuickSortProcedure(LA, pivot_idx + 1, high)
Step 5 - procedure Partition(LA, low, high):
(i) pivot = LA[high]
(ii) i = low - 1
(iii) j = low
(iv) repeat while j < high
(a) if LA[j] <= pivot then
(1) i = i + 1
(2) swap LA[i] and LA[j]
(b) j = j + 1
(v) swap LA[i + 1] and LA[high]
(vi) return i + 1
Step 6 - print "Array is sorted"
Step 7 - exit
