# Computer Science

##### 202 • 206 • 250

##### Pseudocode

- Binary Search
`/* * 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) { s.push(child) //add child to stack } } } //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) { q.enqueue(child) //add child to queue } } } /* * 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 void add(E element) { 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 */ void add(E element) { 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) heap.add(element) //see method above; adds and reorganizes return heap } E removeMin() { E min = heap[1] //root; index 0 not used heap[1] = 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[1], 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 //if already visited, ignore } } //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) } //if already visited, ignore } } } //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) } //if already visited, ignore } } } }`

##### Summations

$$ \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 $$ |