Introduction¶

1. Datastructure¶

2. Complexity¶

image source

3. Iteration, Recurrsion & Dynamic Coding¶

3.1 Factorial (Iteration)¶

In [3]:

import time as time

In [4]:

def factorial_iteration(n):
    product = 1
    for i in range(1,n+1):
        product = product*i
    return product

step 1: 1x1
step 2: 1x2
step 3: 1x2x3
.
.
step 10: 1x2x3x4x5x6x7x8x9x10

In [5]:

t1 = time.time()
p = factorial_iteration(30)
t2 = time.time()
print(p, t2-t1)

265252859812191058636308480000000 5.2928924560546875e-05

3.2 Factorial (Recursion)¶

In [6]:

def factorial_recursion(n):
    if n==1 or n==0:
        return 1
    else:
        return n*factorial_recursion(n-1)

step 1: 10x(9!)
step 2: 10x9x(8!)
step 3: 10x9x8x(7!)
.
.
step 10: 10x9x8x7x6x5x4x3x2x(1!)

In [7]:

t1 = time.time()
p = factorial_recursion(30)
t2 = time.time()
print(p, t2-t1)

265252859812191058636308480000000 7.796287536621094e-05

3.3 Factorial (Dynamic)¶

In [8]:

def factorial_dynamic(n):
    fct = [1 for i in range(n+1)]
    fct[0] =1
    fct[1] =1
    for k in range(2,n+1):
        fct[k] = k*fct[k-1]
    return fct[n]

F[0] =1
F[1] =1
F[2] = 2
F[3] = 6
.
.
.
F[10] = 10!

In [9]:

t1 = time.time()
p = factorial_dynamic(30)
t2 = time.time()
print(p, t2-t1)

265252859812191058636308480000000 6.413459777832031e-05

3.4 Fibonacy No¶

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..

$F_n = F_{n-1} + F_{n-2}$

In [24]:

def fibonacci_recursive(n): 
    if n<0: 
        print("Incorrect input") 
    # First Fibonacci number is 0 
    elif n==1: 
        return 0
    # Second Fibonacci number is 1 
    elif n==2: 
        return 1
    else: 
        return fibonacci_recursive(n-1)+fibonacci_recursive(n-2) 

In [25]:

t1 = time.time()
F = fibonacci_recursive(40)
t2 = time.time()
print(F, t2-t1)

63245986 36.67340326309204

In [26]:

FibArray = [0,1] 
  
def fibonacci_dynamic(n): 
    if n<0: 
        print("Incorrect input") 
    elif n<=len(FibArray): 
        return FibArray[n-1] 
    else: 
        temp_fib = fibonacci_dynamic(n-1)+fibonacci_dynamic(n-2) 
        FibArray.append(temp_fib) 
        return temp_fib 

In [27]:

t1 = time.time()
F = fibonacci_dynamic(40)
t2 = time.time()
print(F, t2-t1)

63245986 9.298324584960938e-05

4. Greedy and Divide & Conqure¶

4.1 Greedy algorithm: Find minimum number of currency notes and values that sum to given amount¶

In [28]:

def countCurrency(amount): 
    
    notes = [1000, 500, 200, 100, 50, 20, 10, 5, 1] 
    noteCounter = [0, 0, 0, 0, 0, 0, 0, 0, 0] 
    
    for note, j in zip(notes, noteCounter): 
        if amount >= note: 
            j = amount // note 
            amount = amount - (j * note)
            print (note ," : ", j) 

In [29]:

amount = 868
countCurrency(amount) 

4.2. Divide & Conqure: Merge Sort¶

In [42]:

def mergeSort(arr): 
    if len(arr) >1: 
        
        mid = len(arr)//2 #Finding the mid of the array 
        L = arr[:mid] # Dividing the array elements 
        R = arr[mid:] # into 2 halves 

        mergeSort(L) # Sorting the first half 
        mergeSort(R) # Sorting the second half 

        i = j = k = 0
        
        # Copy data to temp arrays L[] and R[] 
        while i < len(L) and j < len(R): 
            if L[i] < R[j]: 
                arr[k] = L[i] 
                i+=1
            else: 
                arr[k] = R[j] 
                j+=1
            k+=1

        # Checking if any element was left 
        while i < len(L): 
            arr[k] = L[i] 
            i+=1
            k+=1

        while j < len(R): 
            arr[k] = R[j] 
            j+=1
            k+=1

In [43]:

arr = [12, 11, 13, 5, 6, 7] 
print ("Given array is", end="\n") 
print(arr) 
mergeSort(arr) 
print("Sorted array is: ", end="\n") 
print(arr) 

Given array is
[12, 11, 13, 5, 6, 7]
Sorted array is: 
[5, 6, 7, 11, 12, 13]

In [ ]: