Assignment1.
Write a program non-recursive and recursive program to calculate Fibonacci numbers and
analyze their time and space complexity.
def recursive_fibonacci(n):
if n<=1:
return n
else:
return recursive_fibonacci(n-1) + recursive_fibonacci(n-2)
def non_recursive_fibonacci(n):
first=0
second=1
print(first)
print(second)
while n-2>0:
third = first + second
first=second
second=third
print(third)
n-=1
if __name__=="__main__":
n=10
for i in range(n):
print(recursive_fibonacci(i))
non_recursive_fibonacci(n)v
Assignment2. Write a program to implement Huffman Encoding using a greedy strategy
import heapq
# Creating Huffman tree node
class node:
def __init__(self,freq,symbol,left=None,right=None):
self.freq=freq # frequency of symbol
self.symbol=symbol # symbol name (character)
self.left=left # node left of current node
self.right=right # node right of current node
self.huff= '' # # tree direction (0/1)
def __lt__(self,nxt): # Check if curr frequency less than next nodes freq
return self.freq<nxt.freq
def printnodes(node,val=''):
newval=val+str(node.huff)
# if node is not an edge node then traverse inside it
if node.left:
printnodes(node.left,newval)
if node.right:
printnodes(node.right,newval)
# if node is edge node then display its huffman code
if not node.left and not node.right:
print("{} -> {}".format(node.symbol,newval))
if __name__=="__main__":
chars = ['a', 'b', 'c', 'd', 'e', 'f']
freq = [ 5, 9, 12, 13, 16, 45]
nodes=[]
for i in range(len(chars)): # converting characters and frequencies into huffman tree nodes
heapq.heappush(nodes, node(freq[i],chars[i]))
while len(nodes)>1:
left=heapq.heappop(nodes)
right=heapq.heappop(nodes)
left.huff = 0
right.huff = 1
# Combining the 2 smallest nodes to create new node as their parent
newnode = node(left.freq + right.freq , left.symbol + right.symbol , left , right)
# node(freq,symbol,left,right)
heapq.heappush(nodes, newnode)
printnodes(nodes[0]) # Passing root of Huffman Tree
OUTPUT:
f -> 0
c -> 100
d -> 101
a -> 1100
b -> 1101
e -> 111
Assignment.3. Write a program to solve a fractional Knapsack problem using a greedy method
def fractional_knapsack():
weights=[10,20,30]
values=[60,100,120]
capacity=50
res=0
# Pair : [Weight,value]
for pair in sorted(zip(weights,values), key= lambda x: x[1]/x[0], reverse=True):
if capacity<=0: # Capacity completed - Bag fully filled
break
if pair[0]>capacity: # Current's weight with highest value/weight ratio Available Capacity
res+=int(capacity * (pair[1]/pair[0])) # Completely fill the bag
capacity=0
elif pair[0]<=capacity: # Take the whole object
res+=pair[1]
capacity-=pair[0]
print(res)
if __name__=="__main__":
fractional_knapsack()
Assignment4. Write a program to solve a 0-1 Knapsack problem using dynamic programming or branch and
bound strategy.
def fractional_knapsack():
weights=[10,20,30]
values=[60,100,120]
capacity=50
res=0
# Pair : [Weight,value]
for pair in sorted(zip(weights,values), key= lambda x: x[1]/x[0], reverse=True):
if capacity<=0: # Capacity completed - Bag fully filled
break
if pair[0]>capacity: # Current's weight with highest value/weight ratio Available Capacity
res+=int(capacity * (pair[1]/pair[0])) # Completely fill the bag
capacity=0
elif pair[0]<=capacity: # Take the whole object
res+=pair[1]
capacity-=pair[0]
print(res)
if __name__=="__main__":
fractional_knapsack()
Assignment5. Design n-Queens matrix having first Queen placed. Use backtracking to place remaining
Queens to generate the final n-queen‘s matrix.
def n_queens(n):
col = set()
posDiag=set() # (r+c)
negDiag=set() # (r-c)
res=[]
board = [["0"]*n for i in range(n) ]
def backtrack(r):
if r==n:
copy = [" ".join(row) for row in board]
res.append(copy)
return
for c in range(n):
if c in col or (r+c) in posDiag or (r-c) in negDiag:
continue
col.add(c)
posDiag.add(r+c)
negDiag.add(r-c)
board[r][c]="1"
backtrack(r+1)
col.remove(c)
posDiag.remove(r+c)
negDiag.remove(r-c)
board[r][c]="0"
backtrack(0)
for sol in res:
for row in sol:
print(row)
print()
if __name__=="__main__":
n_queens(8)
Assignment6. Write a program for analysis of quick sort by using deterministic and randomized variant.
#include<iostream>
using namespace std;
int partition(int * arr, int p, int r){
int x = arr[r];
int i = p - 1;
for(int j = p; j < r; j++){
if(arr[j] <= x){
i++;
swap(arr[i],arr[j]);
}
}
swap(arr[i + 1], arr[r]);
return i + 1;
}
void quickSort(int * arr, int p, int r){
if (p < r){
int q = partition(arr, p, r);
quickSort(arr, p, q - 1);
quickSort(arr, q + 1, r);
}
}
//Randomized
int randomPartition(int * arr, int p, int r){
int x = arr[r];
int i = rand() % ((r - p) + 1) + p;
cout << i << endl;
for(int j = p; j < r; j++){
if(arr[j] <= x){
i++;
swap(arr[i],arr[j]);
}
}
swap(arr[i + 1], arr[r]);
return i + 1;
}
void radomizedQuickSort(int * arr, int p, int r){
if (p < r){
int q = randomPartition(arr, p, r);
radomizedQuickSort(arr, p, q - 1);
radomizedQuickSort(arr, q + 1, r);
}
}
int main(){
int A[] = {23,34,54,123,34,56,67676,112};
int n = sizeof(A)/ sizeof(A[0]);
radomizedQuickSort(A, 0, n - 1);
for(int i : A){
cout << i << " ";
}
cout << '\n';
return 0;
}
