D1

Question 1

What is a bubble sort?

Answer 1

Comparing adjacent items in a list

Question 2

Explain how to do a quick sort?

Answer 2

Split list in half, keeping order write numbers below and above, then repeat

Use (n+1)/2 and round up

Question 3

Explain how to do a binary search?

Answer 3

1) Split ordered list in half ((n+1)/2 and round up)
2a) If T=m search is complete
2b) If Tm discard useless half and repeat until T is found

Question 4

How do you find the maximum iterations needed for a binary search?

Answer 4

Use log2^n and round up

Question 5

How do you find the lower bound for bin packing?

Answer 5

Sum of heights/bin heights and round up?

Question 6

Explain first fit bin packing and advantage and disadvantage?

Answer 6

• take items in given order, starting with 1 bin go along list putting all items into first available bin

Advantage: quick

Disadvantage: unlikely to lead to a good solution

Question 7

Explain first fit decreasing bin packing and advantage and disadvantage?

Answer 7

Same as first fit but order items largest to smallest first

A: good solution/easy to do

D: not optimal solution

Question 8

Explain full bin packing and advantage and disadvantage?

Answer 8

Use observation to find combinations to fill a bun + pack these first

A: often good/optimal solution

D: difficult + takes a long time

Question 9

When is the solution optimal for bin packing?

Answer 9

When no. of bins used = lower bound

Question 10

What is a graph?

Answer 10

Vertices connects by edges

Question 11

What is a weighted graph?

Answer 11

When the graph has numbers on each edge

Question 12

What does Euclide algorithm find?

Answer 12

HCF

Question 13

What is a subgraph?

Answer 13

Part of a graph (same vertices and edges)

Question 14

What is a path?

Answer 14

Finite sequence of edges, no repeated vertices

Question 15

What is a walk?

Answer 15

Sequence of edges, can return to vertices once only

Question 16

What is a cycle/circuit?

Answer 16

Closed path, end vertex of the last edge is the start vertex of the first edge

Question 17

What is a connected graph?

Answer 17

A graph where a path can be found between any vertices (all connected)

Question 18

What is a loop?

Answer 18

An edge that starts and ends at the same vertex

Question 19

What is a simple graph?

Answer 19

No loops, no more than one edge connecting any pair of vertices

Question 20

What is a diagraph?

Answer 20

When edges of graph have direction

Question 21

What is a tree?

Answer 21

A graph with exactly one path between any two vertices

Question 22

What is a spanning tree?

Answer 22

A subgraph which includes all original vertices but is also a tree

Question 23

What is a bipartite graph?

Answer 23

A graph that only consists of two sets of vertices, where vertices only join vertices in the other set

Question 24

What is a complete graph?

Answer 24

Every vertex is directly connected to every other vertex

Question 25

What is a complete bipartite graph?

Answer 25

A bipartite graph where both sets are fully joined

Question 26

What are isomorphic graphs?

Answer 26

Graphs that show the same information but are drawn differently

Question 27

What is an adjacency matrix?

Answer 27

An adjacency matrix records the number of direct links between vertices

Question 28

What is a distance matrix?

Answer 28

A distance matrix records weights on each of the edges ( put - if not joined)

Question 29

Loop on adjacency matrix?

Answer 29

Counts as 2

Question 30

What is a minimum spanning tree/MST/minimum connector?

Answer 30

A spanning tree such that total length of edges is as small as possible

Question 31

Explain 4 steps of kruskals algorithm and what it does?

Answer 31

Finds the MST 1) sort edges into ascending weight order 2) select arc of least weight to start tree 3) consider next arc of least weight: - if it forms a cycle reject it - if it doesn't, add it 4) continue until all vertices are connected

Question 32

Explain 4 steps of prims algorithm and what it does?

Answer 32

Finds the MST 1) choose any vertex to start tree 2) select arc of least weight which joins vertex in the tree to a vertex not yet in the tree (if arcs have equal weight choose randomly) 3) repeat step 2 until all connected

Question 33

Why are dummies needed?

Answer 33

To show dependency when subsequent activities do not all depend on the same preceding activities To show that an activity can be uniquely represented in terms of its end events

Question 34

Two common constraints?

Answer 34

X greater than or equal to zero | Y greater than or equal to zero