AS

Question 1

How do you carry out a bubble sort?

Answer 1

Start at the first element of the list. Then compare the adjacent element to the right, if they’re in the wrong order then swap them. Then compare elements 2 and 3 and swap if needed. Continue this process of comparing and swapping until all the list is sorted

Question 2

How do you carry out a quick sort?

Answer 2

Start at the middle element in the list (right-hand one if there is no middle) and mark it as a pivot by underlining. Then retaining the order of elements put everything left of the pivot to its left and everything greater than to the right. Then box the pivot. Next pick a pivot for each of the sublists we have made using the same middle method and repeat until the list is sorted so everything has been a pivot or every sublist has length 1.

Question 3

What is the formula for working out the time of the algorithm?

Answer 3

T = f(m)/f(n) x t where f(x) is the order of the algorithm so polynomial gives f(x) = x^n or logarithmic gives f(x) = log(x)

Question 4

What is a graph?

Answer 4

A diagram consisting of nodes which can be connected by edges that may have weights on them

Question 5

What is Eulers handshaking lemma?

Answer 5

Σ deg(V) = 2 #edges

Question 6

What is a path?

Answer 6

A finite sequence of edges connecting vertices such that one vertex appears only once in the path

Question 7

What is a trail?

Answer 7

A finite sequence of edges such that no edge is visited more than once

Question 8

What is a hamiltonian cycle?

Answer 8

A closed path that passes through every vertex only once and starts and ends at the same node

Question 9

What is a tree?

Answer 9

A connected graph with no cycles

Question 10

What is a spanning tree?

Answer 10

It is a subgraph which includes all the vertices and is also a tree

Question 11

What is K_n?

Answer 11

It is a complete graph of n nodes where every node connects to every other node and so will have exactly n(n-1)/2 arcs

Question 12

What is kruskals?

Answer 12

A minimum spanning tree algorithm that lists all of the arcs in order of ascending weights and then adds each arc to the MST so long as it doesn’t make a cycle and at the end we should have an MST. We MUST list the rejects so list all the arcs and tick or cross them to indicate a selection or a rejection.

Question 13

What is prims?

Answer 13

Another minimum spanning tree algorithm in which we start at a given node, look at every arc connecting to that node and pick the one with the lowest cost. We then do this and look at every arc connecting to the now two nodes we have in our MST and select the one with the lowest cost that doesn’t make a cycle. We MUST NOT list the rejects so only list the arcs
that are selected.

https://algorithm-visualizer.org/greedy/prims-minimum-spanning-tree

Question 14

How do we do Prims on a matrix and what is the total number of comparisons?

Answer 14

Given the matrix we cross out the row of the start vertex and label it number 1 above. Then look at the lowest cost arc for the labelled columns and circle it. Then add this arc to the MST and cross out the rest of the row and number the node we crossed out. Continue this until all rows are crossed out and the circled entries will give you the arcs we need for the MST. The total comparisons is (n^3 - 7n + 6)/6

Question 15

What is a semi-Eulerian graph?

Answer 15

A connected graph with strictly one pair of odd nodes

Question 16

What is a Eulerian graph?

Answer 16

A connected graph such that all of the vertices have even degrees.

Question 17

What is the Chinese postman algorithm?

Answer 17

It finds the shortest route that travels along every arc at least once and returns to the starting point in an Eulerian graph. However in a semi-Eulerian graph we start and end at the two odd nodes. To make a graph eulerian we list the odd nodes and find every pairing of them. Then we calculate the shortest distance and hence lowest cost between each pair and sum them for the two pairs so if A,B,C,D are odd then a possible pairing is AB,CD. We then choose the pair of edges that has the lowest overall cost and add those into the graph which makes all nodes even and so we can traverse it easily.

Question 18

How do you draw a Gannt chart given the activity network?

Answer 18

The start of the blank box is the earliest event time for the activity and ends at the early time + the length of the activity. If this isn’t equal to the end time (Hence the activity isn’t critical) We draw a dashed box from the end of the blank box up to the end time of the activity. It is also convention to draw the critical path at the top of the chart

Question 19

What is a critical activity?

Answer 19

An activity is critical if the late end time - early start time - activity duration = 0

Question 20

What is the float on an activity?

Answer 20

The float is the late end - early start - duration and is the total time we can delay starting an activity such that it won’t effect the end time of the entire project