.png)
1. Programs on 1-d arrays like -
a. sum of elements of array,
# sum of elements in given array
def _sum(arr):
sum=0
for i in arr:
sum = sum + i
return(sum)
arr=[]
arr = [12, 3, 4, 15,45,78,450]
n = len(arr)
ans = _sum(arr)
print ('Sum of the array is ', ans)
b. searching an element in array,
#finding an element in an array
#finding character value
x = ['p','y','t','h','o','n']
print(x.index('o'))
# finding numerical value
x = [5,1,7,0,3,4]
print(x.index(7))
c. finding minimum and maximum element in array,
# program to find minimum (or maximum) element in an array
# Minimum Function
def getMin(arr, n):
res = arr[0]
for i in range(1,n):
res = min(res, arr[i])
return res
# Maximum Function
def getMax(arr, n):
res = arr[0]
for i in range(1,n):
res = max(res, arr[i])
return res
# Driver Program
arr = [12, 1234, 45, 67, 1]
n = len(arr)
print ("Minimum element of array:", getMin(arr,n))
d. count the number of even and odd numbers in an array. For all such programs, also find the time complexity, compare if there are multiple methods
def CountingEvenOdd(arr, arr_size):
even_count = 0
odd_count = 0
# loop to read all the values
# in the array
for i in range(arr_size):
# checking if a number is
# completely divisible by 2
if (arr[i] & 1 == 1):
odd_count += 1 #odd_count=odd_count+1
else:
even_count += 1 #even_count=even_count+1
print("Number of even elements = ",even_count)
print("Number of odd elements = ",odd_count)
arr = [2, 3, 4, 6,7,8,9,10,11,12,13]
n = len(arr)
# Function Call
CountingEvenOdd(arr, n)
2. Programs on 2-d arrays like
a. row-sum, and b. column-sum,
n = int(input("Enter the number of rows: "))
m = int(input("Enter the number of columns: "))
# Initialize the matrix with user input values
matrix = []
print("Enter values in matrix:")
for i in range(n):
data = []
for j in range(m):
data.append(int(input()))
matrix.append(data)
# Print the matrix
print("Matrix:")
for i in range(n):
for j in range(m):
print(matrix[i][j], end=" ")
print()
# Calculate and print row-wise sum
for i in range(n):
row_sum = 0
for j in range(m):
row_sum += matrix[i][j]
print(f"Sum of row {i+1}: {row_sum}")
# Calculate and print column-wise sum
for i in range(m):
col_sum = 0
for j in range(n):
col_sum += matrix[j][i]
print(f"Sum of column {i+1}: {col_sum}")
c. sum of diagonal elements,
MAX = 100
def printDiagonalSums(mat, n):
principal = 0
secondary = 0
# Calculate the sum of the elements on the principal and secondary diagonals
for i in range(0, n):
for j in range(0, n):
# Condition for principal diagonal
if (i == j):
principal += mat[i][j]
# Condition for secondary diagonal
if ((i + j) == (n - 1)):
secondary += mat[i][j]
# Print the sums of the diagonals
print("Principal Diagonal:", principal)
print("Secondary Diagonal:", secondary)
# Driver code
a = [[1, 2, 3, 4],
[5, 6, 7, 8],
[1, 2, 3, 4],
[5, 6, 7, 8]]
printDiagonalSums(a, 4)
d. addition of two matrices ,
X = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
Y = [[9, 8, 7],
[6, 5, 4],
[3, 2, 1]]
result = [[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]
# Iterate through rows
for i in range(len(X)):
# Iterate through columns
for j in range(len(X[0])):
result[i][j] = X[i][j] + Y[i][j]
# Print the sum of matrices
for r in result:
print(r)
e. multiplication of two matrices. For all such programs, also find the time complexity, compare if there are multiple methods
# Program to multiply two matrices using nested loops
# Take a 3x3 matrix
A = [[12, 7, 3],
[4, 5, 6],
[7, 8, 9]]
# Take a 3x4 matrix
B = [[5, 8, 1, 2],
[6, 7, 3, 0],
[4, 5, 9, 1]]
result = [[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]]
# Iterating by row of A
for i in range(len(A)):
# Iterating by column by B
for j in range(len(B[0])):
# Iterating by rows of B
for k in range(len(B)):
result[i][j] += A[i][k] * B[k][j]
# Printing the result
for r in result:
print(r)
3. Program to perform
a. linear search
def LinearSearch(array, n, k):
# Loop through the array elements
for j in range(0, n):
# If the element is found, return its index
if (array[j] == k):
return j
# If the element is not found, return -1
return -1
array = [1, 3, 5, 7, 9]
k = 7
n = len(array)
result = LinearSearch(array, n, k)
if(result == -1):
print("Element not found")
else:
print("Element found at index: ", result)
b. binary search on list of elements. Compare the algorithms by calculating time required in milliseconds using readymade libraries.
def BinarySearch(arr, k, low, high):
if high >= low:
mid = low + (high - low)//2
if arr[mid] == k:
return mid
elif arr[mid] > k:
return BinarySearch(arr, k, low, mid-1)
else:
return BinarySearch(arr, k, mid + 1, high)
return -1
arr = [1, 3, 5, 7, 9, 15, 16, 14, 45]
k = 15
result = BinarySearch(arr, k, 0, len(arr)-1)
if result != -1:
print("Element is present at index " + str(result))
else:
print("Not found")
4. Programs to sort elements of list by using various algorithms like
a. bubble,
def bubbleSort(arr):
n = len(arr)
# Traverse through all array elements
for i in range(n):
# Last i elements are already sorted
for j in range(0, 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]
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubbleSort(arr)
print("Sorted array is:")
for i in range(len(sorted_arr)):
print("%d" %sorted_arr[i])
b. selection sort,
def selection_sort(arr):
for i in range(len(arr)):
min_index = i
for j in range(i+1, len(arr)):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
my_list = [5, 3, 8, 6, 7, 2]
sorted_list = selection_sort(my_list)
print(sorted_list)
c. insertion sort. Compare the efficiency of algorithms.
def insertion_sort(list1):
# Outer loop to traverse through 1 to len(list1)
for i in range(1, len(list1)):
value = list1[i]
# Move elements of list1[0..i-1], that are
# greater than value, to one position ahead
# of their current position
j = i - 1
while j >= 0 and value < list1[j]:
list1[j + 1] = list1[j]
j -= 1
list1[j + 1] = value
return list1
# Driver code to test above
list1 = [10, 5, 13, 8, 2]
print("The unsorted list is:", list1)
print("The sorted list1 is:", insertion_sort(list1))
5. Programs to find a pattern in a given string - general way
def search(pat, txt):
M = len(pat)
N = len(txt)
# A loop to slide pat[] one by one
for i in range(N - M + 1):
j = 0
# For current index i, check for pattern match
while(j < M):
if (txt[i + j] != pat[j]):
break
j += 1
if (j == M):
print("Pattern found at index ", i)
# Driver Code
if __name__ == '__main__':
txt = "AABAACAADAABAAABAA"
pat = "AABA"
search(pat, txt)
brute force technique.
def bruteForceStringSearch(text, pattern):
n = len(text)
m = len(pattern)
for i in range(n-m+1):
j = 0
while j < m and text[i+j] == pattern[j]:
j += 1
if j == m:
return i
return -1
text = "hello world"
pattern = "world"
result = bruteForceStringSearch(text, pattern)
if result == -1:
print("Pattern not found in text")
else:
print("Pattern found at index", result)
6. Programs on recursion like
a. factorial,
def factorial(n):
# Checking the number
# is 1 or 0 then
# return 1
# other wise return
# factorial
if (n==1 or n==0):
return 1
else:
return (n * factorial(n - 1))
# Driver Code
num = 5
print("number : ",num)
print("Factorial : ",factorial(num))
b. fibonacci,
def recur_fibo(n):
if n <= 1:
return n
else:
return(recur_fibo(n-1) + recur_fibo(n-2))
nterms = 10
# check if the number of terms is valid
if nterms <= 0:
print("Plese enter a positive integer")
else:
print("Fibonacci sequence:")
for i in range(nterms):
print(recur_fibo(i))
c. Tower of hanoi. Compare algorithms to find factorial/fibonacci using iterative and recursive approaches.
def tower_of_hanoi(n, source, destination, auxiliary):
if n == 1:
print(f"Move disk 1 from {source} to {destination}")
return
tower_of_hanoi(n-1, source, auxiliary, destination)
print(f"Move disk {n} from {source} to {destination}")
tower_of_hanoi(n-1, auxiliary, destination, source)
n = 3
tower_of_hanoi(n, 'A', 'C', 'B')
7. Program to implement
a. file merging,
def merge_files(input_files, output_file):
with open(output_file, 'wb') as outfile:
for file in input_files:
with open(file, 'rb') as infile:
outfile.write(infile.read())
print(f"Files merged into {output_file}")
# example usage
input_files = ["file1.txt", "file2.txt", "file3.txt"]
output_file = "merged_files.txt"
merge_files(input_files, output_file)
b. coin change problems using Greedy Algorithm and to understand time complexity.
def coin_change_greedy(coins, amount):
coins = sorted(coins, reverse=True)
count = 0
for coin in coins:
while amount >= coin:
amount -= coin
count += 1
return count
print(coin_change_greedy([100,50,20,10,5,1],251))
8. Program to implement
a. merge sort,
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
arr = [3, 7, 1, 9, 2, 5]
sorted_arr = merge_sort(arr)
print(sorted_arr)
9. Program to implement fibonacci series using dynamic programming and to understand time complexity. Compare it with the general recursive algorithm.
def recursive_fibonacci(n):
if n <= 1:
return n
else:
return recursive_fibonacci(n-1) + recursive_fibonacci(n-2)
# Dynamic programming algorithm
def dynamic_fibonacci(n):
if n <= 1:
return n
else:
fib = [0, 1]
for i in range(2, n+1):
fib.append(fib[i-1] + fib[i-2])
return fib[n]
# Testing the algorithms
n = 10
print("Recursive algorithm:")
for i in range(n):
print(recursive_fibonacci(i))
print("\nDynamic programming algorithm:")
for i in range(n):
print(dynamic_fibonacci(i))
10. Program to implement N-Queen Problem using Backtracking Strategy and to understand time complexity
def is_valid(board, row, col, n):
# Check if this row on the left side of board
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
# 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 solve_n_queen_util(board, col, n):
if col == n:
return True
for i in range(n):
if is_valid(board, i, col, n):
board[i][col] = 1
if solve_n_queen_util(board, col + 1, n):
return True
board[i][col] = 0
return False
def solve_n_queen(n):
board = [[0 for x in range(n)] for y in range(n)]
if not solve_n_queen_util(board, 0, n):
print("Solution does not exist")
return False
print_solution(board)
return True
def print_solution(board):
for i in range(len(board)):
for j in range(len(board)):
print(board[i][j], end=" ")
print()
n = 4
solve_n_queen(n)
.png)
.png)
.png)
