decision Flashcards
3 bin packing algorithms
- first fit
- first fit decreasing
- full bin
first fit
consider terms in order they are given
first fit decreasing
order terms in decreasing order and then sort
full bin
find pairs that fill the bin and remaining are packed by first fit
how to find lower bound for optimal solution
sum numbers in the set and halve
order of an algorithm
if algorithm has order f(n) then increasing n to m will increase run time by factor f(m)/f(n)
if increased by factor k then what is … increased by
- linear
- quadratic
- cubic
- k
- k^2
- k^3
degree
number of edges on a vertex
walk
route along graph from one vertex to the next
path
walk with no vertex visited more than once
trail
walk where no edge is visited more than once
cycle
walk where end vertex is the same as start vertex and no other vertex is visited more than once
hamiltonian cycle
cycle that includes every vertex
loop
edge that starts and finishes at the same vertex
simple graph
no loops and only one edge connecting any pair of vertices
eulers handshaking lemma
in an undirected graph the sum of the degrees of the vertices are 2x the number of edges so number of odd nodes must be even
tree
graph with no cycles
spanning tree
tree that has all the vertices of original graph
isomorphic graph
same info drawn differently
adjacency matrix
shows number of arcs joining the vertices
planar graph
no two edges meet other than at verticesp
planarity algorithm
applied to a graph with a hamiltonian cycle
mst
spanning tree with arc lengths as smalla s possible
kruskals
makes an mst by ordering arcs into ascending order and applying them unless the arc forms a cycle