Vinit Khandelwal

Here is how to calculate fibonacci with dynamic programming caching. Run the program here:  https://repl.it/@VinitKhandelwal/fibonacci-dynamic-programming cal = 0 def slowFibonacci ( n ): global cal cal += 1 if n< 2 : return n return slowFibonacci ( n -1 ) + slowFibonacci ( n -2 ) cal2 = 0 cache = {} def fastFibonacci ( n ): global cache , cal2 if n in cache : return cache [ n ] else : cal2 += 1 if n< 2 : return n cache [ n ] = fastFibonacci ( n -1 ) + fastFibonacci ( n -2 ) return cache [ n ] print ( f "Fibonacci without caching {slowFibonacci(30)}" ) print ( f "Calculated {cal} times" ) print ( f "Fibonacci without caching {fastFibonacci(30)}" ) print ( f "Calculated {cal2} times" ) OUTPUT Fibonacci without caching 832040 Calculated 2692537 times Fibonacci without caching 832040 Calculated 32 times

Here is how to search using Depth-First-Search (DFS) in Python. There are three ways of implementing DFS - InOrder, PreOrder, and PostOrder. InOrder Depth-First-Search gives output in ascending order PreOrder Depth-First-Search gives output in order of traversing PostOrder Depth-First-Search gives output in order of starting from the last left node, going rightwards and backwards Suppose the following is the tree: 5 / \ 3 7 / \ / \ 2 4 6 8 / \ 1 10 / \ 9 15 / \ 13 19 / \ / \ 11 14 17 20 \ / \ 12 16 18 Here is how all three Depth-First-Search would work class BinaryTree : def __init__ ( self ): self...

Here is how to carry out Breadth First Search on a Binary Search Tree in Python. It is performed in two ways - using loop and using recursive function. Both ways are shown below. Run the code here: https://repl.it/@VinitKhandelwal/breadth-first-search class BinaryTree : def __init__ ( self ): self .reset () def reset ( self ): self .head = None self .crawler = self .head def push ( self , value ): new_node = Node ( value ) # if no head if self .head == None : self .head = new_node print ( f "{value} head" ) # if head else : crawler = self .head while True : if value > crawler.value : if crawler.child_right is None : print ( f "{value} right child of {crawler.value}" ) crawler.child_right = new_node break else : crawler = crawler.child_right elif value < c...

Here is how to sort using Heap Sort in Python? Run the code here:  https://repl.it/@VinitKhandelwal/heap-sort def max_heapify ( A , heap_size , i ): left = 2 * i + 1 right = left + 1 largest = i if left < heap_size and A [ left ] > A [ largest ]: largest = left if right < heap_size and A [ right ] > A [ largest ]: largest = right if largest != i : A [ i ], A [ largest ] = A [ largest ], A [ i ] max_heapify ( A , heap_size , largest ) def build_heap ( A ): heap_size = len ( A ) for i in range ( int ( heap_size/ 2 ), -1 , -1 ): max_heapify ( A , heap_size , i ) def heapsort ( A ): heap_size = len ( A ) build_heap ( A ) #print A #uncomment this print to see the heap it builds for i in range ( heap_size -1 , 0 , -1 ): A [ 0 ], A [ i ] = A [ i ], A [ 0 ] heap_size -= 1 max_heapify ( A , h...

Pythonic way of swapping values between two variables in Python Run the code here:  https://repl.it/@VinitKhandelwal/pythonic-swap x = 1 y = 2 print ( f "x = {x}" ) print ( f "y = {y}" ) # Swap x and y using traditional coding practice temp = x x = y y = temp print ( f "x = {x}" ) print ( f "y = {y}" ) a = 10 b = 20 print ( f "a = {a}" ) print ( f "b = {b}" ) # Swap a and b using Pythonic coding practice a , b = b , a print ( f "a = {a}" ) print ( f "b = {b}" ) OUTPUT x = 1 y = 2 x = 2 y = 1 a = 10 b = 20 a = 20 b = 10 TIME COMPLEXITY O(n log n)

Here is how to sort using Quick Sort in Python. Run this code here:  https://repl.it/@VinitKhandelwal/quick-sort def quickSort ( list1 , left , right ): length = len ( list1 ) if left < right : pivot = right partitionIndex = partition ( list1 , pivot , left , right ) quickSort ( list1 , left , partitionIndex - 1 ) quickSort ( list1 , partitionIndex + 1 , right ) return list1 def partition ( list1 , pivot , left , right ): pivotValue = list1 [ pivot ] partitionIndex = left for i in range ( left , right ): if list1 [ i ] < pivotValue : swap ( list1 , i , partitionIndex ) partitionIndex += 1 swap ( list1 , right , partitionIndex ) return partitionIndex def swap ( list1 , firstIndex , secondIndex ): temp = list1 [ firstIndex ] list1 [ firstIndex ] = list1 [ secondIndex ] list1 [ secondIndex ] = temp numbers = [ 99 , 44 , 6 , 2 , 1 , 5 , 63 ...

Here is how to sort using Merge Sort method in Python. Run the code here:  https://repl.it/@VinitKhandelwal/merge-sort #mergeSort function to break lists into halves def mergeSort ( list1 ): # if list size is just 1 then no sorting required length = len ( list1 ) if length < 2 : return list1 # cutting lists into middle middle = int ( length/ 2 ) left = list1 [ 0 : middle ] right = list1 [ middle :] #first mergeSort until splitted completely, then merge return merge ( mergeSort ( left ), mergeSort ( right )) # merge function to merge back all splitted lists def merge ( left , right ): result = [] leftIndex = 0 rightIndex = 0 # compare and merge while leftIndex < len ( left ) and rightIndex < len ( right ): if left [ leftIndex ] < right [ rightIndex ]: result.append ( left [ leftIndex ]) leftIndex += 1 else : result.append ( right [ rightIndex ]) ...

Here is how to sort using Insertion Sort in Python? Run the code here:  https://repl.it/@VinitKhandelwal/insertion-sort def insertionSort ( list1 ): n = len ( list1 ) for i in range ( 1 , n ): index = i for j in reversed ( range ( 0 , i )): if list1 [ i ] < list1 [ j ]: index = j else : break if index == i : pass else : temp = list1 [ i ] list1 [ index+ 1 : i+ 1 ] = list1 [ index : i ] list1 [ index ] = temp return list1 print ( insertionSort ([ 5 , 3 , 8 , 1 , 9 , 0 , 2 , 4 , 7 , 6 ])) print ( insertionSort ([ 9 , 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 , 0 ])) # O(n^2) OUTPUT [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] BIG O O(n^2)

Here is how to Sort using Selection Sort in Python. One function keeps moving maximum value at the end, the other moves minimum value at the beginning. Run the code here:  https://repl.it/@VinitKhandelwal/selection-sort def selectionSortMax ( list1 ): a = len ( list1 ) for i in range ( 0 , a ): high = list1 [ 0 ] high_index = 0 for j in range ( 0 , a ): if list1 [ j ] > high : high = list1 [ j ] high_index = j a -= 1 temp = list1 [ a ] list1 [ a ] = list1 [ high_index ] list1 [ high_index ] = temp return list1 def selectionSortMin ( list1 ): a = len ( list1 ) for i in range ( 0 , a ): minimum = i temp = list1 [ i ] for j in range ( i+ 1 , a ): if list1 [ j ] < list1 [ minimum ]: minimum = j list1 [ i ] = list1 [ minimum ] list1 [ minimum ] = temp return list1 print ( selectionSortMax ([ 5 , 3 , 7 , 6 , 1 ...

Here is how bubble sort works in Python. Run the code here:  https://repl.it/@VinitKhandelwal/bubblesort def bubblesort ( list1 ): a = len ( list1 ) for i in range ( 0 , a -1 ): for j in range ( 0 , a -1 ): if list1 [ j ] > list1 [ j+ 1 ]: temp = list1 [ j ] list1 [ j ] = list1 [ j+ 1 ] list1 [ j+ 1 ] = temp a -= 1 return list1 print ( bubblesort ([ 7 , 1 , 4 , 8 , 6 , 5 , 2 , 3 , 9 , 0 ])) OUTPUT [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Here is how to reverse a string using recursive function in Python. Run the code here:  https://repl.it/@VinitKhandelwal/reverseString def reverseStringIteration ( sentence ): reversed_string = "" for i in range ( 0 , len ( sentence )): reversed_string += sentence [ -1 ] sentence = sentence [: -1 ] return reversed_string def reverseStringRecursion ( sentence ): if sentence == "" : return "" else : return reverseStringRecursion ( sentence [ 1 :]) +sentence [ 0 ] print ( reverseStringRecursion ( "This is a sentence." )) print ( reverseStringIteration ( "Another sentence." )) OUTPUT .ecnetnes a si sihT .ecnetnes rehtonA

Here is how to Calculate Fibonacci using Recursive Function and Iterative Method in Python. Recursive method here is very expensive in terms of processing. For a larger number, it will hang the device. Run the code here:  https://repl.it/@VinitKhandelwal/fibonacci # Recursive - O(2^n) def fibonacciRecursive ( n ): if n < 2 : return n return fibonacciRecursive ( n -1 ) + fibonacciRecursive ( n -2 ) # Iterative - O(n) def fibonacciIterative ( n ): result = 0 now = 1 for i in range ( 1 , n+ 1 ): prev = now now = result result = prev + now return result print ( fibonacciRecursive ( 8 )) print ( fibonacciIterative ( 8 )) OUTPUT 21 21

Calculate Factorial using Recursive and Iterative Methods? Run the code here:  https://repl.it/@VinitKhandelwal/factorial # Recursive Method - O(n) def factorialRecursive ( num ): if num == 2 : return 2 return num * factorialRecursive ( num -1 ) # Iterative Method - O(n) def factorialIterative ( num ): temp = num facto = 1 for i in range ( 2 , temp+ 1 ): facto *= i return facto print ( factorialRecursive ( 5 )) print ( factorialIterative ( 5 )) OUTPUT 120 120

Here is how to write a recursion while avoiding stack overflow Run the code here: https://repl.it/@VinitKhandelwal/recursion counter = 0 def inception (): # To avoid recursion global counter print ( counter ) if counter > 3 : return "done" counter += 1 # recursion return inception () print ( inception ()) OUTPUT 0 1 2 3 4 done

Create a Graph Data Structure. Run the code here:  https://repl.it/@VinitKhandelwal/Graph class Graph : def __init__ ( self ): self .numberOfNodes = 0 self .adjacentDict = {} def addVertex ( self , node ): self .adjacentDict [ node ] = [] self .numberOfNodes += 1 def addEdge ( self , node1 , node2 ): self .adjacentDict [ node1 ] .append ( node2 ) self .adjacentDict [ node2 ] .append ( node1 ) def showConnections ( self ): for key , value in self .adjacentDict.items (): print ( f "{key}:{value}" ) obj = Graph () obj.addVertex ( 0 ) obj.addVertex ( 1 ) obj.addVertex ( 2 ) obj.addVertex ( 3 ) obj.addVertex ( 4 ) obj.addVertex ( 5 ) obj.addVertex ( 6 ) obj.addEdge ( 3 , 1 ) obj.addEdge ( 3 , 4 ) obj.addEdge ( 4 , 2 ) obj.addEdge ( 4 , 5 ) obj.addEdge ( 1 , 2 ) obj.addEdge ( 1 , 0 ) obj.addEdge ( 0 , 2 ) obj.addEdge ( 5 , 6 ) obj.showConnections () ...