Pseudo Code Algorithms with Python

Find the largest number in a list or array of numbers.

numbers = [5,6,2,7,6,2,0,4]

max = numbers[0]

for number in numbers:

   if number > max:
       max = number

The Big-0 of this program is n O(n)

Search for a number in an array or list

Try to search and see if the number 0 is in the list or array

numbers = [5,6,2,7,6,2,0,4]

for number in numbers:
    if number == 0:
        return True

The Big-0 of this program is n O(n)

Search for a number in a Sorted array or list

Try to search to see if the number 80 is in the list or array.

the needle is the number we are searching for.

Note

We call this algorithm the binary search.

# binary search
haystack = [0,11,25,38,41,54,66,79,80,94]
needle = 80

lo = 0
hi = len( haystack )

while lo < hi:

    mid = int( (lo + hi) / 2 )

    if needle > haystack[ mid ]:
        lo = mid + 1
    elif needle < haystack[ mid ]:
        hi = mid
    else:
        print "found %d which is the %d index of the list" % ( haystack[ mid ], mid )
        break

• Worst case in 8 item list is 3 compares.
• Worst case in 16 item list is 4 compares.
• Worst case in 32 item list is 5 compares.

The Big-0 of this program is n O(logn) - base 2

This is a very good algorithm!

Bubble Sort an array or list

This is a bubble sort algo using python, don't use this in production this is for learning only!

BIGO( n^2 )

def bubsort( mylist ):
   while True:
       swapped = False
       for i in range( 0, len( mylist ) - 1 ):
           if mylist[i] > mylist[i+1]:
               temp = mylist[i]
               mylist[i] = mylist[i+1]
               mylist[i+1] = temp
               swapped = True
       if not swapped:
           break

python recursion

def gcd( x, y ):
    """Find greatest common divisor of two numbers recursion"""

    if y == 0: 
        return x
    else:
        return gcd( y, x%y )

def gcd2( x, y ):
    """find the greatest common divisor of two numebrs"""
    for i in range( 2, x ):
        if x % i == 0 and y % i == 0:
            return i; 


if __name__ == "__main__":
   print gcd( 287, 91 )
   print gcd2( 287, 91 )

: )

python heap

A heap is a binary tree where the parent is always larger than its children.

Determine the last nodes that are leaves: (total number of items / 2) - 1

def build_heap( data ):
    """Turn any array or list (data) into a heap tree"""
    j = ( len( data ) / 2 ) - 1
    i = j
    while i >= 0:
        current = data[i]
        #insert_heap( current, i , length of subtree i - 1 )
         i -= 1

Most operating systems use heap tree to manage memory.

hash table

Don't use this in production! python has a datatype called dict, use that instead!!!

This is an example of building a hash table.

1. sparse table or direct address table.

Assume that:

• Totle number of keys <= the size or the array.
• no 2 elements have the same keys.

Algorythm:

• Create A[0, max -1]
• put key x into A[x]

Example:

keys = 5,2,3,7 

A = list()
A[2] = 2
A[5] = 5
A[3] = 3
A[7] = 7

1. Hash table

Assume that:

• keys = {0,1,2,3,4,n-1}
• total numebr of keys > the size of the array

Algorythm:

• A = list(0, max -1)
• put key x into A[ hash(x) ]

hash function like md5 or sha256 hash(x) = x mod 6

If you have collisions there could be a problem.

A few 'easy' hash functions:

example = 11141874

• Truncation, choose part of the data to use for storage.

A[874] = 11141874

• Folding, split up data and add them up:

first 2 chars + last 2 chars

A[85] = 11141874

• Modular

  k mod m where m is the array size

  example m = 10

Extras

Note:

Count the total number of comparisons in terms of n.

|

for( int i = 2 ; i<= n ; i++ ){ } Worst case there will be at least two comparisons. Or at least n - 1 comparisons.

Big-O notation compared to Complexity

Always look for the worst case when finding the Big-O

• O( 1 )

• Constant complexity

• O( log n )

• Logarithmic complexity

• O( n )

• Linear complexity

• O( n log n )

• n log n complexity

• O( n^b )

• Polynomial complexity

• O( b^n ), where b>1

• Exponential complexity

• O( n! )

• Factorial complexity