## Sunday, October 10, 2021

### New Minimum Spanning Tree

\textbf{Step 1:} Take the input graph $G$ such that $v$ number of vertices and $e$ number of edges.

\newline \newline

\textbf{Step 2:} Take the input graph $F$ that is a subgraph of $G$.

\newline \newline

\textbf{Step 3:} Initialize an array $result$ to store the minimum spanning tree $(mst)$.

\newline \newline

\textbf{Step 4:} We then iterate through all the edges of the graph $G$ [$for$ $e \in G$], check if the current edge is in the subgraph $F$ (if $e \in F$)

\newline \newline

\textbf{Step 5:} If the condition is true, then add the edge into the $result$ array and delete the edge from $G$.

\newline \newline

\textbf{Step 6: }Repeat steps 4 and 5 until all the edges of $G$ are visited.

\newline \newline

\textbf{Step 7:} We then run Kruskal's algorithm on $G$.

\newline \newline

\textbf{Step 8:} We then sort remaining edges in $G$ in ascending order based on the weight of the edge.

\newline \newline

\textbf{Step 9: }Pick the smallest edge from $G$ and check whether it forms a cycle with already existing edges in the $result$ array. If the cycle is not formed, then add it to the $result$ array. Otherwise, delete it.

\newline \newline

\textbf{Step 10: }Repeat step 9 until there are $(v-1)$ edges in the minimum spanning tree.

\newline \newline

\textbf{Correctness of the algorithm - }We want to include all the edges of the subgraph $F$ in the resulting minimum spanning tree. So, based on above steps we first, we first add all the edges of the subgraph $F$ and then apply Kruskal's algorithm on the remaining edges of graph $G$ to find the minimum spanning tree.

\newline \newline

\textbf{Time Complexity - }

Step 4 - Time complexity for iteration of all edges of graph $G$ is $\mathcal{O}(e)$ \newline

Step 7 - Time complexity of Kruskal's algorithm is $\mathcal{O}(|E| \log |V|)$, \newline

Step 8 - Time complexity of Sorting remaining edges is $\mathcal{O}(|E| \log |E|)$ \newline

Step 9 - Time complexity for picking smallest edge and repeating step is $\mathcal{O}(|E| \log |V|)$ \newline

\newline \newline

\textbf{Total Time Complexity} is $\mathcal{O}(e)$ + $\mathcal{O}(|E| \log |V|)$ +

$\mathcal{O}(|E| \log |E|)$ + $\mathcal{O}(|E| \log |V|)$ = \textbf{$\mathcal{O}(|E| \log |E|)$}

## Sunday, September 19, 2021

### Dynamic Programming - FFT Subset Sum problem

import numpy as np

import math

s = [1,2,3,5,10, 15, 20]

#print("Set", s)

n= int(math.pow(2,len(s)))

#print(power, n)

A = np.zeros(n)

C1 = []

for item in s:

A[item] = 1

A1 = np.fft.fft(A)

# print(len(A1), type(A1), A1)

for i in range(0,n,1):

C1.append(A1[i]*A1[i]*A1[i])

C = np.fft.ifft(C1)

#print(C, C.real)

for i in range(0,n,1):

if C[i].real>=.999999:

print(i,"yes")

else:

print(i,"no")

## Monday, September 13, 2021

### Dynamic Programming - Find Closest Element between 2 arrays - O(n2) time complexity

# Driver Code

A = [6, 1, 12]

B = [1, 0, 8]

C = [0,0,0]

prev = 0

for i in range(0, len(A)):

prev = 0

#print("iteration I=", i)

for j in range (0, len(B)):

#print("iteration J=", j)

temp = abs(A[i]-B[j])

#print("Temp", A[i], B[j], temp, prev)

if(temp >= 0):

if(j == 0):

prev= temp

C[i] = B[j]

if(A[i] == B[j]):

prev = temp

C[i] = B[j]

#print("if", temp, prev)

elif (temp <  prev):

prev = temp

C[i]= B[j]

#print("elif", C[i], prev)

print(C)

Output is: C = [8, 1, 8]

## Saturday, September 11, 2021

### Dynamic Programming - Binary Search - Index function to find 2*x+5 - O(Log n) - Better approach

Time Complexity is O(Log n) . Its better and faster without recursion.

from random import randint

import math

random_odd_numbers = list((val

for val in iter(lambda: randint(-64, 64), 0) if val % 2 != 0))

mylist = sorted(set(random_odd_numbers))

l = 0

h = len(mylist)

while ((h - l) > 1):

mid = math.ceil((l + h) / 2)

#print(mylist[mid], l, mid, h - 1)

if mylist[mid] == 2 * mid + 5 or(mylist[h - 1] == 2 * h + 5) or mylist[l] == 2 * l + 5:

print(2 * h + 5, "yes", mylist)

break

elif mylist[mid] < 2 * mid + 5:

l = mid

else :

h = mid

## Wednesday, September 8, 2021

### Dynamic Programming - Binary Search - Index function to find 2*x+5

Time Complexity O(n log n)

# Python3 Program for recursive binary search.

# Returns index of x in arr if present, else -1

def binarySearch (arr, l, r, x):

# Check base case

#print(x, r)

if r >= l:

mid = l + (r - l) // 2

# If element is present at the middle itself

if arr[mid] == x:

return True

# If element is smaller than mid, then it

# can only be present in left subarray

elif arr[mid] > x:

return binarySearch(arr, l, mid-1, x)

# Else the element can only be present

# in right subarray

else:

return binarySearch(arr, mid + 1, r, x)

else:

# Element is not present in the array

return False

# Driver Code

arr = [ 2, 4, 8, -9, 14, 20, 69 ]

for x in (2**p for p in range(1, len(arr))):

#print(2*x+5)

result = binarySearch(arr, 0, len(arr)-1, (2*x+5))

if(result == True):

print (2*x+5, " - Element is present in the array")

break

if(result == False):

print ("Element is not present in array")

# Function call

## Wednesday, September 1, 2021

### Dynamic Programming - count-ways-reach-nth-stair-using-steps 1-4

Dynamic programming exercise to count number of ways to reach n steps using either n+1 or n+4 steps. Had to use count global variable, as returning r was not giving me the correct answer. This works as expected.

Recursive algorithm - solve(n - 1) + solve(n - 4)

Python code sample:

count = 0

def solve(n):

global count

# Base case

if n < 0:

return 0

if n == 0:

return 1

if n == 1:

count = count + 1

return 1

r = solve(n - 1) + solve(n - 4)

return r

# Driver program to test above function

n = 6

ret = solve(n)

print("Final:", count)

Output of this program is 3.

Example: for n = 6 there are 3 ways to get from stairs 1 to stairs 6.
Those are:
1 → 2 → 3 → 4 → 5 → 6,
1 → 2 → 6, and
1 → 5 → 6