Thursday, November 17, 2022

CS6515 - My Experience with Gerogia Tech's - Intro to Graduate Algorithms course

4 fundamental topics of the course. If you understand these 4, you will pass the course.

  • Dynamic Programming
  • Divide and Conquer
  • Graph Theory
  • NP Reductions
Key is to do all home work assignments practice problems and practice problems from DPV book.
This course is highly theoretical in nature. Course can be extremely challenging for a person new to Computer science. Hard work and practice will see you through. 

Three exams weight 75% of your grades. Remaining are Home work assignments, Coding assignments and Polls. Together they form 25% of your grade. So getting 20-25% should be doable. 

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[19].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