Basic graph theory vertex (node), edge (arc), edge weight undirected graph directed graph path in a graph cycle in a graph bi-partite graph a tree is a bi-partite graph complete graph planar graph depth-first search (traversal) in a graph (use a stack) breadth-first search (traversal) in a graph (use a queue) representation of a graph adjacency matrix useful when graph is dense ( |E| approx.= |V|^2 ) adjacency lists useful when graph is sparse ( |E| << |V|^2 ) although an undirected edge between nodes A and B is not the same theoretically as two directed edges A --> B and B --> A, we often represent them that way in adjacency lists for an undirected graph Topological sort Single Source Shortest Path algorithm for shortest paths in unweighted digraphs Dijkstra's algorithm for shortest paths in weighted digraphs Spanning tree Minimum spanning tree Kruskal's algorithm for MST Prim's algorithm for MST Uses for graphs: course prerequisite structure, maps, modeling digital networks, airline and auto routes, flow of traffic, work flow in an organization, finite state machines, document structure, hypermedia, linguistic representations, all tree uses (trees are graphs) tons and tons of stuff Euler path path through a graph that crosses each edge exactly once Euler circuit EP that begins and ends on the same node We have an efficient algorithm for finding Euler path/circuit Hamiltonian path path through a graph that visits each node exactly once Hamiltonian circuit HP that begins and ends on the same node Traveling salesman is example of Hamiltonian path/circuit No efficient (polynomial time, like O(N^2) ) algorithm is known for solving it
Sorting we can prove that no sort that uses only pairwise comparisons can do better (faster) than N log N best case. This means that all comparison sorts are Big-Omega(N log N), bounded below. They might be worse, however, and some are. bubble sort O(N^2) worst case insertion sort O(N^2) worst case works with pair-wise swaps (item with nearest neighbor) sometimes used as the "finisher" in quicksort selection sort O(N^2) worst case similar in concept to insertion sort but operationally it manipulates the array by possibly long-range swaps heap sort O(N log N) best case O(N log N) worst case O(N log N) average case merge sort O(N log N) best case O(N log N) wosrt case O(N log N) average case cost: often uses lots of extra memory, needs a second array as large as the one you are sorting quicksort O(N log N) best case O(N^2) worst case O(N log N) average case does not need much extra space get extra efficiency by cutting off recursion when the lists become smaller than, say, length 15 and then doing some other sort like insertion sort on the small lists to finish up bogosort random shuffling until you get the one that is in order O(infinity) worst case an extreme, just an illustration, not a serious shuffle sorting into buckets a way to sort in O(N) time can be used when the full range of possible input values is known allocate an array of int A and initialize all slots to 0 then when you see an input number n, do A[n]++ this seems to violate the Big-Omega(N log N) proof, but this sort does not do only pairwise comparisons. It effectively does lots of comparisons at once by putting a number right into an array slot. Since we believe TANSTAAFL, the tradeoff is that is uses lots of memory (not all array slots are filled) and you have to know in advance the range of inputs. Other O(N) sorts we can also sort N items in N time if we use parallel hardware the Big-Oh complexity results for our sort algorithms have all assumed we were running them on a single processor. sorts are either stable or unstable stable means it preserves the original order of items with the same value when there are duplicate values in the input. often a sort can be implemented to be stable or unstable, and in many cases making it stable sacrifices some efficiency bubble sort is stable insertion sort is stable selection sort as we did it in class is not stable it can be made stable with no change in Big-Oh complexity but at a cost in practical efficiency merge sort is not necessarily stable but is easy to make so (just make sure the merge takes from the left-most array if it can for duplicates) quick sort is not stable heap sort is not stable (heap is the issue) //=========================================================================== Sets and Maps ADT ops, behavior, and ways to implement them (lists, trees, hashing, etc.) //=========================================================================== Hashing, Hash Tables, Hash Maps Pigeon hole principle (chicken hole principle) Hash Table, hash function how to pick table size how to make an effective hash function what to do about collisions hash into linked lists (or other collection data structures) table size should be prime, and same the size as # elements expected probing to find an open cell in the table linear probing function quadratic probing function "expo" probing function table size should be prime, and twice the # elements expected Rehasing to extend the table size Hash Maps... storing associated information/object along with a hashed key //=========================================================================== Blockchain SHA-256 Cryptographic hash function basic block chain construction and operation nonce "mining" what it is, how it's done complexity of the hashing used in mining blocks (for Bitcoin application) //=========================================================================== binary heap a binary heap is a completely different thing from the runtime heap... runtime heap is not heap-structured, not related at all just unfortunate and maybe a bit confusing to share the name "heap" binary tree with two properties: heap order property structure property always a complete binary tree, with last level being filled from L to R but perhaps not full representation of binary heap as array heaps can be Min or Max operations: getMin (Max) O(1) worst, avg since it is at the root of the heap tree removeMin (Max) O(log N) worst case O(log N) average case add O(log N) worst case O(1) average case (75% of the heap elements in last 2 tree levels) incElt, decElt cost of searching for the Elt, then plus cost of rearranging the heap array when the priority is incremented or decremented searching the array linearly is O(N) using a HashMap (like Assn 4) is O(1) cost of rearranging the heap array in O(log N) build simple way is O(N log N) by doing N adds cleaver way is O(N) if you have all the elements on hand, use special "build" //=========================================================================== priority queue limplementing priority queue with list, BST implement priority queue using binary heap elements stored have value and priority priority is used to put elements into binary heap operations: enq: add item to PrQUE deq: take item out of the PrQUE, and that item is "highest" (or lowest) priority front: produce element from queue that has "highest" (or lowest) priority size, empty, etc... //=========================================================================== Tree representations (linked cells, implicit as array) We have represented a tree (binary tree) as -- linked cells (basic unbalanced BST, also used for balanced methods like AVL, Splay) -- array (binary heap) in array representation, the links are implicit and are obtained via array subscript arithmetic -- know why implicit, array representation works ok for binary heap, not for general case of binary tree //=========================================================================== Balanced BST Tree balancing: AVL: imbalance condition, rotations to re-balance rotations alter tree structure but maintain the order property worst case time complexity for insert, remove, contains show how AVL tree is altered by insert Binary Tree terms full, perfect, complete