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.


Unordered List
Notice


Notice the self
in class definition.
Recursion
The Three Laws of Recursion
 A recursion algorithm must have a base case.
 A recursion algorithm must change its state and move toward the base case.
 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


Hanoi Tower
Here is a highlevel outline of how to move a tower from the starting pole, to the goal pole, using an intermediate pole:
 Move a tower of
height1
to an intermediate pole, using the final pole.  Move the remaining disk to the final pole.
 Move the tower of
height1
from the intermediate pole to the final pole using the original pole.


Exploring a Maze


Dynamic Programming
TODO
Search
Sequential Search


Binary Search
Loop


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.
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 subtrees, 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 subtree, and less than or equal to (to be decided) any key stored in the right subtree.
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.