Programming Foundation - Algorithms

• Common Algorithms
  • Search Algorithms
  • Sorting Algorithm
  • Computational Algorithm
  • Collection Algorithm
• Common Data Structures
  • Stacks and Queues
  • Hash Table

Common Algorithms

Search Algorithms

• find specific data in structure (i.e. a substring within a string)

Sorting Algorithm

• Take a dataset and apply a sort order on it

Computational Algorithm

• given one set of data, calcualte another (is a given number prime?)

Collection Algorithm

• work with collections of data (count specific items, navigate among data elements, filter out unwanted data etc.)

# Find the greatest common denominator of two numbers
#using Euclids Algorithm

def gcd(a, b):
  while(b != 0):
    t = a
    a = b
    b = t % b
  return a

#try out the function with few numbers
print(gcd(60,96)) #should be 12
print(gcd(20, 8)) # should be 4
print(gcd(12, 30))

12
4
6

Common Data Structures

• Arrays
• Link Lists
• Stacks and Queues
• Hash Table

# Linked list example


# the Node class
class Node(object):
    def __init__(self, val):
        self.val = val
        self.next = None

    def get_data(self):
        return self.val

    def set_data(self, val):
        self.val = val

    def get_next(self):
        return self.next

    def set_next(self, next):
        self.next = next


# the LinkedList class
class LinkedList(object):
    def __init__(self, head=None):
        self.head = head
        self.count = 0

    def get_count(self):
        return self.count

    def insert(self, data):
        new_node = Node(data)
        new_node.set_next(self.head)
        self.head = new_node
        self.count += 1

    def find(self, val):
        item = self.head
        while (item != None):
            if item.get_data() == val:
                return item
            else:
                item = item.get_next()
        return None

    def deleteAt(self, idx):
        if idx > self.count:
            return
        if self.head == None:
            return
        else:
            tempIdx = 0
            node = self.head
            while tempIdx < idx-1:
                node = node.get_next()
                tempIdx += 1
            node.set_next(node.get_next().get_next())
            self.count -= 1

    def dump_list(self):
        tempnode = self.head
        while (tempnode != None):
            print("Node: ", tempnode.get_data())
            tempnode = tempnode.get_next()


# create a linked list and insert some items
itemlist = LinkedList()
itemlist.insert(38)
itemlist.insert(49)
itemlist.insert(13)
itemlist.insert(15)

itemlist.dump_list()

# exercise the list
print("Item count: ", itemlist.get_count())
print("Finding item: ", itemlist.find(13))
print("Finding item: ", itemlist.find(78))

# delete an item
itemlist.deleteAt(3)
print("Item count: ", itemlist.get_count())
print("Finding item: ", itemlist.find(38))
itemlist.dump_list()

Stacks and Queues

Practical Applications

• Stack
  • Expression processing
  • Backtracking: browser back stack, for example
• Queue
  • Order processing
  • Messaging

# try out the Python stack functions

# create a new empty stack
stack = []

# push items onto the stack
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)

# print the stack contents
print(stack)

# pop an item off the stack
x = stack.pop()
print(x)
print(stack)

[1, 2, 3, 4]
4
[1, 2, 3]

# try out the Python queue functions
from collections import deque

# create a new empty deque object that will function as a queue
queue = deque()

# add some items to the queue
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)

# print the queue contents
print(queue)

# pop an item off the front of the queue
x = queue.popleft()
print(x)
print(queue)

deque([1, 2, 3, 4])
1
deque([2, 3, 4])

Hash Table

Some called it dictionary

• key-to-value mappings are unique
• hash tables are typically very fast
• for small dataset, arrays are ussually more effiecient
• hash table don't order entries in a predictable way

# demonstrate hashtable usage


# create a hashtable all at once
items1 = dict({"key1": 1, "key2": 2, "key3": "three"})
print(items1)


# create a hashtable progressively
items2 = {}
items2["key1"] = 1
items2["key2"] = 2
items2["key3"] = 3
print(items2)

# try to access a nonexistent key
# print(items1["key6"])

# replace an item
items2["key2"] = "two"
print(items2)

# iterate the keys and values in the dictionary
for key, value in items2.items():
    print("key: ", key, " value: ", value)

{'key1': 1, 'key2': 2, 'key3': 'three'}
{'key1': 1, 'key2': 2, 'key3': 3}
{'key1': 1, 'key2': 'two', 'key3': 3}
key:  key1  value:  1
key:  key2  value:  two
key:  key3  value:  3