code

1.Tower of Hanoi

def TOH(n,A,B,C):
    if n>0:
        TOH(n-1,A,C,B)
        print('Moved disk',n,'from',A,'to',C)
        TOH(n-1,B,A,C)
n=int(input("Enter How many disk:"))
TOH(n,'A','B','C')

2.kruskal

# Write a program to find the shortest path from a graph using Kruskal’s Algorithm.

from collections import defaultdict
# Part of Cosmos by OpenGenus Foundation
class Graph:
    def __init__(self,vertices):
        self.V= vertices
        self.graph = []
    def addEdge(self,u,v,w):
        self.graph.append([u,v,w])
    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])
    def union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)
        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else :
            parent[yroot] = xroot
            rank[xroot] += 1
    def KruskalMST(self):
        result =[]
        i,e = 0,0
        self.graph =  sorted(self.graph,key=lambda item: item[2])
        parent = [] ; rank = []
        for node in range(self.V):
            parent.append(node)
            rank.append(0)
        while e < self.V -1 :
            u,v,w =  self.graph[i]
            i = i + 1
            x = self.find(parent, u)
            y = self.find(parent ,v)
            if x != y:
                e = e + 1
                result.append([u,v,w])
                self.union(parent, rank, x, y)
        print("Constructed MST :")
        print("Vertex A    Vertex B  Weight")
        for u,v,weight  in result:
            print ("    %d          %d        %d" % (u,v,weight))
vetx = int(input("Enter no. of vertices :"))
eegde = int(input("Enter no. of edges :"))
g = Graph(vetx)
print("For each edge input (Source vertex , Destination vertex , Weight of the edge ) :")
for x in range(eegde):
    qq,xx,yy = map(int,input().split(" "))
    g.addEdge(qq, xx, yy)
g.KruskalMST()



3.knapsack

'''
Write a program to solve the following 0/1 Knapsack using dynamic programming
approach profits p=(15,25,13,23),weight W=(2,6,12,9),Knapsack C=20 and number of items n=4.
'''

# A Dynamic Programming based Python
# Program for 0-1 Knapsack problem
# Returns the maximum value that can
# be put in a knapsack of capacity W

def knapSack(W, wt, val, n):
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]

    # Build table K[][] in bottom up manner
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i-1] <= w:
                K[i][w] = max(val[i-1]
                        + K[i-1][w-wt[i-1]],
                            K[i-1][w])
            else:
                K[i][w] = K[i-1][w]

    return K[n][W]


# Driver code
wt=[]
val=[]
W,n=input("Enter the capacity of Knapsack and number of item:").split()
W=int(W)
n=int(n)
print('Enter weight and their corresponding value with space:')
for mn in range(0,n):
    x,y=input().split()
    wt.append(int(x))
    val.append(int(y))

print("Output:",knapSack(W, wt, val, n))

4.job sequence

'''Write a program using greedy method to solve this problem when no of job n=5,
profits (P1,P2,P3,P4,P5) = (3,25,1,6,30) and deadlines (d1,d2,d3,d4,d5) = (1,3,2,1,2).
'''

# 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
        # (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 = [['J1', 1, 3],  # Job Array
       ['J2', 3, 25],
       ['J3', 2, 1],
       ['J4', 1, 6],
       ['J5', 2, 30]]

print("Following is maximum profit sequence of jobs")
printJobScheduling(arr, 3)  # Function Call


5.n queen

#Write a program to solve n-queen’s problem using backtracking.

#Number of queens
print ("Enter the number of queens")
N = int(input())

#chessboard
#NxN matrix with all elements 0
board = [[0 for x in range(N)]for x in range(N)]

def is_attack(i, j):
    #checking if there is a queen in row or column
    for k in range(0,N):
        if board[i][k]==1 or board[k][j]==1:
            return True
    #checking diagonals
    for k in range(0,N):
        for l in range(0,N):
            if (k+l==i+j) or (k-l==i-j):
                if board[k][l]==1:
                    return True
    return False

def N_queen(n):
    #if n is 0, solution found
    if n==0:
        return True
    for i in range(0,N):
        for j in range(0,N):
            '''checking if we can place a queen here or not
            queen will not be placed if the place is being attacked
            or already occupied'''
            if (not(is_attack(i,j))) and (board[i][j]!=1):
                board[i][j] = 1
                #recursion
                #wether we can put the next queen with this arrangment or not
                if N_queen(n-1)==True:
                    return True
                board[i][j] = 0

    return False

N_queen(N)
for i in board:
    print (i)

6.merge sort

# A program to sort a linear array using merge sort algorithm.
def mergeSort(arr):
    if len(arr) > 1:

        # Finding the mid of the array
        mid = len(arr)//2 # take floor division

        # 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

        # 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
    print('Merging ',arr)
#Take input from user
n=int(input('How many numbers:'))
arr=list(map(int,input('Enter the elements:').split()[:n]))
print('Before sorting the array is',arr)
#call mergesort function
mergeSort(arr)
print('After sort the array is',arr)