decision

Question 1

3 bin packing algorithms

Answer 1

• first fit
• first fit decreasing
• full bin

Question 2

first fit

Answer 2

consider terms in order they are given

Question 3

first fit decreasing

Answer 3

order terms in decreasing order and then sort

Question 4

full bin

Answer 4

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

Question 5

how to find lower bound for optimal solution

Answer 5

sum numbers in the set and halve

Question 6

order of an algorithm

Answer 6

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

Question 7

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

Answer 7

• k
• k^2
• k^3

Question 8

degree

Answer 8

number of edges on a vertex

Question 9

walk

Answer 9

route along graph from one vertex to the next

Question 10

path

Answer 10

walk with no vertex visited more than once

Question 11

trail

Answer 11

walk where no edge is visited more than once

Question 12

cycle

Answer 12

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

Question 13

hamiltonian cycle

Answer 13

cycle that includes every vertex

Question 14

loop

Answer 14

edge that starts and finishes at the same vertex

Question 15

simple graph

Answer 15

no loops and only one edge connecting any pair of vertices

Question 16

eulers handshaking lemma

Answer 16

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

Question 17

tree

Answer 17

graph with no cycles

Question 18

spanning tree

Answer 18

tree that has all the vertices of original graph

Question 19

isomorphic graph

Answer 19

same info drawn differently

Question 20

adjacency matrix

Answer 20

shows number of arcs joining the vertices

Question 21

planar graph

Answer 21

no two edges meet other than at verticesp

Question 22

planarity algorithm

Answer 22

applied to a graph with a hamiltonian cycle

Question 23

mst

Answer 23

spanning tree with arc lengths as smalla s possible

Question 24

kruskals

Answer 24

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

Question 25

prims

Answer 25

makes an mst by starting with a given vertex and add on arc of least weight from that vertex

Question 26

dijkstras

Answer 26

shortest route from starting node to any other node

Question 27

floyds

Answer 27

shortest routes between all the nodes

Question 28

eulerian graph

Answer 28

trail that includes every edge and starts and finishes at the same vertex, and has an even degree on all nodes

Question 29

semi eulerian graph

Answer 29

trail that includes every edge and finishes at the same vertex, and has exactly 2 odd nodes

Question 30

weight of network with all even nodes

Answer 30

total weight of network

Question 31

weight of network with 2 odd nodes

Answer 31

total weight plus length of shortest path between 2 odd nodes

Question 32

route inspection algorithm

Answer 32

• 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

Question 33

tour

Answer 33

walk which visits every vertex and returns to starting vertex

Question 34

triangle inequality

Answer 34

longest side <= sum of two shorter sides

Question 35

initial upper bound

Answer 35

weight of minimum spanning tree x 2

Question 36

how to formulate a linear programming problem

Answer 36

• define decision variables x,y,z….
• state objective function
• constraints as inequalities

Question 37

feasible region

Answer 37

satisfies all constraints

Question 38

how to make equations from <= constraints

Answer 38

add slack variables

Question 39

how to make equations from >= constraints

Answer 39

• surplus variable
  + artificial

Question 40

dummy activity

Answer 40

only shows dependencies on other activities

Question 41

early event time

Answer 41

work source to sink

Question 42

late event time

Answer 42

work sink to source

Question 43

critical activity

Answer 43

if it is increased, the whole project duration is increased

Question 44

critical path

Answer 44

• follows critical activities
• at each node early=late

Question 45

total float definition

Answer 45

• time that a project can be delayed without affecting duration of whole project

Question 46

total float equation

Answer 46

latest finish time - duration - earliest start time