1

1. Bubble Sort

Source Code:
# Python program for implementation of Bubble Sort

def bubbleSort(arr):
n = len(arr)

# Traverse through all array elements

for i in range(n):

# Last i elements are already in place

for j in range(0, n-i-1):

# traverse the array from 0 to n-i-1

# Swap if the element found is greater
# than the next element
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]

# Driver code to test above

arr = [64, 34, 25, 12, 22, 11, 90]

bubbleSort(arr)

print ("Sorted array is:")

for i in range(len(arr)):
print ("%d" %arr[i]),

Output :

Prabin Karki
 2

2. Selection Sort

Source Code:

# Python program for implementation of Selection

# Sort
import sys
A = [64, 25, 12, 22, 11]

# Traverse through all array elements

for i in range(len(A)):

# Find the minimum element in remaining

# unsorted array
min_idx = i
for j in range(i+1, len(A)):
if A[min_idx] > A[j]:
min_idx = j

# Swap the found minimum element with

# the first element
A[i], A[min_idx] = A[min_idx], A[i]

# Driver code to test above

print ("Sorted array")
for i in range(len(A)):
print("%d" %A[i]),

Output :

Prabin Karki
 3

3. Insertion Sort

Source Code:

# Python program for implementation of Insertion Sort

# Function to do insertion sort

def insertionSort(arr):

# Traverse through 1 to len(arr)

for i in range(1, len(arr)):

key = arr[i]

# Move elements of arr[0..i-1], that are

# greater than key, to one position ahead
# of their current position
j = i-1
while j >= 0 and key < arr[j] :
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key

# Driver code to test above

arr = [12, 11, 13, 5, 6]
insertionSort(arr)
for i in range(len(arr)):
print ("% d" % arr[i])

Output :

Prabin Karki
 4

4. Sequential/Linear Search

Source Code:

# Python3 code to linearly search x in arr[].

# If x is present then return its location,
# otherwise return -1

def search(arr, n, x):

for i in range(0, n):

if (arr[i] == x):
return i
return -1
# Driver Code
arr = [2, 3, 4, 10, 40]
x = 10
n = len(arr)

# Function call
result = search(arr, n, x)
if(result == -1):
print("Element is not present in array")
else:
print("Element is present at index", result)

Output :

Prabin Karki
 5

5. Merge Sort

Source Code:

# Python program for implementation of MergeSort

def mergeSort(arr):
if len(arr) > 1:

# Finding the mid of the array

mid = len(arr)//2

# Dividing the array elements

L = arr[:mid]

# into 2 halves
R = arr[mid:]

# Sorting the first half

mergeSort(L)

# Sorting the second half

mergeSort(R)

i=j=k=0

# Copy data to temp arrays L[] and R[]

while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1

Prabin Karki
 6

# Checking if any element was left

while i < len(L):
arr[k] = L[i]
i += 1
k += 1

while j < len(R):

arr[k] = R[j]
j += 1
k += 1

# Code to print the list

def printList(arr):
for i in range(len(arr)):
print(arr[i], end=" ")
print()
# Driver Code
if __name__ == '__main__':
arr = [12, 11, 13, 5, 6, 7]
print("Given array is", end="\n")
printList(arr)
mergeSort(arr)
print("Sorted array is: ", end="\n")
printList(arr)

Output :

Prabin Karki
 7

6. Quick Sort

Source Code:

# Python program for implementation of Quicksort Sort

# This function takes last element as pivot, places

# the pivot element at its correct position in sorted
# array, and places all smaller (smaller than pivot)
# to left of pivot and all greater elements to right
# of pivot
def partition(arr,low,high):
i = ( low-1 ) # index of smaller element
pivot = arr[high] # pivot

for j in range(low , high):

# If current element is smaller than the pivot

if arr[j] < pivot:

# increment index of smaller element

i = i+1
arr[i],arr[j] = arr[j],arr[i]

arr[i+1],arr[high] = arr[high],arr[i+1]
return ( i+1 )

# The main function that implements QuickSort

# arr[] --> Array to be sorted,
# low --> Starting index,
# high --> Ending index

# Function to do Quick sort

def quickSort(arr,low,high):

Prabin Karki
 8

if low < high:

# pi is partitioning index, arr[p] is now

# at right place
pi = partition(arr,low,high)

# Separately sort elements before

# partition and after partition
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)

# Driver code to test above

arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr,0,n-1)
print ("Sorted array is:")
for i in range(n):
print ("%d" %arr[i]),

Output :

Prabin Karki
 9

7. Heap Sort

Source Code :

# Python program for implementation of Quicksort Sort

# This function takes last element as pivot, places

# the pivot element at its correct position in sorted
# array, and places all smaller (smaller than pivot)
# to left of pivot and all greater elements to right
# of pivot

def partition(arr,low,high):
i = ( low-1 ) # index of smaller element
pivot = arr[high] # pivot

for j in range(low , high):

# If current element is smaller than the pivot

if arr[j] < pivot:

# increment index of smaller element

i = i+1
arr[i],arr[j] = arr[j],arr[i]

arr[i+1],arr[high] = arr[high],arr[i+1]
return ( i+1 )

# The main function that implements QuickSort

# arr[] --> Array to be sorted,
# low --> Starting index,
# high --> Ending index

# Function to do Quick sort

Prabin Karki
 10

def quickSort(arr,low,high):
if low < high:

# pi is partitioning index, arr[p] is now

# at right place

pi = partition(arr,low,high)

# Separately sort elements before

# partition and after partition
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)

# Driver code to test above

arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr,0,n-1)
print ("Sorted array is:")
for i in range(n):
print ("%d" %arr[i]),

Output :

Prabin Karki
 11

8. Selection in Expected Linear Time

Source Code :
# Python program for implementation of heap Sort

# To heapify subtree rooted at index i.

# n is size of heap

def heapify(arr, n, i):

largest = i # Initialize largest as root
l=2*i+1 # left = 2*i + 1
r=2*i+2 # right = 2*i + 2

# See if left child of root exists and is

# greater than root
if l < n and arr[largest] < arr[l]:
largest = l

# See if right child of root exists and is

# greater than root
if r < n and arr[largest] < arr[r]:
largest = r

# Change root, if needed

if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # swap

# Heapify the root.

heapify(arr, n, largest)

# The main function to sort an array of given size

Prabin Karki
 12

def heapSort(arr):
n = len(arr)

# Build a maxheap.
for i in range(n//2 - 1, -1, -1):
heapify(arr, n, i)

# One by one extract elements

for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # swap
heapify(arr, i, 0)

# Driver code
arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
print("%d" % arr[i]),

Output :

Prabin Karki
 13

9. Selection in Worst Case Linear Time

Source Code :
# Python3 implementation of randomized
# quickSelect
import random

# This function returns k'th smallest

# element in arr[l..r] using QuickSort
# based method. ASSUMPTION: ELEMENTS
# IN ARR[] ARE DISTINCT
def kthSmallest(arr, l, r, k):

# If k is smaller than number of

# elements in array
if (k > 0 and k <= r - l + 1):

# Partition the array around a random

# element and get position of pivot
# element in sorted array
pos = randomPartition(arr, l, r)

# If position is same as k
if (pos - l == k - 1):
return arr[pos]
if (pos - l > k - 1): # If position is more,
# recur for left subarray
return kthSmallest(arr, l, pos - 1, k)

# Else recur for right subarray

return kthSmallest(arr, pos + 1, r,
k - pos + l - 1)

# If k is more than the number of

Prabin Karki
 14

# elements in the array

return 999999999999

def swap(arr, a, b):

temp = arr[a]
arr[a] = arr[b]
arr[b] = temp

# Standard partition process of QuickSort().

# It considers the last element as pivot and
# moves all smaller element to left of it and
# greater elements to right. This function
# is used by randomPartition()
def partition(arr, l, r):
x = arr[r]
i=l
for j in range(l, r):
if (arr[j] <= x):
swap(arr, i, j)
i += 1
swap(arr, i, r)
return i

# Picks a random pivot element between l and r

# and partitions arr[l..r] around the randomly
# picked element using partition()
def randomPartition(arr, l, r):
n=r-l+1
pivot = int([Link]() % n)
swap(arr, l + pivot, r)
return partition(arr, l, r)

# Driver Code
if __name__ == '__main__':

Prabin Karki
 15

arr = [12, 3, 5, 7, 4, 19, 26]

n = len(arr)
k=3
print("K'th smallest element is",
kthSmallest(arr, 0, n - 1, k))

Prabin Karki
 16

10. Job Sequencing Problem

Source Code :

# Program to find the maximum profit

# job sequence from a given array
# of jobs with deadlines and profits

# function to schedule the jobs take 2

# arguments array and no of jobs to schedule

def printJobScheduling(arr, t):

# length of array
n = len(arr)

# Sort all jobs according to

# decreasing order of profit
for i in range(n):
for j in range(n - 1 - i):
if arr[j][2] < arr[j + 1][2]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]

# To keep track of free time slots

result = [False] * t

# To store result (Sequence of jobs)

job = ['-1'] * t

# Iterate through all given jobs

for i in range(len(arr)):

# Find a free slot for this job

Prabin Karki
 17

# (Note that we start from the

# last possible slot)
for j in range(min(t - 1, arr[i][1] - 1), -1, -1):

# Free slot found

if result[j] is False:
result[j] = True
job[j] = arr[i][0]
break

# print the sequence

print(job)

# Driver COde
arr = [['a', 2, 100], # Job Array
['b', 1, 19],
['c', 2, 27],
['d', 1, 25],
['e', 3, 15]]

print("Following is maximum profit sequence of jobs")

# Function Call
printJobScheduling(arr, 3)

Output :

Prabin Karki
 18

11. Prim’s Algorithm

Source Code :

# A Python program for Prim's Minimum Spanning Tree (MST) algorithm.

# The program is for adjacency matrix representation of the graph

import sys # Library for INT_MAX

class Graph():

def __init__(self, vertices):

self.V = vertices
[Link] = [[0 for column in range(vertices)]
for row in range(vertices)]

# A utility function to print the constructed MST stored in parent[]

def printMST(self, parent):
print "Edge \tWeight"
for i in range(1, self.V):
print parent[i], "-", i, "\t", [Link][i][ parent[i] ]

# A utility function to find the vertex with

# minimum distance value, from the set of vertices
# not yet included in shortest path tree
def minKey(self, key, mstSet):

# Initilaize min value

min = [Link]

for v in range(self.V):
if key[v] < min and mstSet[v] == False:

Prabin Karki
 19

min = key[v]
min_index = v

return min_index

# Function to construct and print MST for a graph

# represented using adjacency matrix representation
def primMST(self):

# Key values used to pick minimum weight edge in cut

key = [[Link]] * self.V
parent = [None] * self.V # Array to store constructed MST
# Make key 0 so that this vertex is picked as first vertex
key[0] = 0
mstSet = [False] * self.V

parent[0] = -1 # First node is always the root of

for cout in range(self.V):

# Pick the minimum distance vertex from

# the set of vertices not yet processed.
# u is always equal to src in first iteration
u = [Link](key, mstSet)

# Put the minimum distance vertex in

# the shortest path tree
mstSet[u] = True

# Update dist value of the adjacent vertices

# of the picked vertex only if the current
# distance is greater than new distance and
# the vertex in not in the shotest path tree
for v in range(self.V):

Prabin Karki
 20

# graph[u][v] is non zero only for adjacent vertices of m

# mstSet[v] is false for vertices not yet included in MST
# Update the key only if graph[u][v] is smaller than key[v]
if [Link][u][v] > 0 and mstSet[v] == False and key[v] > [Link][u][v]:
key[v] = [Link][u][v]
parent[v] = u

[Link](parent)

g = Graph(5)
[Link] = [ [0, 2, 0, 6, 0],
[2, 0, 3, 8, 5],
[0, 3, 0, 0, 7],
[6, 8, 0, 0, 9],
[0, 5, 7, 9, 0]]

[Link]();

Output :

Prabin Karki
 21

12. Dijkstra’s Algorithm

Source Code :

# Python program for Dijkstra's single

# source shortest path algorithm. The program is
# for adjacency matrix representation of the graph

# Library for INT_MAX

import sys

class Graph():

def __init__(self, vertices):

self.V = vertices
[Link] = [[0 for column in range(vertices)]
for row in range(vertices)]

def printSolution(self, dist):

print "Vertex \tDistance from Source"
for node in range(self.V):
print node, "\t", dist[node]

# A utility function to find the vertex with

# minimum distance value, from the set of vertices
# not yet included in shortest path tree
def minDistance(self, dist, sptSet):

# Initilaize minimum distance for next node

min = [Link]

# Search not nearest vertex not in the

# shortest path tree

Prabin Karki
 22

for v in range(self.V):
if dist[v] < min and sptSet[v] == False:
min = dist[v]
min_index = v

return min_index

# Funtion that implements Dijkstra's single source

# shortest path algorithm for a graph represented
# using adjacency matrix representation
def dijkstra(self, src):

dist = [[Link]] * self.V

dist[src] = 0
sptSet = [False] * self.V

for cout in range(self.V):

# Pick the minimum distance vertex from

# the set of vertices not yet processed.
# u is always equal to src in first iteration
u = [Link](dist, sptSet)

# Put the minimum distance vertex in the

# shotest path tree
sptSet[u] = True

# Update dist value of the adjacent vertices

# of the picked vertex only if the current
# distance is greater than new distance and
# the vertex in not in the shotest path tree
for v in range(self.V):
if [Link][u][v] > 0 and sptSet[v] == False and \
dist[v] > dist[u] + [Link][u][v]:

Prabin Karki
 23

dist[v] = dist[u] + [Link][u][v]

[Link](dist)

# Driver program
g = Graph(9)
[Link] = [[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]
];

[Link](0);

Output :

Prabin Karki
 24

13. Huffman Coding

Source Code :
// C program for Huffman Coding
#include <stdio.h>
#include <stdlib.h>

// This constant can be avoided by explicitly

// calculating height of Huffman Tree
#define MAX_TREE_HT 100

// A Huffman tree node

struct MinHeapNode {

// One of the input characters

char data;

// Frequency of the character

unsigned freq;

// Left and right child of this node

struct MinHeapNode *left, *right;
};

// A Min Heap: Collection of

// min-heap (or Huffman tree) nodes
struct MinHeap {

// Current size of min heap

unsigned size;

// capacity of min heap

unsigned capacity;

Prabin Karki
 25

// Array of minheap node pointers

struct MinHeapNode** array;
};

// A utility function allocate a new

// min heap node with given character
// and frequency of the character
struct MinHeapNode* newNode(char data, unsigned freq)
{
struct MinHeapNode* temp
= (struct MinHeapNode*)malloc
(sizeof(struct MinHeapNode));

temp->left = temp->right = NULL;

temp->data = data;
temp->freq = freq;

return temp;
}

// A utility function to create

// a min heap of given capacity
struct MinHeap* createMinHeap(unsigned capacity)

struct MinHeap* minHeap

= (struct MinHeap*)malloc(sizeof(struct MinHeap));

// current size is 0
minHeap->size = 0;

minHeap->capacity = capacity;

Prabin Karki
 26

minHeap->array
= (struct MinHeapNode**)malloc(minHeap->
capacity * sizeof(struct MinHeapNode*));
return minHeap;
}

// A utility function to
// swap two min heap nodes
void swapMinHeapNode(struct MinHeapNode** a,
struct MinHeapNode** b)

struct MinHeapNode* t = *a;

*a = *b;
*b = t;
}

// The standard minHeapify function.

void minHeapify(struct MinHeap* minHeap, int idx)

int smallest = idx;

int left = 2 * idx + 1;
int right = 2 * idx + 2;

if (left < minHeap->size && minHeap->array[left]->

freq < minHeap->array[smallest]->freq)
smallest = left;

if (right < minHeap->size && minHeap->array[right]->

freq < minHeap->array[smallest]->freq)
smallest = right;

Prabin Karki
 27

if (smallest != idx) {
swapMinHeapNode(&minHeap->array[smallest],
&minHeap->array[idx]);
minHeapify(minHeap, smallest);
}
}

// A utility function to check

// if size of heap is 1 or not
int isSizeOne(struct MinHeap* minHeap)
{

return (minHeap->size == 1);

}

// A standard function to extract

// minimum value node from heap
struct MinHeapNode* extractMin(struct MinHeap* minHeap)

struct MinHeapNode* temp = minHeap->array[0];

minHeap->array[0]
= minHeap->array[minHeap->size - 1];

--minHeap->size;
minHeapify(minHeap, 0);

return temp;
}

// A utility function to insert

// a new node to Min Heap

Prabin Karki
 28

void insertMinHeap(struct MinHeap* minHeap,

struct MinHeapNode* minHeapNode)

++minHeap->size;
int i = minHeap->size - 1;

while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) {

minHeap->array[i] = minHeap->array[(i - 1) / 2];

i = (i - 1) / 2;
}

minHeap->array[i] = minHeapNode;
}

// A standard function to build min heap

void buildMinHeap(struct MinHeap* minHeap)

int n = minHeap->size - 1;
int i;

for (i = (n - 1) / 2; i >= 0; --i)

minHeapify(minHeap, i);
}

// A utility function to print an array of size n

void printArr(int arr[], int n)
{
int i;
for (i = 0; i < n; ++i)

Prabin Karki
 29

printf("%d", arr[i]);

printf("\n");
}

// Utility function to check if this node is leaf

int isLeaf(struct MinHeapNode* root)

return !(root->left) && !(root->right);

}

// Creates a min heap of capacity

// equal to size and inserts all character of
// data[] in min heap. Initially size of
// min heap is equal to capacity
struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size)

struct MinHeap* minHeap = createMinHeap(size);

for (int i = 0; i < size; ++i)

minHeap->array[i] = newNode(data[i], freq[i]);

minHeap->size = size;
buildMinHeap(minHeap);

return minHeap;
}

// The main function that builds Huffman tree

struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size)

Prabin Karki
 30

{
struct MinHeapNode *left, *right, *top;

// Step 1: Create a min heap of capacity

// equal to size. Initially, there are
// modes equal to size.
struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size);

// Iterate while size of heap doesn't become 1

while (!isSizeOne(minHeap)) {

// Step 2: Extract the two minimum

// freq items from min heap
left = extractMin(minHeap);
right = extractMin(minHeap);

// Step 3: Create a new internal

// node with frequency equal to the
// sum of the two nodes frequencies.
// Make the two extracted node as
// left and right children of this new node.
// Add this node to the min heap
// '$' is a special value for internal nodes, not used
top = newNode('$', left->freq + right->freq);

top->left = left;
top->right = right;

insertMinHeap(minHeap, top);
}

// Step 4: The remaining node is the

// root node and the tree is complete.

Prabin Karki
 31

return extractMin(minHeap);
}

// Prints huffman codes from the root of Huffman Tree.

// It uses arr[] to store codes
void printCodes(struct MinHeapNode* root, int arr[], int top)

// Assign 0 to left edge and recur

if (root->left) {

arr[top] = 0;
printCodes(root->left, arr, top + 1);
}

// Assign 1 to right edge and recur

if (root->right) {

arr[top] = 1;
printCodes(root->right, arr, top + 1);
}

// If this is a leaf node, then

// it contains one of the input
// characters, print the character
// and its code from arr[]
if (isLeaf(root)) {

printf("%c: ", root->data);

printArr(arr, top);
}
}

Prabin Karki
 32

// The main function that builds a

// Huffman Tree and print codes by traversing
// the built Huffman Tree
void HuffmanCodes(char data[], int freq[], int size)

{
// Construct Huffman Tree
struct MinHeapNode* root
= buildHuffmanTree(data, freq, size);

// Print Huffman codes using

// the Huffman tree built above
int arr[MAX_TREE_HT], top = 0;

printCodes(root, arr, top);

}

// Driver program to test above functions

int main()
{

char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' };

int freq[] = { 5, 9, 12, 13, 16, 45 };

int size = sizeof(arr) / sizeof(arr[0]);

HuffmanCodes(arr, freq, size);

return 0;
}

Prabin Karki
 33

Output :

Prabin Karki
 34

14. Matrix Chain Multiplication

Source Code :

# A naive recursive implementation that

# simply follows the above optimal
# substructure property
import sys

# Matrix A[i] has dimension p[i-1] x p[i]

# for i = 1..n

def MatrixChainOrder(p, i, j):

if i == j:
return 0

_min = [Link]

# place parenthesis at different places

# between first and last matrix,
# recursively calculate count of
# multiplications for each parenthesis
# placement and return the minimum count
for k in range(i, j):

count = (MatrixChainOrder(p, i, k)
+ MatrixChainOrder(p, k + 1, j)
+ p[i-1] * p[k] * p[j])

if count < _min:

_min = count

Prabin Karki
 35

# Return minimum count

return _min

# Driver code
arr = [1, 2, 3, 4, 3]
n = len(arr)

print("Minimum number of multiplications is ",

MatrixChainOrder(arr, 1, n-1))

Output :

Prabin Karki
 36

15. String Editing (Edit Distance)

Source Code :

# A Naive recursive Python program to fin minimum number

# operations to convert str1 to str2

def editDistance(str1, str2, m, n):

# If first string is empty, the only option is to

# insert all characters of second string into first
if m == 0:
return n

# If second string is empty, the only option is to

# remove all characters of first string
if n == 0:
return m

# If last characters of two strings are same, nothing

# much to do. Ignore last characters and get count for
# remaining strings.
if str1[m-1] == str2[n-1]:
return editDistance(str1, str2, m-1, n-1)

# If last characters are not same, consider all three

# operations on last character of first string, recursively
# compute minimum cost for all three operations and take
# minimum of three values.
return 1 + min(editDistance(str1, str2, m, n-1), # Insert
editDistance(str1, str2, m-1, n), # Remove
editDistance(str1, str2, m-1, n-1) # Replace
)

Prabin Karki
 37

# Driver code
str1 = "sunday"
str2 = "saturday"
print editDistance(str1, str2, len(str1), len(str2))

Output :

Prabin Karki
 38

16. Zero-One Knapsack Problem (Dynamic Programming)

Source Code :

# Python3 program to print Vertex Cover

# of a given undirected graph
from collections import defaultdict

# This class represents a directed graph

# using adjacency list representation
class Graph:

def __init__(self, vertices):

# No. of vertices
self.V = vertices

# Default dictionary to store graph

[Link] = defaultdict(list)

# Function to add an edge to graph

def addEdge(self, u, v):
[Link][u].append(v)

# The function to print vertex cover

def printVertexCover(self):

# Initialize all vertices as not visited.

visited = [False] * (self.V)

# Consider all edges one by one

for u in range(self.V):

# An edge is only picked when

Prabin Karki
 39

# both visited[u] and visited[v]

# are false
if not visited[u]:

# Go through all adjacents of u and

# pick the first not yet visited
# vertex (We are basically picking
# an edge (u, v) from remaining edges.
for v in [Link][u]:
if not visited[v]:

# Add the vertices (u, v) to the

# result set. We make the vertex
# u and v visited so that all
# edges from/to them would
# be ignored
visited[v] = True
visited[u] = True
break

# Print the vertex cover

for j in range(self.V):
if visited[j]:
print(j, end = ' ')

print()

# Driver code

# Create a graph given in

# the above diagram
g = Graph(7)
[Link](0, 1)
[Link](0, 2)

Prabin Karki
 40

[Link](1, 3)
[Link](3, 4)
[Link](4, 5)
[Link](5, 6)

[Link]()

Output :

Prabin Karki
 41

17. Floyd Warshall Algorithm

Source Code :

# Python Program for Floyd Warshall Algorithm

# Number of vertices in the graph

V=4

# Define infinity as the large

# enough value. This value will be
# used for vertices not connected to each other
INF = 99999

# Solves all pair shortest path

# via Floyd Warshall Algorithm

def floydWarshall(graph):

""" dist[][] will be the output

matrix that will finally
have the shortest distances
between every pair of vertices """
""" initializing the solution matrix
same as input graph matrix
OR we can say that the initial
values of shortest distances
are based on shortest paths considering no
intermediate vertices """

dist = list(map(lambda i: list(map(lambda j: j, i)), graph))

""" Add all vertices one by one

Prabin Karki
 42

to the set of intermediate

vertices.
---> Before start of an iteration,
we have shortest distances
between all pairs of vertices
such that the shortest
distances consider only the
vertices in the set
{0, 1, 2, .. k-1} as intermediate vertices.
----> After the end of a
iteration, vertex no. k is
added to the set of intermediate
vertices and the
set becomes {0, 1, 2, .. k}
"""
for k in range(V):

# pick all vertices as source one by one

for i in range(V):

# Pick all vertices as destination for the

# above picked source
for j in range(V):

# If vertex k is on the shortest path from

# i to j, then update the value of dist[i][j]
dist[i][j] = min(dist[i][j],
dist[i][k] + dist[k][j]
)
printSolution(dist)

# A utility function to print the solution

def printSolution(dist):

Prabin Karki
 43

print "Following matrix shows the shortest distances\

between every pair of vertices"
for i in range(V):
for j in range(V):
if(dist[i][j] == INF):
print "%7s" % ("INF"),
else:
print "%7d\t" % (dist[i][j]),
if j == V-1:
print ""

# Driver program to test the above program

graph = [[0, 5, INF, 10],
[INF, 0, 3, INF],
[INF, INF, 0, 1],
[INF, INF, INF, 0]
]
# Print the solution
floydWarshall(graph)

Output :

Prabin Karki
 44

18. Subset-Sum Problem (Backtracking)

Source Code :

#include <bits/stdc++.h>
using namespace std;
#define ARRAYSIZE(a) (sizeof(a)) / (sizeof(a[0]))
#define mx 200

static int total_nodes;

// Prints subset found

void printSubset(int A[], int size)
{
for(int i = 0; i < size; i++)
{
cout << A[i] << " ";
}
cout << "n ";
}

// inputs
// s - set vector
// t - tuplet vector
// s_size - set size
// t_size - tuplet size so far
// sum - sum so far
// ite - nodes count
// target_sum - sum to be found
void subset_sum(int s[], int t[],
int s_size, int t_size,
int sum, int ite,
int const target_sum)

Prabin Karki
 45

{
total_nodes++;

if (target_sum == sum )
{

// We found subset
printSubset(t, t_size);

// Exclude previously added item

// and consider next candidate
subset_sum(s, t, s_size, t_size - 1,
sum - s[ite], ite + 1,
target_sum);
return;
}
else
{

// Generate nodes along the breadth

for(int i = ite; i < s_size; i++)
{
t[t_size] = s[i];

// Consider next level node (along depth)

subset_sum(s, t, s_size, t_size + 1,
sum + s[i], i + 1, target_sum);
}
}
}

// Wrapper to print subsets that sum to target_sum

// input is weights vector and target_sum
void generateSubsets(int s[], int size,

Prabin Karki
 46

int target_sum)
{
int *tuplet_vector = new int[mx];

subset_sum(s, tuplet_vector, size,

0, 0, 0, target_sum);

free(tuplet_vector);
}

// Driver Code
int main()
{
int weights[] = { 10, 7, 5, 18, 12, 20, 15 };
int size = ARRAYSIZE(weights);

generateSubsets(weights, size, 35);

cout << "Nodes generated " << total_nodes << "n";

return 0;
}

Output :

Prabin Karki
 47

19. 0-1 Knapsack (Backtracking)

Source Code :

# A naive recursive implementation

# of 0-1 Knapsack Problem

# Returns the maximum value that

# can be put in a knapsack of
# capacity W

def knapSack(W, wt, val, n):

# Base Case
if n == 0 or W == 0:
return 0

# If weight of the nth item is

# more than Knapsack of capacity W,
# then this item cannot be included
# in the optimal solution
if (wt[n-1] > W):
return knapSack(W, wt, val, n-1)

# return the maximum of two cases:

# (1) nth item included
# (2) not included
else:
return max(
val[n-1] + knapSack(
W-wt[n-1], wt, val, n-1),
knapSack(W, wt, val, n-1))

Prabin Karki
 48

# end of function knapSack

#Driver Code
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print knapSack(W, wt, val, n)

Output :

Prabin Karki
 49

20. N-Queens Problem

Source Code :

# Python program to solve N Queen

# Problem using backtracking

global N
N=4

def printSolution(board):
for i in range(N):
for j in range(N):
print board[i][j],
print

# A utility function to check if a queen can

# be placed on board[row][col]. Note that this
# function is called when "col" queens are
# already placed in columns from 0 to col -1.
# So we need to check only left side for
# attacking queens
def isSafe(board, row, col):

# Check this row on left side

for i in range(col):
if board[row][i] == 1:
return False

# Check upper diagonal on left side

for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False

Prabin Karki
 50

# Check lower diagonal on left side

for i, j in zip(range(row, N, 1), range(col, -1, -1)):
if board[i][j] == 1:
return False

return True

def solveNQUtil(board, col):

# base case: If all queens are placed
# then return true
if col >= N:
return True

# Consider this column and try placing

# this queen in all rows one by one
for i in range(N):

if isSafe(board, i, col):
# Place this queen in board[i][col]
board[i][col] = 1

# recur to place rest of the queens

if solveNQUtil(board, col + 1) == True:
return True

# If placing queen in board[i][col

# doesn't lead to a solution, then
# queen from board[i][col]
board[i][col] = 0

# if the queen can not be placed in any row in

# this colum col then return false
return False

Prabin Karki
 51

# This function solves the N Queen problem using

# Backtracking. It mainly uses solveNQUtil() to
# solve the problem. It returns false if queens
# cannot be placed, otherwise return true and
# placement of queens in the form of 1s.
# note that there may be more than one
# solutions, this function prints one of the
# feasible solutions.
def solveNQ():
board = [ [0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]

if solveNQUtil(board, 0) == False:
print "Solution does not exist"
return False

printSolution(board)
return True

# driver program to test above function

solveNQ()
Output :

Prabin Karki
 52

21. Vertex Cover Problem (Approximate Algorithm)

Source Code :

# Python3 program to print Vertex Cover

# of a given undirected graph
from collections import defaultdict

# This class represents a directed graph

# using adjacency list representation
class Graph:

def __init__(self, vertices):

# No. of vertices
self.V = vertices

# Default dictionary to store graph

[Link] = defaultdict(list)

# Function to add an edge to graph

def addEdge(self, u, v):
[Link][u].append(v)

# The function to print vertex cover

def printVertexCover(self):

# Initialize all vertices as not visited.

visited = [False] * (self.V)

# Consider all edges one by one

Prabin Karki
 53

for u in range(self.V):

# An edge is only picked when

# both visited[u] and visited[v]
# are false
if not visited[u]:

# Go through all adjacents of u and

# pick the first not yet visited
# vertex (We are basically picking
# an edge (u, v) from remaining edges.
for v in [Link][u]:
if not visited[v]:

# Add the vertices (u, v) to the

# result set. We make the vertex
# u and v visited so that all
# edges from/to them would
# be ignored
visited[v] = True
visited[u] = True
break

# Print the vertex cover

for j in range(self.V):
if visited[j]:
print(j, end = ' ')

print()

# Driver code

# Create a graph given in

# the above diagram

Prabin Karki
 54

g = Graph(7)
[Link](0, 1)
[Link](0, 2)
[Link](1, 3)
[Link](3, 4)
[Link](4, 5)
[Link](5, 6)

[Link]()

Output :

Prabin Karki