decision

curved box in flow chart

start/end

rectangle in flow chart

instruction

diamond box in flow chart

decision

how to layout trace table

instruction step column

column for each variable

column for equation

new row for new step

print column

maximum number of passes needed to sort list of n items into order using bubble sort

n

circumstances in which max number of passes would be needed to sort list using bubble sort

when number at the end needs to be at the start

how to use bubble sort

compare adjacent items in a list from left to right

in order, leave

not in order, swap

list in order when a pass is completed without any swaps

how to use quick sort algorithm

select a pivot then split the items into two sub-lists

one sub-list contains items less than the pivot

the other sub-list contains items greater than the pivot

select further pivots from within each sub-list and repeat

three bin packing algorithms

first-fit

first-fit decreasing

full-bin

adv disadv first-fit bin packing algorithm

adv quick to implement

disadv unlikely to lead to a good solution

adv disadv first-fit decreasing

adv usually get fairly good solution, easy to implement

disadv may not get optimal solution

how to use full bin packing algorithm

use observation to find combinations of items that will fit in a bin. pack these first

any remaining items are packed using the first-fit algorithm

adv disadv full-bin packing

adv usually get good solution

disadv difficult to do, especially with plentiful and awkward numbers

change in run time of algorithm

if algorithm has order f(n), then increasing the size of the problem from n to m will increase the run time of the algorithm by a factor of approximately f(m)/f(n)

Define walk

route through a graph along edges from one vertex to the next

Define path

Walk where no vertex is revisited

Define cycle

Path that ends where it started

Define Hamiltonian cycle

Cycle that visits every vertex

Define trail

Walk where no edge is revisited

Define Eulerian circuit

Trail where every edge is visited and starts and ends at the same vertex

Define complete graph

Graph with every vertex connected to every vertex

Euler's handshaking lemma

Sum of vertices’ degrees = edges X 2

So you can never have odd number of odd vertices

Define classical travelling salesman problem

Each vertex visited once

Define practical traveling salesman problem

Each vertex visited at least once

Weird dummy

So that each activity can be uniquely represented in terms of its events

how start planarity

I

graph that has direction associated with edges

directed graph/digraph

define tree

connected graph with no cycles

define complete graph

every vertex directly connected by a single edge to each of the other vertices

define adjacency matrix

each entry describes number of arcs joining the corresponding vertices

define eulerian graph

contains a trail that includes every edge and starts and finishes at the same vertex

semi eulerian graph

contains a trail that includes every edge but starts and finishes at different vertices

define a tour

walk which visits every vertex, returning to its starting vertex

triangle inequality

longest side of any triangle is less than or equal to the sum of the 2 shorter sides

maximum point linear programming

last point covered by an objective line as it leaves feasible region

minimum point linear programming

first point covered by an objective line as it enters the feasible region

what do slack variables represent

amount of slack between actual quantity and maximum possible value of that quantity

what does simplex method allow u to do

determine if a particular vertex on the edge of the feasible region is optimal

decide which adjacent vertex u should move to in order to increase value of objective function

two stage simplex method

define a new objective function to minimise the sum of all the artificial variables

big M method

subtract M x (sum of artificial variables) from objective function

source node and sink node critical path analysis

start and end node

describe dummy

no time or cost

solely shows dependencies between activities

define critical activity

activity where any increase in its duration means an increase for duration of entire project

define critical path

path from source node to sink node which entirely follows critical activities

longest path contained in the network

total float of activity

amount of time that its start may be delayed without affecting duration of project

latest finish - earliest start - duration

define resource levelling

the process of adjusting the start and finish times of the activities to take into account constraints on resources

rules for scheduling

use first available worker

if there is a choice of activities for a worker, assign the one with the lowest value for its late time

lower bound for number of workers to complete a project within its critical time

sum of all activity times / critical time of project

define order of an algorithm

tells u how changes in the size of a problem affect its approximate run time

order of bubble sort

n^2

what happen when no negatives in I row but value of I isnt 0

original problem has no feasible solution

no values of x y and z that satisfy all initial constraints

how draw resource histogram

label every square

why is thingy using order of algorithm only approximation

order of X doesnt mean proportional to X (which is assumption behind answer)

merely means that dominant term is of order X