Algorithm in Python Notes

Learning Python Algorithm Notes

Linear Structures

What distinguishes one linear structure from another is the way in which items are added and removed, in particular the location where these additions and removals occur.

Stack

Queue

Hot Potatoes (Josephus) Question

To simulate the circle, we will use a queue. Assume that the child holding the potato will be at the front of the queue. Upon passing the potato, the simulation will simply dequeue and then immediately enqueue that child, putting her at the end of the line. She will then wait until all the others have been at the front before it will be her turn again. After num dequeue/enqueue operations, the child at the front will be removed permanently and another cycle will begin. This process will continue until only one name remains.

class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)


def hotPotato(nameList, num):
    simuQueue = Queue()
    for name in nameList:
        simuQueue.enqueue(name)
    while simuQueue.size() > 1:
        for i in range(num):
            simuQueue.enqueue(simuQueue.dequeue())
        simuQueue.dequeue()
    return simuQueue.dequeue()

print(hotPotato(['Bill', 'David', 'Susan', 'Jane', 'Kent', 'Brad'], 7))

Unordered List

Notice

class ClassName:
   ...
   self.parameterName
   parameterName

Notice the self in class definition.

Recursion

The Three Laws of Recursion

1. A recursion algorithm must have a base case.
2. A recursion algorithm must change its state and move toward the base case.
3. A recursion algorithm must call itself, recursively.

A base case is the condition that allows the algorithm to stop recusing. A base case is typically a problem that is small enough to solve directly.

To obey the second law, we must arrange for a change of state that moves the algorithm toward the base case. A change of state means that some data that the algorithm is using is modified. Usually the data that represents our problem gets smaller in some way.

Converting an Integer to a String in Any Base

def baseConvert(n, base):
    convertStr = "0123456789ABCDEF"
    if n < base:
        return convertStr[n]
    else:
        return baseConvert(n//base, base) + convertStr[n%base]

print(baseConvert(1453, 16))
print(baseConvert(10, 2))

Hanoi Tower

Here is a high-level outline of how to move a tower from the starting pole, to the goal pole, using an intermediate pole:

1. Move a tower of height-1 to an intermediate pole, using the final pole.
2. Move the remaining disk to the final pole.
3. Move the tower of height-1 from the intermediate pole to the final pole using the original pole.

def hanoiTower(height, fromPole, toPole, withPole):
    if height >= 1:
        hanoiTower(height-1, fromPole, withPole, toPole)
        print(fromPole + ' -> ' + toPole)
        hanoiTower(height-1, withPole, toPole, fromPole)

hanoiTower(3, 'A', 'B', 'C')

Exploring a Maze

def searchFrom(maze, startRow, startColumn):
    # try each of four directions from this point until we find a way out.
    # base Case return values:
    #  1. We have run into an obstacle, return false
    maze.updatePosition(startRow, startColumn)
    if maze[startRow][startColumn] == OBSTACLE :
        return False
    #  2. We have found a square that has already been explored
    if maze[startRow][startColumn] == TRIED or maze[startRow][startColumn] == DEAD_END:
        return False
    # 3. We have found an outside edge not occupied by an obstacle
    if maze.isExit(startRow,startColumn):
        maze.updatePosition(startRow, startColumn, PART_OF_PATH)
        return True
    maze.updatePosition(startRow, startColumn, TRIED)
    # Otherwise, use logical short circuiting to try each direction
    # in turn (if needed)
    found = searchFrom(maze, startRow-1, startColumn) or \
            searchFrom(maze, startRow+1, startColumn) or \
            searchFrom(maze, startRow, startColumn-1) or \
            searchFrom(maze, startRow, startColumn+1)
    if found:
        maze.updatePosition(startRow, startColumn, PART_OF_PATH)
    else:
        maze.updatePosition(startRow, startColumn, DEAD_END)
    return found

Dynamic Programming

TODO

Search

Sequential Search

def unorderedSequentialSearch(unorderedList, item):
    pos = 0
    found = False
    while pos < len(unorderedList) and not found:
        if unorderedList[pos]==item:
            found = True
        else:
            pos += 1
    return found

testList = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(unorderedSequentialSearch(testList, 3))
print(unorderedSequentialSearch(testList, 13))

def orderedSequentialSearch(orderedList, item):
    pos = 0
    found = False
    stop = False
    while pos < len(orderedList) and not found and not stop:
        if orderedList[pos] == item:
            found = True
        elif orderedList[pos] > item:
            stop = True
        else:
            pos += 1

    return found

anOrderedList = [0, 1, 2, 8, 13, 17, 19, 32, 42]
print(orderedSequentialSearch(anOrderedList, 3))
print(orderedSequentialSearch(anOrderedList, 13))

Binary Search

Loop

def binarySearch(orderedList, item):
    first = 0
    last = len(orderedList)
    found = False
    while first <= last and not found:
        middle = (first+last)//2
        if orderedList[middle] == item:
            found = True
        elif item < orderedList[middle]:
            last = middle - 1
        else:
            first = middle + 1

    return found

Recursion

def recurBinarySearch(orderedList, item):
    if len(orderedList) == 0:
        return False
    else:
        middle = len(orderedList)//2
        if orderedList[middle] == item:
            return True
        elif item < orderedList[middle]:
            return recurBinarySearch(orderedList[:middle], item)
        else:
            return recurBinarySearch(orderedList[middle+1:], item)

Notice: [:middle] and [middle+1:]

Hash

Resolve collision

The general name for this process of looking for another slot after a collision is rehashing. With simple linear probing, the rehash function is newhashvalue=rehash(oldhashvalue)
where rehash(pos)=(pos+1)%sizeoftablere. The “plus 3” rehash can be defined as rehash(pos) = (pos+3)%sizeoftable.

In general, rehash(pos) = (pos+skip)%sizeoftable.

_It is important to note that the size of the “skip” must be such that all the slots in the table will eventually be visited._ Otherwise, part of the table will be unused. To ensure this, it is often suggested that the table size be a prime number. This is the reason we have been using 11 in our examples.

Sort

Tree

Tree Traversals

Binary Search Tree

Definition

A binary search tree is a rooted binary tree, whose internal nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right. The tree additionally satisfies the binary search tree property, which states that the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to (to be decided) any key stored in the right sub-tree.

In the implementation of the class TreeNode, the definition of isLeftChild() method :

def isLeftChild(self):
        return self.parent and self.parent.leftChild == self

Why we should use self.parent and ... , because this ensure the node is not the root.

Graph