Analysis And Design Of Algorithms
Course Code: 24PCA401
By: Dr. Praveen N
Nitte Institute of Professional Education(NIPE)
NITTE (Deemed to be University), Mangaluru
Note: Please use your Nitte email ID to access the Google Drive files.
Lab Programs & Performance Analysis
Floyd's Algorithm
def floyd_warshall(graph):
v = len(graph)
dist = list(map(lambda i: list(map(lambda j: j, i)), graph))
for k in range(v):
for i in range(v):
for j in range(v):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return distComplexity: $O(V^3)$
Download Code0/1 Knapsack (DP)
Solve the 0/1 Knapsack problem using Dynamic Programming.
Complexity: $O(N \times W)$
Download CodeGreedy Knapsack
Discrete & Continuous Knapsack using Greedy Approximation.
Complexity: $O(N \log N)$
Download CodeQuick Sort
Sorting with Quick Sort, including empirical time analysis for $n > 5000$.
Complexity: $O(N \log N)$ average
Download Code
Merge Sort
Sorting with Merge Sort, including empirical time analysis for $n > 5000$.
Complexity: $O(N \log N)$
Download Code
N Queen's Problem
def solve_n_queens(n):
# Solves N-Queens using Backtracking
board = [['.'] * n for _ in range(n)]
# ... (Backtracking logic)Complexity: $O(N!)$
Download CodeSelection Sort
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]Complexity: $O(n^2)$
Download Code
Bubble Sort
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]Complexity: $O(n^2)$
Download Code
Insertion Sort
def insertion_sort(arr):
n=len(arr)
for i in range(1,n):
j=i-1
v=l[i]
while j>=0 and arr[j]>v:
arr[j+1]=l[j]
j=j-1
arr[j+1]=vComplexity: $O(n^2)$
Download Code
Newton's Square Root
guess = n / 2
while(guess != (guess + n / guess) / 2):
guess = (guess + n / guess) / 2