decision Flashcards

1
Q

3 bin packing algorithms

A
  • first fit
  • first fit decreasing
  • full bin
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

first fit

A

consider terms in order they are given

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

first fit decreasing

A

order terms in decreasing order and then sort

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

full bin

A

find pairs that fill the bin and remaining are packed by first fit

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

how to find lower bound for optimal solution

A

sum numbers in the set and halve

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

order of an algorithm

A

if algorithm has order f(n) then increasing n to m will increase run time by factor f(m)/f(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

if increased by factor k then what is … increased by
- linear
- quadratic
- cubic

A
  • k
  • k^2
  • k^3
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

degree

A

number of edges on a vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

walk

A

route along graph from one vertex to the next

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

path

A

walk with no vertex visited more than once

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

trail

A

walk where no edge is visited more than once

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

cycle

A

walk where end vertex is the same as start vertex and no other vertex is visited more than once

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

hamiltonian cycle

A

cycle that includes every vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

loop

A

edge that starts and finishes at the same vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

simple graph

A

no loops and only one edge connecting any pair of vertices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

eulers handshaking lemma

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

tree

A

graph with no cycles

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

spanning tree

A

tree that has all the vertices of original graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

isomorphic graph

A

same info drawn differently

20
Q

adjacency matrix

A

shows number of arcs joining the vertices

21
Q

planar graph

A

no two edges meet other than at verticesp

22
Q

planarity algorithm

A

applied to a graph with a hamiltonian cycle

23
Q

mst

A

spanning tree with arc lengths as smalla s possible

24
Q

kruskals

A

makes an mst by ordering arcs into ascending order and applying them unless the arc forms a cycle

25
prims
makes an mst by starting with a given vertex and add on arc of least weight from that vertex
26
dijkstras
shortest route from starting node to any other node
27
floyds
shortest routes between all the nodes
28
eulerian graph
trail that includes every edge and starts and finishes at the same vertex, and has an even degree on all nodes
29
semi eulerian graph
trail that includes every edge and finishes at the same vertex, and has exactly 2 odd nodes
30
weight of network with all even nodes
total weight of network
31
weight of network with 2 odd nodes
total weight plus length of shortest path between 2 odd nodes
32
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
33
tour
walk which visits every vertex and returns to starting vertex
34
triangle inequality
longest side <= sum of two shorter sides
35
initial upper bound
weight of minimum spanning tree x 2
36
how to formulate a linear programming problem
- define decision variables x,y,z.... - state objective function - constraints as inequalities
37
feasible region
satisfies all constraints
38
how to make equations from <= constraints
add slack variables
39
how to make equations from >= constraints
- surplus variable + artificial
40
dummy activity
only shows dependencies on other activities
41
early event time
work source to sink
42
late event time
work sink to source
43
critical activity
if it is increased, the whole project duration is increased
44
critical path
- follows critical activities - at each node early=late
45
total float definition
- time that a project can be delayed without affecting duration of whole project
46
total float equation
latest finish time - duration - earliest start time