SREE VIDYANIKETHAN ENGINEERING COLLEGE Page No.
:
Date:
Exp. No: 01
MAXIMUM SUBSET SUM USING LINEAR SEARCH TECHNIQUE
SOURCE CODE:
def max_subset_sum(arr):
n = len(arr)
max_sum = 0
max_sum_arr = 0
max_subset_size = 0
max_subset = []
for i in range(n):
current_sum = 0
current_subset = []
max_sum_arr += arr[i]
for j in range(i, n):
current_sum += arr[j]
current_subset.append(arr[j])
if (current_sum > max_sum) or (current_sum == max_sum and
len(current_subset) > max_subset_size):
max_sum = current_sum
max_subset_size = len(current_subset)
max_subset = current_subset.copy()
return max_sum, max_subset_size, max_subset, max_sum_arr
if __name__ == '__main__':
A = list(map(int, input().split()))
max_sum, max_subset_size, max_subset, max_sum_arr = max_subset_sum(A)
print('Array is:', A)
print('Max sum of arr:', max_sum_arr)
print('No. of elements in the chosen subset:', max_subset_size)
print('Chosen subset:', max_subset)
print('Maximum choosen subset sum:', max_sum)
OUTPUT:
1 2 4 -1 0 -3
Array is: [1, 2, 4, -1, 0, -3]
Max sum of arr: 3
No. of elements in the chosen subset: 3
Chosen subset: [1, 2, 4]
Maximum choosen subset sum: 7
Roll No.: 21121A3359
SREE VIDYANIKETHAN ENGINEERING COLLEGE Page No.:
Date:
Exp. No: 02
GROUP TRAVEL SCHEDULING USING BINARY SEARCH
SOURCE CODE:
def main():
num_groups = int(input("Enter the number of groups:"))
num_planes = int(input("Enter the number of planes:"))
group_capacities = list(map(int, input('Enter the capacities of
groups:').split()))
plane_capacities = list(map(int, input('Enter the capacities of
planes:').split()))
group_capacities.sort()
plane_capacities.sort()
start = 0
end = num_planes
minimum_allocation_times = -1
while start <= end:
mid = (start + end) // 2
available_seats = mid // 2
if mid % 2 != 0:
available_seats += 1
seats_left = available_seats
group_index = num_groups - 1
allocation_flag = 0
for plane_index in range(num_planes - 1, -1, -1):
if group_index == -1:
break
seats_left = available_seats
while group_index >= 0 and seats_left > 0:
if plane_capacities[plane_index] >=
group_capacities[group_index]:
group_index -= 1
seats_left -= 1
else:
allocation_flag = 1
break
if group_index == -1 and allocation_flag == 0:
minimum_allocation_times = mid
end = mid - 1
else:
start = mid + 1
print("Minimum allocation times needed:", minimum_allocation_times)
if __name__ == "__main__":
main()
Roll No.: 21121A3359
SREE VIDYANIKETHAN ENGINEERING COLLEGE Page No.:
Date:
OUTPUT:
Enter the number of groups:5
Enter the number of planes:3
Enter the capacities of groups:4 7 9 13 14
Enter the capacities of planes:5 10 15
Minimum allocation times needed: 3
Roll No.: 21121A3359
SREE VIDYANIKETHAN ENGINEERING COLLEGE Page No.:
Date:
Exp. No: 03
QUICK SORT TECHNIQUE TO FIND AN INTEGER NOT IN THE ARRAY AND GREATER THAN KEY
SOURCE CODE:
def partition(array, low, high):
pivot = array[high]
i = low - 1
for j in range(low, high):
if array[j] <= pivot:
i = i + 1
(array[i], array[j]) = (array[j], array[i])
(array[i + 1], array[high]) = (array[high], array[i + 1])
return i + 1
def quickSort(array, low, high):
if low < high:
pi = partition(array, low, high)
quickSort(array, low, pi - 1)
quickSort(array, pi + 1, high)
# data = [8, 7, 2, 1, 0, 9, 6]
data = list(map(int,input('Enter the array:').split()))
print('Unsorted Array:', data)
quickSort(data, 0, len(data) - 1)
sorted_array = data
print('Sorted Array:', sorted_array)
# key = 1
key = int(input('Enter the key : '))
def find_smallest_greater_number(sorted_array, key):
smallest = key + 1
for num in sorted_array:
if num == smallest:
smallest += 1
elif num > smallest:
return smallest
return smallest
result = find_smallest_greater_number(sorted_array, key)
if key in sorted_array:
print(f"The smallest integer greater than {key} not present in the array is
{result}.")
else:
print('Key is not in array. Please input key which is in array.')
Roll No.: 21121A3359
SREE VIDYANIKETHAN ENGINEERING COLLEGE Page No.:
Date:
OUTPUT:
Enter the array:8 7 2 1 0 9 6
Unsorted Array: [8, 7, 2, 1, 0, 9, 6]
Sorted Array: [0, 1, 2, 6, 7, 8, 9]
Enter the key : 1
The smallest integer greater than 1 not present in the array is 3.
Roll No.: 21121A3359
SREE VIDYANIKETHAN ENGINEERING COLLEGE Page No.:
Date:
Exp. No.: 04
COMPUTE TIME COMPLEXITY OF N INTEGER USING MERGE SORT
SOURCE CODE:
import random
import timeit
import matplotlib.pyplot as plt
import math
def mergeSort(array):
if len(array) > 1:
mid = len(array) // 2
l = array[:mid]
r = array[mid:]
#sort the two halves array
mergeSort(l)
mergeSort(r)
i=j=k=0
while i<len(l) and j<len(r):
if l[i] < r[j]:
array[k] = l[i]
i += 1
else:
array[k] = r[j]
j += 1
k += 1
while i<len(l):
array[k] = l[i]
i += 1
k += 1
while j<len(r):
array[k] = r[j]
j += 1
k += 1
def measureTime(n):
array = [random.randint(1, 100000) for _ in range(n)]
start = timeit.default_timer()
mergeSort(array)
end = timeit.default_timer()
return end-start
# main program
if __name__ == '__main__':
n_values = [2000, 3000, 7000, 5000, 6000, 10000]
time_taken = []
for n in n_values:
time_taken.append(measureTime(n))
Roll No.: 21121A3359
SREE VIDYANIKETHAN ENGINEERING COLLEGE Page No.:
Date:
# plot the graph
plt.plot(n_values, time_taken, marker='o')
plt.xlabel('No. of elements')
plt.ylabel('Time taken')
plt.title('Time VS no. of elements', color='red')
plt.grid(True)
plt.show()
def printComplexity(n):
print('\nn_values\t Best_case \t Avg_case \t\t Worst_case')
for n in n_values:
best = n*math.log(n)
avg = n*math.log(n)
worst = n*math.log(n)
print(n,'\t', best,'\t', avg, '\t', worst)
printComplexity(n)
OUTPUT:
n_values Best_case Avg_case Worst_case
2000 15201.804919084165 15201.804919084165 15201.804919084165
3000 24019.10270295074 24019.10270295074 24019.10270295074
7000 61975.657996262154 61975.657996262154 61975.657996262154
5000 42585.96595708119 42585.96595708119 42585.96595708119
6000 52197.08848926115 52197.08848926115 52197.08848926115
10000 92103.40371976183 92103.40371976183 92103.40371976183
Roll No.: 21121A3359
SREE VIDYANIKETHAN ENGINEERING COLLEGE Page No.:
Date:
Exp. No.: 05
DYNAMIC PROGRAMMING TECHNIQUE TO OPTIMIZE PASSING RATE OF STUDENTS
SOURCE CODE:
def find_max_passing_students():
N = int(input("Enter the number of students: "))
marks = []
bounds = []
for i in range(N):
student_marks = int(input(f"Enter marks for student {i+1}: "))
student_bound = int(input(f"Enter bound for student {i+1}: "))
marks.append(student_marks)
bounds.append(student_bound)
# Create a 2D table to store the maximum passing students
dp = [[0 for _ in range(sum(marks) + 1)] for _ in range(N + 1)]
# Sort students by marks in descending order
students = sorted(zip(marks, bounds), reverse=True)
# Initialize the passing count
passing_count = 0
# Iterate through the students and calculate passing students using dynamic
programming
for i in range(1, N + 1):
for j in range(1, sum(marks) + 1):
student_marks, student_bound = students[i - 1]
if student_marks > j:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - student_marks] +
student_bound)
# The maximum passing students will be in dp[N][sum(marks)]
return dp[N][sum(marks)]
max_passing_students = find_max_passing_students()
print(f"The maximum number of students that can pass is: {max_passing_students}")
Roll No.: 21121A3359
SREE VIDYANIKETHAN ENGINEERING COLLEGE Page No.:
Date:
OUTPUT:
Enter the number of students: 4
Enter marks for student 1: 80
Enter bound for student 1: 10
Enter marks for student 2: 85
Enter bound for student 2: 15
Enter marks for student 3: 90
Enter bound for student 3: 20
Enter marks for student 4: 95
Enter bound for student 4: 25
The maximum number of students that can pass is: 70
Roll No.: 21121A3359
SREE VIDYANIKETHAN ENGINEERING COLLEGE Page No.:
Date:
Exp. No.: 06
0/1 KNAPSACK PROBLEM USING DYNAMIC PROGRAMMING
SOURCE CODE:
def knapsack(weights, values, capacity):
n = len(weights)
# Initialize a table to store the maximum values for different subproblems.
dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
# Build the table using dynamic programming.
for i in range(1, n + 1):
for w in range(1, capacity + 1):
if weights[i - 1] <= w:
# If the current item can fit in the knapsack, decide whether to
include it or not.
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] +
values[i - 1])
else:
# If the current item's weight exceeds the current knapsack
capacity, skip it.
dp[i][w] = dp[i - 1][w]
# Reconstruct the solution by backtracking through the table.
selected_items = []
i, w = n, capacity
while i > 0 and w > 0:
if dp[i][w] != dp[i - 1][w]:
selected_items.append(i - 1)
w -= weights[i - 1]
i -= 1
# Return the maximum value and the indices of selected items.
max_value = dp[n][capacity]
return max_value, selected_items
# Take user input for weights, values, and capacity.
n = int(input("Enter the number of items: "))
weights = []
values = []
for i in range(n):
weight = int(input(f"Enter the weight of item {i + 1}: "))
value = int(input(f"Enter the value of item {i + 1}: "))
weights.append(weight)
values.append(value)
capacity = int(input("Enter the knapsack capacity: "))
# Call the knapsack function with user-provided inputs.
max_value, selected_items = knapsack(weights, values, capacity)
print("Maximum value:", max_value)
print("Selected items:", selected_items)
Roll No.: 21121A3359
SREE VIDYANIKETHAN ENGINEERING COLLEGE Page No.:
Date:
OUTPUT:
Enter the number of items: 5
Enter the weight of item 1: 2
Enter the value of item 1: 3
Enter the weight of item 2: 3
Enter the value of item 2: 4
Enter the weight of item 3: 4
Enter the value of item 3: 5
Enter the weight of item 4: 5
Enter the value of item 4: 6
Enter the weight of item 5: 6
Enter the value of item 5: 7
Enter the knapsack capacity: 7
Maximum value: 9
Selected items: [2, 1]
Roll No.: 21121A3359
SREE VIDYANIKETHAN ENGINEERING COLLEGE Page No.:
Date:
Exp. No.: 07
ALL-PAIRS SHORTEST PATHS USING FLOYDWARSHALL ALGORITHM
SOURCE CODE:
import sys
def floyd_warshall(graph, num_vertices):
distance = graph
# Apply the Floyd-Warshall algorithm
for k in range(num_vertices):
for i in range(num_vertices):
for j in range(num_vertices):
if distance[i][k] + distance[k][j] < distance[i][j]:
distance[i][j] = distance[i][k] + distance[k][j]
return distance
def print_solution(distance, num_vertices):
for i in range(num_vertices):
for j in range(num_vertices):
if distance[i][j] == float("inf"):
print("inf", end="\t")
else:
print(distance[i][j], end="\t")
print()
if __name__ == "__main__":
graph = [
[0, 3, float("inf"), 7],
[8, 0, 2, float("inf")],
[5, float("inf"), 0, 1],
[2, float("inf"), float("inf"), 0]
]
num_vertices = len(graph)
shortest_paths = floyd_warshall(graph, num_vertices)
print("Shortest distances between all pairs of vertices:")
print_solution(shortest_paths, num_vertices)
OUTPUT:
Shortest distances between all pairs of vertices:
0 3 5 6
5 0 2 3
3 6 0 1
2 5 7 0
Roll No.: 21121A3359
SREE VIDYANIKETHAN ENGINEERING COLLEGE Page No.:
Date:
Exp. No.: 08
FIND & DISPLAY GOOD PAIRS OF STRING IN N BINARY STRINGS
SOURCE CODE:
def find_common_characters(str1, str2):
# Create two sets to store the characters in each string
set1 = set(str1)
set2 = set(str2)
# Check if there's any common character
common_characters = set1.intersection(set2)
return common_characters
def find_good_pairs(binary_strings):
good_pairs = []
n = len(binary_strings)
for i in range(n):
for j in range(i + 1, n):
common_chars = find_common_characters(binary_strings[i],
binary_strings[j])
if len(common_chars) > 0:
good_pairs.append((binary_strings[i], binary_strings[j]))
return good_pairs
binary_strings = ["1", "01", "001", "000", "11111", "1010", "101010"]
good_pairs = find_good_pairs(binary_strings)
for pair in good_pairs:
print(f"Good pair: {pair[0]} and {pair[1]}")
OUTPUT:
Good pair: 1 and 01
Good pair: 1 and 001
Good pair: 1 and 11111
Good pair: 1 and 1010
Good pair: 1 and 101010
Good pair: 01 and 001
Good pair: 01 and 000
Good pair: 01 and 11111
Good pair: 01 and 1010
Good pair: 01 and 101010
Good pair: 001 and 000
Good pair: 001 and 11111
Good pair: 001 and 1010
Good pair: 001 and 101010
Good pair: 000 and 1010
Good pair: 000 and 101010
Good pair: 11111 and 1010
Good pair: 11111 and 101010
Good pair: 1010 and 101010
Roll No.: 21121A3359
SREE VIDYANIKETHAN ENGINEERING COLLEGE Page No.:
Date:
Exp. No.: 09
KNAPSACK PROBLEM USING GREEDY METHOD
SOURCE CODE:
def knapsack_greedy(values, weights, capacity):
# Calculate the value-to-weight ratio for each item
value_per_weight = [(v / w, v, w) for v, w in zip(values, weights)]
value_per_weight.sort(reverse=False)
total_value = 0
knapsack = [] # Items selected for the knapsack
for ratio, value, weight in value_per_weight:
if capacity >= weight:
knapsack.append((value, weight))
total_value += value
capacity -= weight
return total_value, knapsack
# Example usage
# values = [60, 100, 120]
# weights = [10, 20, 30]
# capacity = 50
values = [100,500,400,150]
weights = [20,30,40,10]
capacity = 75
max_value, selected_items = knapsack_greedy(values, weights, capacity)
print(f"Maximum value: {max_value}")
print("Selected items:")
for value, weight in selected_items:
print(f"Value: {value}, Weight: {weight}")
OUTPUT:
Maximum value: 650
Selected items:
Value: 100, Weight: 20
Value: 400, Weight: 40
Value: 150, Weight: 10
Roll No.: 21121A3359
SREE VIDYANIKETHAN ENGINEERING COLLEGE Page No.:
Date:
Exp. No.: 10
DIJKSTRA’S ALGORITHM FOR SOLVING SINGLE SOURCE SHORTEST PATH PROBLEM USING GREEDY
APPROACH
SOURCE CODE:
import heapq
def dijkstra(graph, start):
# Create a dictionary to store the shortest distances from the start node
shortest_distances = {node: float('inf') for node in graph}
shortest_distances[start] = 0
# Create a priority queue to keep track of nodes to visit next
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
# If the current distance is greater than what we have in the dictionary,
skip this node
if current_distance > shortest_distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
# If we find a shorter path to the neighbor, update the distance and add
it to the priority queue
if distance < shortest_distances[neighbor]:
shortest_distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return shortest_distances
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
start_node = 'A'
shortest_distances = dijkstra(graph, start_node)
for node, distance in shortest_distances.items():
print(f"Shortest distance from {start_node} to {node} is {distance}")
OUTPUT:
Shortest distance from A to A is 0
Shortest distance from A to B is 1
Shortest distance from A to C is 3
Shortest distance from A to D is 4
Roll No.: 21121A3359
SREE VIDYANIKETHAN ENGINEERING COLLEGE Page No.:
Date:
Exp. No.: 11
FIND BEAUTIFUL NUMBERS USING GREEDY APPROACH
SOURCE CODE:
def is_beautiful_number(num):
num_str = str(num)
length = len(num_str)
N = length // 2
first_half = int(num_str[:N])
second_half = int(num_str[N:])
return sum(map(int, str(first_half))) == sum(map(int, str(second_half)))
def find_beautiful_numbers_in_interval(M, N):
beautiful_numbers = []
for num in range(M, N + 1):
if is_beautiful_number(num):
beautiful_numbers.append(num)
return beautiful_numbers
M = 10
N = 100
beautiful_numbers = find_beautiful_numbers_in_interval(M, N)
print("Beautiful numbers in the interval [", M, "-", N, "]:", beautiful_numbers)
OUTPUT:
Beautiful numbers in the interval [ 10 - 100 ]: [11, 22, 33, 44, 55, 66, 77, 88, 99]
Roll No.: 21121A3359
SREE VIDYANIKETHAN ENGINEERING COLLEGE Page No.:
Date:
Exp. No.: 12
FIND SUBSET OF GIVEN SET USING BACKTRACKING TECHNIQUE
SOURCE CODE:
def subset_sum(S, target_sum):
def backtrack(start, current_subset, current_sum):
if current_sum == target_sum:
solutions.append(current_subset[:])
return
if current_sum > target_sum or start == len(S):
return
for i in range(start, len(S)):
current_subset.append(S[i])
backtrack(i + 1, current_subset, current_sum + S[i])
current_subset.pop()
solutions = []
backtrack(0, [], 0)
return solutions
S = [1, 2, 5, 6, 8]
d = 9
result = subset_sum(S, d)
if result:
print("Solutions:")
for subset in result:
print(subset)
else:
print("No solution found.")
OUTPUT:
Solutions:
[1, 2, 6]
[1, 8]
Roll No.: 21121A3359
SREE VIDYANIKETHAN ENGINEERING COLLEGE Page No.:
Date:
Exp. No.: 04
TABLE-DRIVEN AGENT
SOURCE CODE:
OUTPUT:
Exp. No.: 04
WORKING WITH DIFFERENT DATA FORMATS USING PANDAS
SOURCE CODE:
import pandas as pd
import json
from io import StringIO
def a():
csv_file_path = input("Enter the CSV file path: ")
df = pd.read_csv(csv_file_path)
print(df.head())
output_csv_path = input("Enter the output CSV file path: ")
df.to_csv(output_csv_path, index=False)
def b():
json_file_path = input("Enter the JSON file path: ")
df = pd.read_json(json_file_path)
print(df.head())
output_json_path = input("Enter the output JSON file path: ")
df.to_json(output_json_path, orient='records')
json_data = input("Enter JSON data as a string: ")
parsed_data = pd.read_json(StringIO(json_data))
print(parsed_data)
def c():
excel_file_path = input("Enter the Excel file path: ")
df = pd.read_excel(excel_file_path, sheet_name='Sheet1')
print(df.head())
output_excel_path = input("Enter the output Excel file path: ")
df.to_excel(output_excel_path, sheet_name='Sheet1', index=False)
def switch(ch):
if ch=='a':
return a()
elif ch=='b':
return b()
else:
return c()
t=1
while(t>0):
ch=input("Enter your choice:")
if ch=='e':
Roll No.: 21121A3359
SREE VIDYANIKETHAN ENGINEERING COLLEGE Page No.:
Date:
t=0
else:
t=t+1
switch(ch)
OUTPUT:
Enter your choice:a
Enter the CSV file path: your_input.csv
Name Age City
0 lakshmi 20 Kurnool
1 Ram 21 Chennai
2 marry 27 Mumbai
3 chalapathi 29 Tirupati
Enter the output CSV file path: output.csv
Enter your choice:b
Enter the JSON file path: your_input.json
name age city
0 latha 24 Chicago
1 somu 20 Mumbai
2 David 25 Tirupati
3 lucky 24 vizag
Enter the output JSON file path: output.json
Enter JSON data as a string: [{"name": "kiran", "age": 28, "city": "chennai"},
{"name": "lucky", "age": 26, "city": "vizag"}]
name age city
0 kiran 28 chennai
1 lucky 26 vizag
Enter your choice:c
Enter the Excel file path: your_input.xlsx
Unnamed: 0 Name Age City
0 1 John 30 vizag
1 2 Hari 25 chennai
2 3 Muni 28 mumbai
3 4 Marry 22 Tirupati
Enter the output Excel file path: output.xlsx
Enter your choice:e
Roll No.: 21121A3359
