Theorem Names
Terms
undefined, object
copy deck
- Kuratowski's Theorem
- A graph is planar iff it does not contain a copy of K5 or K3,3
- Dijkstra's Algorithm
- For each node u not in X, define D(u) = w(s,u) (X is the set of nodes for which shortest paths have been determined)
- Type Invariant
- If during execution, an expression E is ever evaluated and its value is an object O, then the dynamic type of O is a subtype of the static type of E.
- Kruskal's algorithm
- Find a min weight edge - if it forms a cycle with edges already taken, throw it out, otherwise keep it
- Prim's algorithm
- Start with any vertex, add min weight edge extending from connected component that does not form a cycle
- Selection Sort
- Find min Swap with first element Recurse!
- Insertion Sort
- Take the next unsorted element and move it into position
- QuickSort
- Choose a pivot Partition the array/list Recurse!
- HeapSort
- Build a max/min heap Put roots into array
- MergeSort
- If length 0 or 1, already sorted Divide elements into two sub-lists Recurse each sub-list Merge sublists back into one sorted list
- Requirements to be a Tree
- |E| = |V| - 1 Connected No cycles
- Criteria for a Bipartite Graph
- 2-colorable No cycles of odd length