Decision maths

What is the maximum number of passes needed in a bubble sort (including the final check pass) ?

n

When does the maximum number of passes in a bubble sort occur ?

When the smallest or largest (depending on the order in which you're sorting) is at the end of the list

Where do you place an item that is of equal size to your pivot in a quick sort ?

In either sub-list

What is the maximum number of comparisons in a bubble sort ?

(n-1) lots of n all / 2

n(n-1) / 2

What is a benefit of a bubble sort vs a quick sort

It is very adaptive : it can stop early on if the list is sorted with only a few comparisons

When is a quick sort more appropriate than a bubble sort and why ?

When the list is very random : items can move further after each step thus the list is sorted faster

How do you determine if your solution is optimal e.g. in bin packing?

find the lower bound for number of bins : (total sum) / (bin size) then round up to nearest integer

In the full bin packing algorithm, once full bins have been created, what must you make sure to do with the remaining items ?

Pack them in the order they appear (first fit)

What is the max number of comparisons needed for first fit bin packing ?

to pack nth item needs (n-1) comparisons

sum of numbers 1 to (n-1) from n=1 to n : 1/2 (n-1) (n)

if f(n) is the time complexity, increasing the size from n to m increases the run time by a factor of...

f(m) / f(n)

Define a walk

A series of nodes connected by edges

Define a path

A series of nodes connected by edges where no vertex is repeated

Define trail in terms of a walk

A walk where no edge is repeated

Define cycle in terms of a walk

A walk that begins and ends at the same vertex and no node is visited more than once

Define Hamiltonian cycle in terms of a walk

A walk which begins and ends at the same vertex and visits every node exactly once

Define simple graph

A graph with no loops; at most one edge connecting any pair of vertices

Euler's handshake lemma

in an undirected graph, the sum of degrees of the vertices is 2 * the number of edges

Thus the number of odd vertices is even

Define spanning tree

A subgraph that contains every node and is also a tree

Define complete graph

Every vertex is connected to every other vertex by a single edge : notation is kn

graph must be undirected

What are the conditions for isomorphic graphs?

same number of vertices of the same degree,

connected in the same way e.g. vertex of valency 3 connected to a vertex of valency 2

What do you put in an adjacency matrix to represent a loop ?

2 (providing loop can be travelled in both directions)

What do cells in an adjacency matrix represent?

Connections between nodes

What do entries in distance matrices represent ?

weights of arcs

What should you put in a distance matrix for the cells e.g. A->A if there is no loop

-

What should you put if there is no connected between two different nodes e.g. A->B in a distance matrix ?

infinity symbol

How can you tell if a graph is undirected ?

"symmetrical about the leading diagonal"

What must you remember to show when doing Kruskal's ?

The order in which you consider the nodes and if you have added or rejected them

What is a minimum spanning tree?

A spanning tree where the total length of its arcs are as small as possible

State the two differences between Prim's and Kruskal's

Prim's adds vertices but Kruskal's adds edges.

There is always a tree at any given point in Prim's

How can you approach a question that needs Dijkstra's but has two "start" vertices and one "end" vertex ?

Begin at the end

What two tables will you have when doing Floyd's ?

Distance table and route table

How many comparisons are there per row in Floyd's ?

(n-1)(n-2) : (n-1) rows, (n-2) columns (because the leading diagonal makes a column but we need to exclude it)

In the route inspection algorithm, what must we assume about somebodies route unless told otherwise ?

They begin and end at the same vertex

How can you use an adjacency matrix to find the valency for each node?

Add up the entries in a row for a given node for the valency of that node

What do you need to remember to do in Dijkstra's / Route inspection / Spanning tree Qs etc in terms of your final answer ?

Give route

Give length

Check units

True or False: You should include derived constraints in the constraints list for linear programming ?

False!!!! Only include given constraints (and x,y >= 0 if appropriate)

If I sell cakes and brownies and I want to maximise profits each day, how could I define my decision variables ?

let x = the number of cakes sold per day

let y = the number of brownies sold per day

(make sure to be specific)

True or False : The coordinates of the optimal point always give the optimal solution that we will use ?

False : sometimes the variables must be integers

What do we call the start/end node in activity networks ?

source/sink

What do we need to put on arcs in activity networks?

ARROWS

What do early event times represent ?

The earliest that the following activity can begin / earliest that all preceding activities have completed

What do late event times represent ?

The latest the following activity can begin without delaying the overall project time

Give the two reasons we may need a dummy activity

1) two activities would otherwise begin and end at the same event

2) C depends on A and B but D depends only on A

Define Critical acitvity

An activity is critical if any increase in its duration increases the total time for the whole project

How do you locate critical activities ?

They sit on critical paths

(and will always be between critical events)

What does 3 indicate on a Gantt chart in hours ?

3 hours have elapsed,

The 4th hour is about to begin