Programming
Lab-
Algorithm
Practical Note
Book
DEPARTMENT OF COMPUTER SCIENCE
2024 – 2026
DEPARTMENT OF COMPUTER SCIENCE
2024- 2026
DEPARTMENT OF COMPUTER SCIENCE
2024 – 2026
[Link]:
Certified that this is bonafide record done by
Staff Incharge Head of Department
Submitted for the Practical Examination held on
Internal Examiner External Examiner
CONTENTS
[Link] DATE PROGRAMS PAGE. SIGN
NO.
1 VARIOUS OPERATIONS
ON STACK
2 VARIOUS OPERATIONS
IN QUEUE
3 TOWER OF HANOI
PROBLEM
4 SORTING OF ARRAY USING
QUICK SORT
5 SEARCHING AN ELEMENT
IN A TREE USING DIVIDE
AND CONQUER STRATEGY
6 MERGE SORT
7 KNAPSACK PROBLEM
8 SALESMEN PROBLEM
9 8*8 MATRICES
EX NO: 1
DATE:
VARIOUS OPERATIONS ON STACK
AIM:
To write a program to perform various operations on stack.
ALGORITHM:
STEP 1: Start the process.
STEP 2: Initialize a stack with a specified size and a top pointer set to 0.
STEP 3: Present a menu for Insertion, Deletion, Display, or Exit options.
STEP 4: For Insertion, if the stack is not full, increment the top pointer, add
the element to the stack, and display the stack.
STEP 5: For Deletion, if the stack is not empty, decrement the top pointer,
remove and display the deleted element from the stack.
STEP 6: For Display, print the current elements in the stack.
STEP 7: Repeat the menu until the user chooses to Exit, and handle invalid
selections.
STEP 8: Stop the process.
CODING:
def insert (stack, x):
global top, size
if top >= size:
print ("Stack is full")
else:
top = top + 1
stac k . append(x)
print("The stack elements are", stack)
def delete(stack):
global top
if top == 0:
print("Stack is empty")
else:
top = top - 1
print("The deleted element is", [Link]())
def display(stack):
print("The stack elements are:", stack)
size = int(input("Enter the size of the stack: "))
top = 0
stack = []
while True:
print ("Stack operations")
print ("1. Insertion")
print ("2. Deletion")
print ("3. Display")
print ("4. Exit")
print ("Enter your choice: ")
choice = int(input())
if choice == 1:
print ("The stack elements are:", stack)
x = int (input("Enter the data: "))
insert (stack, x)
elif choice == 2:
delete(stack)
elif choice == 3:
display(stack)
elif choice == 4:
break
else:
print ("Invalid choice")
OUTPUT:
EX NO: 2
DATE:
VARIOUS OPERATIONS IN QUEUE
AIM:
To write a program to perform various operation in queue.
ALGORITHM:
STEP 1: Start the process.
STEP 2: Initialize the circular queue with size and two pointers (front and rear)
set to 0.
STEP 3: Present a menu for Insert, Delete, Print, or Exit options.
STEP 4: For Insert, add an element to the rear of the queue, wrapping around if
full.
STEP 5: For Delete, remove an element from the front of the queue.
STEP 6: For Print, display the current queue.
STEP 7: Repeat until Exit choice; handle invalid selections.
STEP 8: Stop the process.
CODING:
def insert(q, data):
global front, rear
rear = (rear + 1) % n
if rear == front:
print("Queue is full")
if front == 0:
rear = n - 1
else:
rear = rear - 1
else:
q[rear] = data
def delete(q):
global front, rear
if front == rear:
print("Queue is empty")
else:
front = (front + 1) % n
q[front] = None
# Main program
front = 0
rear = 0
print("Enter the size of the queue:")
n = int(input())
q = [None] * n
while True:
print ("Circular Queue operations")
print ("1. Insert")
print ("2. Delete")
print ("3. Print")
print ("4. Exit")
print ("Enter your choice:")
choice = int (input ())
if choice == 1:
print ("Enter the element to insert into the queue")
data = int (input ())
insert (q, data)
elif choice == 2:
delete(q)
elif choice == 3:
print(q)
elif choice == 4:
break
else:
print ("Invalid choice")
OUTPUT:
EX NO: 3
DATE:
PROGRAM USING TOWER OF HANOI
AIM:
To write a program to solve the tower of Hanoi problem.
ALGORITHMS:
STEP 1: Start the process.
STEP 2: Define a function tower of Hanoi that takes the number of disks n,
source, auxiliary, and target pegs as parameters.
STEP 3: If there’s only one disk (base case), print the move from the source peg
to the target peg.
STEP 4: For more than one disk, recursively move the top n-1 disks from the
source to the auxiliary peg.
STEP 5: Print the move of the nth disk from the source to the target peg.
STEP 6: Recursively move the n-1 disks from the auxiliary peg to the target
peg.
STEP 7: Set the number of disks n and pegs for source, auxiliary, and target.
STEP 8: Call the function to solve the Tower of Hanoi problem with the
provided parameters.
STEP 9: Stop the Process.
CODING:
def tower_of_hanoi(n, source, auxiliary, target):
if n == 1:
print("Move disk 1 from {} to {}".format(source, target))
return
tower_of_hanoi(n - 1, source, target, auxiliary)
print("Move disk {} from {} to {}".format(n, source, target))
tower_of_hanoi(n - 1, auxiliary, source, target)
n=3
source_peg = "A"
auxiliary_peg = "B"
target_peg = "C"
tower_of_hanoi(n, source_peg, auxiliary_peg, target_peg)
OUTPUT:
EX NO: 4
DATE:
SORTING OF ARRAY USING QUICK SORT
AIM:
To write a program to sort an array of an elements using quick sort.
ALGORITHM
STEP 1: Start the process.
STEP 2: Define a recursive function for quick sort.
STEP 3: Check if the array has one or zero elements (base case), return it.4
STEP 4: Choose a pivot element from the array.
STEP 5: Partition the array into two subarrays: elements less than the pivot.
STEP 6: Partition the array into another subarray: elements greater than or
equal to the pivot.
STEP 7: Recursively call quick sort on the left subarray.
STEP 8: Recursively call quick sort on the right subarray.
STEP 9: Combine the sorted left subarray, pivot, and sorted right subarray.
STEP 10: Return the combined sorted array.
CODING:
def partition(a,m,q):
v = a[m]
i=m
j=q
while i <=j:
while a[i] < v:
i=i+1
while a[j] > v:
j=j-1
if i < j:
a[i], a[j] = a[j], a[i]
else:
return j
def quick_sort(a,low,high):
if low < high:
mid = partition(a, low, high)
quick_sort(a, low, mid - 1)
quick_sort(a, mid + 1, high)
print("Enter the size of the input data:")
n = int(input())
a = []
print("Enter the data:")
for i in range(n):
value = int(input())
[Link](value)
low = 0
high = n - 1
quick_sort(a,low,high)
print("sorted list:",a)
OUTPUT:
EX NO: 5
DATE:
SEARCHING AN ELEMENT IN A TREE USING DIVIDE AND
CONQUER STRATEGY
AIM:
Write a program to search for an element in a tree using divide & conquer
strategy.
ALGORITHM:
STEP 1: Start the process.
STEP 2: Define a function binary (a, x, n) that takes the sorted array a, the
target element x, and the array size n.
STEP 3: Initialize two variables: low = 0 and high = n - 1 to set the boundaries
of the search range.
STEP 4: Enter a while loop that continues as long as low <= high
(search space is valid).
STEP 5: Calculate the middle index mid = (low + high) // 2.
STEP 6: If a[mid] == x, return 0 to indicate the element has been found.
STEP 7: If x < a[mid], set high = mid - 1 to search the left half; otherwise, set
low = mid + 1 to search the right half.
STEP 8: If the element is not found (loop ends without returning), return 1 to
the element is not present.
STEP 9: Stop the process
CODING:
def binary(a, x, n):
low = 0
high = n-1
while low <= high:
mid = (low + high) // 2
if x == a[mid]:
return 0
elif x < a[mid]:
high = mid - 1
elif x > a[mid]:
low = mid + 1
else:
return 1
n = int(input("Enter the size of the array: "))
a = []
for i in range(n):
element = int(input("Enter element : "))
[Link](element)
x = int(input("Enter the element to search for: "))
result= binary(a, x, n)
print(result)
if result==0:
print("element is present")
else:
print("element is not present")
OUTPUT:
EX NO: 6
DATE:
MERGE SORT
AIM:
To Write a program to solve number of elements in ascending order using
Merge sort.
ALGORITHM:
STEP 1: Start the process.
STEP 2: Define a recursive function for merge sort
STEP 3: Check if the array has one or zero elements (base case), return it.
STEP 4: Split the array into two halves.
STEP 5: Recursively call merge sort on the left half.
STEP 6: Recursively call merge sort on the right half.
STEP 7: Merge the sorted halves
STEP 8: Initialize pointers for both halves and a result array, Compare
elements from both halves, adding the smaller element to the result and
Append any remaining elements from either half to the result.
STEP 9: Stop the process.
CODING:
def merge(low, mid, high):
i = low
k = low
j = mid + 1
while i <= mid and j <= high:
if a[i] < a[j]:
b[k] = a[i]
i=i+1
else:
b[k] = a[j]
j=j+1
k=k+1
while i <= mid:
b[k] = a[i]
i=i+1
k=k+1
while j <= high:
b[k] = a[j]
j=j+1
k=k+1
for h in range(low ,high + 1):
a[h] = b[h]
def merge_sort(low,high):
if(low<high):
mid = (low+high)//2
merge_sort(low,mid)
merge_sort(mid+1,high)
merge(low,mid,high)
a = []
b = []
print("Enter the no of elements to be sorted: ")
n = int(input())
print("Enter the elements:")
for i in range(n):
value = int(input())
[Link](value)
[Link](0)
low = 0
high = n - 1
merge_sort(low,high)
print("Sorted list:",a)
OUTPUT:
EX NO:7
DATE:
KNAPSACK PROBLEM
AIM:
To write a program to solve the knapsack problem using greedy method.
ALGORITHM:
STEP 1: Define a 2D table dp for storing maximum values for subproblems.
STEP 2: Initialize the first row and column of dp with zeros.
STEP 3: Iterate through items one by one.
STEP 4: For each item, iterate through possible weights from 1 to capacity.
STEP 5: Check if the current item's weight is less than or equal to the current
capacity.
STEP 6: If it fits, calculate the maximum value by including or excluding the
item.
STEP 7: Update the dp table with the maximum value for the current weight.
STEP 8: Continue until all items and weights are processed.
STEP 9:. Return the value in the last cell of the dp table as the result.
CODING:
def greedy_knapsack(weights, values, capacity):
n = len(weights)
x = [0.0] * n
u = capacity
for i in range(n):
if weights[i] > u:
break
x[i] = 1.0
u -= weights[i]
if i < n and u > 0:
x[i] = u / weights[i]
u=0
return x
weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50
result = greedy_knapsack(weights, values, capacity)
print("Fraction of each item taken:", result)
OUTPUT
EX NO: 8
DATE:
SALESMAN PROBLEM
AIM:
To write a program using exception handling.
ALGORITHM:
STEP 1: Start the program.
STEP 2: Input Data: Collect a list of cities and their pairwise distances.
STEP 3: Initialize: Choose a starting city and mark it as visited.
STEP 4: Find Nearest Neighbor: Identify the nearest unvisited city from the
current city.
STEP 5: Move to Nearest City: Travel to the nearest unvisited city and update
the path.
STEP 6: Repeat: Continue finding and visiting the nearest unvisited city.
STEP 7: Complete Visit: Ensure all cities are visited exactly once.
STEP 8: Return to Start: Travel back to the starting city to close the loop.
STEP 9: Calculate Distance: Sum up all distances traveled in the tour.
STEP 10: Output Solution: Display the path and total distance as the solution.
CODING:
def tsp_nearest_neighbor(distance_matrix):
n = len(distance_matrix) # Number of cities
visited = [False] * n
path = []
total_distance = 0
# Start from the first city (index 0)
current_city = 0
visited[current_city] = True
[Link](current_city)
for _ in range(n - 1):
nearest_city = None
nearest_distance = float('inf')
# Find the nearest unvisited city
for next_city in range(n):
if not visited[next_city] and distance_matrix[current_city][next_city] <
nearest_distance:
nearest_city = next_city
nearest_distance = distance_matrix[current_city][next_city]
# Visit the nearest city
visited[nearest_city] = True
[Link](nearest_city)
total_distance += nearest_distance
current_city = nearest_city
# Return to the starting city
total_distance += distance_matrix[current_city][path[0]]
[Link](path[0]) # Complete the cycle
return path, total_distance
# Example distance matrix
distance_matrix = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
# Run the algorithm
path, total_distance = tsp_nearest_neighbor(distance_matrix)
print("Path:", path)
print("Total Distance:", total_distance)
OUTPUT:
EX NO: 9
DATE:
PROGRAM USING INHERITANCE
AIM:
To write a python program using Inheritance.
ALGORITHM:
STEP 1: Initialize an empty 8x8 chessboard.
STEP 2: Place the first queen in the first row, first column.
STEP 3: Move to the next row and attempt to place a queen in the first
available column.
STEP 4: If placing the queen results in a conflict (same column or diagonal),
backtrack to the previous row.
STEP 5: For each row, repeat the process until all 8 queens are placed.
STEP 6: If you reach the last row and no conflicts occur, output the solution.
STEP 7: Backtrack if placing a queen results in a conflict.
STEP 8: Repeat steps 3 to 7 until all possible solutions are found.
STEP 9: Return all solutions once all queens are placed without conflict.
CODING:
def place(k, i, x):
for j in range(k):
# Check if there's already a queen in the same column or diagonal
if x[j] == i or abs(x[j] - i) == abs(j - k):
return False
return True
def NQueens(k, n, x):
for i in range(n):
if place(k, i, x):
x[k] = i
if k == n - 1:
for i in range(n):
row = ['.'] * n
row[x[i]] = 'Q'
print(" ".join(row))
print("\n")
else:
NQueens(k + 1, n, x)
# Main function to solve the 8-Queens problem
def solve_8_queens():
n=8
x = [-1] * n
NQueens(0, n, x)
solve_8_queens()
OUTPUT: