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
prims
makes an mst by starting with a given vertex and add on arc of least weight from that vertex
dijkstras
shortest route from starting node to any other node
floyds
shortest routes between all the nodes
eulerian graph
trail that includes every edge and starts and finishes at the same vertex, and has an even degree on all nodes
semi eulerian graph
trail that includes every edge and finishes at the same vertex, and has exactly 2 odd nodes
weight of network with all even nodes
total weight of network
weight of network with 2 odd nodes
total weight plus length of shortest path between 2 odd nodes
route inspection algorithm
- identify vertices with odd degree
- consider all possible complete pairings of these vertices
- select pairing with the least sum
- add a repeat of the arcs indicated by this pairing
tour
walk which visits every vertex and returns to starting vertex
triangle inequality
longest side <= sum of two shorter sides
initial upper bound
weight of minimum spanning tree x 2
how to formulate a linear programming problem
- define decision variables x,y,z….
- state objective function
- constraints as inequalities
feasible region
satisfies all constraints
how to make equations from <= constraints
add slack variables
how to make equations from >= constraints
- surplus variable
+ artificial
dummy activity
only shows dependencies on other activities
early event time
work source to sink
late event time
work sink to source
critical activity
if it is increased, the whole project duration is increased
critical path
- follows critical activities
- at each node early=late
total float definition
- time that a project can be delayed without affecting duration of whole project
total float equation
latest finish time - duration - earliest start time
