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.

## 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.

## Unordered List

### Notice

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.

## 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.

TODO

# Search

### Recursion

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.

# Tree

## 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 :

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