# Computer Science

##### 202 • 206 • 250 ##### Pseudocode
• /*
* log in the context of this file shall refer to log of base 2
*
* For a Binary Tree of n nodes, the height is log(n) at best and n at worst
* It will have 1 root, n - 1 children, and n - 1 edges
*/

public class BinarySearch {
/*
* O(log(n)) -> halving size of list each time
*/

//iterative
int binarySearch(list, value) {
low = 0
high = list.size - 1
while (low <= high) {
mid = (low + high) / 2
if (value == list[mid]) //value found
return mid
if (value < list[mid])
high = mid - 1 //value is in lower half
else
low = mid + 1 //value is in upper half
} //if range is negative, value does not exist
return -1
}

//recursive
int binarySearch(list, value, low, high) {
if (low > high) return -1 //invalid range
mid = (low + high) / 2
if (value == list[mid]) //value found
return mid
if (value < list[mid]) //value is in lower half
return binarySearch(list, value, low, mid - 1)
else //value is in upper half
return binarySearch(list, value, mid + 1, high)
}

//initial call
binarySearch(list, value, 0, list.size -1)
}
• Binary Search Tree
/*
* log in the context of this file shall refer to log of base 2
*
* A Binary Search Tree (BST)
*      is a binary tree
*      has unique and comparable keys
*      has nodes where
*          every descendent on the left is smaller
*          every descendent on the right is larger
* Best case for searching is O(1) (root.key == key)
* Worst case for a well sorted tree is O(logn)
*      height of BST is logn, and one of the leaves has the right key
* In an unbalanced tree, height is n, so true worst case is O(n)
*/

public class BinarySearchTree {
Node find(Node root, E key) {
if (root == null) return null //no node
if (root.key = key) return root //key matches
if (root.key < key) return find(root.right, key) //key bigger -> right side
return find(root.left, key) //key smaller -> left side
}

//notice that every left child is smaller than its parent
Node findMin(Node root) {
if (root == null) return null //no node
if (root.left == null) return root //no left child
return findMin(root.left) //go into left child and continue
}

//notice that every right child is greater than its parent
Node findMin(Node root) {
if (root == null) return null //no node
if (root.right == null) return root //no right child
return findMin(root.right) //go into right child and continue
}

//note that every new key will be added as a leaf
Node add(Node root, E key) {
if (root == null) {
root = new BSTNode(key) //create new node with key
} else if (key < root.key) {
root.left = add(root.left, key) //key smaller; continue on left
} else if (key > root.key) {
root.right = add(root.right, key) //key bigger; continue on right
} //if root.key = key, do nothing
return root
}

Node remove(Node root, E key) {
if (root == null) return null
if (key < root.key) { //key smaller; treat left child as root
root.left = remove(root.left, key)
} else if (key > root.key) { //key bigger; treat right child as root
root.right = remove(root.right, key)
} else if (root.left == null) {
//keys match; only right child exists; bring right child to root
root = root.right
} else if (root.right == null) {
//keys match; only left child exists; bring left child to root
root = root.left
} else {
// min key of root.right is guaranteed to be
// > current root.left and <= current root.right
// it therefore will not ruin the ordering of the BST
// if it is moved up to root
Node min = findMin(root.right)
root.key = min.key
min = null
}
return root
}
}
• Tree Traversal
/*
* Terms
*
* Root             node from which all descendents stem
* Child            node with a parent
* Edge             line connecting parent with child
* Leaf             node without any children
*
* Height           maximum path length from that node to a leaf; leaves have height 0
* Depth/Level      number of edges from that node to root; root has depth 0
*
* Depth first      all descendents of node visited before next sibling
* Breadth first    all nodes of current depth visited before next depth
*
* Preorder         node visited before all children of that node
* Inorder          node visited after all left children and before all right children
* Postorder        node visited after all children of that node
*
* Prefix           *ab     operation first         aka Polish Notation
* Infix            a*b     operation in middle
* Postfix          ab*     operation last          aka Reverse Polish Notation
*/

public class TreeTraversal {

//postorder recursive
void depthFirst(Node root) {
if (root != null) {
for (Node child : root) {
depthFirst(child)
}
}
root.visit() //do what you need to do with current node
//for preorder, visit root before calling depthFirst again (right after root != null)
}

//depth first iterative right to left
void treeTraversalStack(Node root) {
Stack s = new Stack();
s.push(root)
while (!s.isEmpty()) {
Node cur = s.pop()
cur.visit() //visit latest node
for (Node child : cur) {
}
}
}

//breadth first iterative left to right
void treeTraversalQueue(Node root) {
Queue q = new Queue()
q.enqueue(root)
while (!q.isEmpty()) {
Node cur = q.dequeue()
cur.visit() //visit latest node
for (Node child : cur) {
}
}
}

/*
* We typically loop through children with for each child
* With first child, next sibling, it is like so:
*/
void firstChildNextSibling(Node cur) {
Node child = cur.firstChild
while (child != null) {
child.visit()
child = child.nextSibling
}
}
}
• Heaps
/*
* Priority Queues - each node is smaller than all of its descendents
*      root is therefore the smallest element
* Complete Binary Tree - binary tree with all levels above the lowest one full
*      and with all elements in the lowest level as left as possible
* Heaps can be visualized as trees, but can also be represented with arrays
*      if we number the nodes 1 through n, starting from the root and travelling breadth first,
*      the numbers will represent their indices in the array (0 is not used for convenience)
*      the left child of node k is therefore at 2k, and the right child is at 2k + 1
*/

public class Heap {

//add element at end then reorganize with upHeap
Node cur = newLastNode() //Node on lowest level right of the last existing node
cur.element = element
while (cur != root && cur.element < cur.parent.element) {//Node is smaller than parent
swapElement(cur, parent) //switch values
cur = cur.parent //go up a level
}
}

//remove root, replace with last node, then reorganize with downHeap
E removeMin() {
E min = root.element //this is the smallest element
Node cur = root //just a name change; currently refers to root
cur.element = getLastNode().element //Get element of rightmost node on last level
getLastNode() = null //last node has moved and no longer exists
while (cur.leftChild != null) { //if null, there are no children
if (cur.leftChild.element < cur.element) {
swapElement(cur, cur.leftChild) //left child smaller; swap
cur = cur.leftChild
} else if (cur.rightChild != null && cur.rightChild.element < cur.element) {
swapElement(cur, cur.rightChild) //right child smaller; swap
cur = cur.rightChild
}
}
return min
}

/*
* Equivalent methods but in an array implementation
*/
size++ //it is assumed the array can fit this size
heap[size] = element //size matches last index as 0 is not used
i = size //iterate through 'parent nodes'
while (i > 1 && heap[i] < heap[i / 2]) {
swapElements(heap[i], heap[i / 2])
i /= 2
}
}

/*
* Create heap from unsorted list
* Best case is O(n) -> already a heap
* Worst case is O(nlogn) -> move every item at k floor(logk) steps up
*/
Heap buildHeap(list) {
heap = new Heap(list.size)
for (E element : list)
return heap
}

E removeMin() {
E min = heap //root; index 0 not used
heap = heap[size]
heap[size] = null //element moved
size--
downHeap(1, size)
return min
}

/*
* Moves element at index i to appropriate position within the heap
*/
void downHeap(i, size) {
while (2 * i <= size) { //left child exists
child = 2 * i
if (child < size) { //right child exists
if (heap[child + 1] < heap[child]) //right child smaller
child++ //child is now indexed at smallest of the two children
}
if (heap[child] < heap[i]) { //child smaller than current
swapElements(heap[child], heap[i])
i = child
}
}
}

//you can actually use heaps to sort your values
E[] heapSort(list) {
heap = buildHeap(list)
E[] sorted = new E[list.size + 1]
for (i = 1 to list.size){
sorted[size - i] = heap.removeMin() //add min from left to right
}
return sorted
}

//sort within same array
E[] heapSort(E[] arr) {
heap = buildHeap(arr)
for (i = 1 to list.size){
swapElements(heap, heap[size + 1 - i]) //smallest element of subarray is moved to the back
downHeap(1, size - i) //shift root element down, bringing next smallest to root
}
return reverse(heap) //reverse for small to large
}

/*
* Previous methods rely on add(E), which uses upHeap
* As half the elements are on the bottom row, it is much more efficient to downHeap
* We start at k = size/2 because all k's greater are already at smallest height
* Algorithm is O(n)
* t(n) = Sigma(i = 0 -> n)(height of node i) = n - log(n + 1)
*/
buildHeapFast(list) {
for(k = size/2; k >= 1; k--)
downHeap(k, size)
}
}
• Graphs
/*
* Terms
* Vertex           'node', contains information for a given point
* Edge             set of ordered pairs of vertices
* Degree           # of edges attached to vertex (going in or out)
* Path             sequence of vertices where every neighbouring vertex has an edge connecting them
* Cycle            path such that last vertex is the same as the first vertex
*
* Directed graph   set of vertices
* Undirected graph graph where edges are unordered pairs
* Acyclic graph    graph with no cycles (the case for dependencies; you can't have A depend on B and B depend on A)
*/

public class Graph {

//depth first recursive graph traversal
void depthFirst(Vertex v) {
v.visited = true //indicate that we've visted the vertex so we don't do it twice
//make sure that visited is false for all vertices before starting this traversal
//do stuff with current vertex here
for (Edge e : v.edges) { //loop through all edges
Vertex v2 = e.endVertex //get connected vertex from respective edge
if (!v2.visited) depthFirst(v2); //recursive call
}
}

//depth first iterative traversal using a stack
void graphTraversalStack(Vertex v) {
Stack s = new Stack();
v.visited = true
s.push(v)
while (!s.isEmpty()) {
Vertex v2 = s.pop()
//do stuff with vertex here
for (Edge e : v2.edges) { //loop through all edges
Vertex w = e.endVertex //get connected vertex from respective edge
if (!w.visited) {
w.visited = true
s.push(w)
}
}
}
}

//breadth first iterative traversal using a queue
void graphTraversalQueue(Vertex v) {
Queue q = new Queue()
v.visited = true
q.enqueue(v)
while (!q.isEmpty()) {
Vertex v2 = q.dequeue()
//do stuff with vertex here
for (Edge e : v2.edges) { //loop through all edges
Vertex w = e.endVertex //get connected vertex from respective edge
if (!w.visited) {
w.visited = true
q.enqueue(w)
}
}
 $$\sum_{i=1}^{n} i$$ $$\frac{n(n+1)}{2}$$ $$\sum_{i=1}^{n} i^2$$ $$\frac{n(n+1)(2n+1)}{6}$$ $$\sum_{i=1}^{n} i^3$$ $$\frac{n^2(n+1)^2}{4}$$ $$\sum_{i=0}^{n-1} c^i$$ $$\frac{c^n - 1}{c-1}$$ $$\sum_{i=0}^n 2^i$$ $$2^{n+1} - 1$$ $$\sum_{i=0}^{n-1} i * 2^i$$ $$2 + (n - 2)2^n$$