Programming

Lab-
Algorithm
Practical Note
Book

DEPARTMENT OF COMPUTER SCIENCE

2024 – 2026
DEPARTMENT OF COMPUTER SCIENCE

2024- 2026
 DEPARTMENT OF COMPUTER SCIENCE

2024 – 2026

REG.NO:

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

S.NO 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", stack.pop())

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())
a.append(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 : "))
a.append(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())
a.append(value)
b.append(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
path.append(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
path.append(nearest_city)
total_distance += nearest_distance
current_city = nearest_city
 # Return to the starting city
total_distance += distance_matrix[current_city][path[0]]
path.append(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: