AS Flashcards
How do you carry out a bubble sort?
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
How do you carry out a quick sort?
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.
What is the formula for working out the time of the algorithm?
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)
What is a graph?
A diagram consisting of nodes which can be connected by edges that may have weights on them
What is Eulers handshaking lemma?
Σ deg(V) = 2 #edges
What is a path?
A finite sequence of edges connecting vertices such that one vertex appears only once in the path
What is a trail?
A finite sequence of edges such that no edge is visited more than once
What is a hamiltonian cycle?
A closed path that passes through every vertex only once and starts and ends at the same node
What is a tree?
A connected graph with no cycles
What is a spanning tree?
It is a subgraph which includes all the vertices and is also a tree
What is K_n?
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
What is kruskals?
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.
What is prims?
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
How do we do Prims on a matrix and what is the total number of comparisons?
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
What is a semi-Eulerian graph?
A connected graph with strictly one pair of odd nodes
What is a Eulerian graph?
A connected graph such that all of the vertices have even degrees.
What is the Chinese postman algorithm?
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.
How do you draw a Gannt chart given the activity network?
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
What is a critical activity?
An activity is critical if the late end time - early start time - activity duration = 0
What is the float on an activity?
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
