ALGORITHMS

Question 1

Pros and cons of a bubble sort

Answer 1

• Easy set of instructions
• Can check for errors on the way
• List containing n elements requires
  n-1 comparisons (max)
• Could take a long time
• Inefficient - quadratic order
  1/2[n(n-1)]

*smallest/largest number always at the end after 1st pass
EDIT
Efficient for CHECKING IF LIST IS IN ORDER - list of size n requires max n-1 comparisons

Inefficient in that carrying out a full sort requires 1/2(n)(n-1), unless list is partially/fully in order

Question 2

Describe how to carry out a bubble sort

Answer 2

(If starting at lefthand side) in first pass compare first value with second value and swap if the second is larger. Then compare the second and third value and swap if the second is larger. Repeat until the end of the list - first pass

Repeat process until list no longer changes after a pass (no swaps in a pass)

Question 3

Describe how to carry out a quicksort

Answer 3

• Select a pivot (usually midpoint of
  list)
• Write down pivot
• Write down objects greater than and
  less than the pivot, keeping them in
  a sublist
• Choose new pivot
• Apply steps to each new sublist
• Algorithm finishes when all objects
  selected as pivots

Question 4

Assumptions made when using resource histograms

Answer 4

A worker can only be assigned to one activity at a time,

A worker can start a new activity immediately after finishing an old one

One worker per activity

Question 5

What is levelling in CPA?

Answer 5

Adjusting the start/finish of an activity to accommodate restraints on resources

Question 6

Assumptions for scheduling diagrams

Answer 6

One worker per activity
Always use first available worker
If we can choose more than one activity to assign to a worker, choose the one with the lower late finish time

Question 7

How do you calculate the lower bound for the number of workers required to complete a project in its minimum time

Answer 7

Sum off all activities’ durations/ minimum finish time

Question 8

Differences between Kruskal’s and Prim’s

Answer 8

n Prim’s algorithm, the starting point can be any node, whereas Kruskal’s algorithm starts
from the arc of least weight. In Prim’s algorithm, each new node and arc is added to the
existing tree as it builds, whereas in applying Kruskal’s algorithm, the arcs are selected
according to their weight and may not be connected until the end.

Question 9

Calculating order of bubble sort

Answer 9

1st pass requires (n-1) comparisons, 2nd requires (n-2) … until only 1 comparison. so is the sum of integers up to n-1 = 1/2(n-1)((n-1)+1)

= 1/2(n-1)(n)

Question 10

Explain why the first fit bin packing algorithm has quadratic order

Answer 10

To pack the k
the item requires at most (k-1) comparisons, if every item placed so far is in a separate bin. Hence the total number of comparisons for n items is ∑ (k-1) to n

Question 11

Difference between dikstra and floyds algorithm

Answer 11

Floyd’s gives you shortest distance between any pair of vertices

Question 12

Order of prims algorithm on a graph order nxn step lvl

Answer 12

Crossing out first row means there are n-1 elements to compare, which requires (n-1) -1 comparisons. Adding second column, and crossing out second row means there are (n-2) elements in each row, however 2 columns, so in total there are ((n-2)x2 -1) comparisons, repeat this up to ((n-(n-1) x (n-1) -1). To compare values after picking the rth value, you will need r(n-r)-1 comparisons. As (n-1) vertices are picked, u get the sum of (n-r)(r) -1 up to n-1 which equals (1/6)(n^3-7n+6) so order is cubic

(Draw out matrix it helps to visualise)

Question 13

Number of arcs in a mst w n vertices

Answer 13

n-1

Question 14

Number of arcs in Kn

Answer 14

NC2 arcs

Question 15

Number of iterations required for floyds on a matrix w n vertices

Answer 15

n iterations all the same type

Question 16

What is an algorithm

Answer 16

A specific set of instructions for carrying out a procedure/solving a problem

Question 17

Applications of bubble sort

Answer 17

Can be used to perform a binary search
Can be used to find all values within a range
Used for finding medians and quartiles

Question 18

Full bin packing pros/cons

Answer 18

Likely gives optimal solution
Can be difficult + time consuming when numbers are plentiful/awkward

Question 19

How algorithms of the same order could have different runtimes

Answer 19

e.g. quadratic could be 0.5n^2 vs 100n^2

Question 20

Uses of minimum spanning trees

Answer 20

Cluster Analysis.
Real-time face tracking and verification (i.e. locating human faces in a video stream).
Protocols in computer science to avoid network cycles.
Entropy based image registration.
Max bottleneck paths.
Dithering (adding white noise to a digital recording in order to reduce distortion).

Question 21

Diff between kruskal’s and prims, + why you would use one over the other

Answer 21

To use Kruskal you have to sort all the edges into order first, this could be time consuming so Prim’s may be faster unless the edges are already sorted. Prim’s is usually faster if you have a graph with high ratio of edges to vertices

Question 22

How to carry out kruskal + prim

Answer 22

[Kruskal]
Sort all the arcs into ascending order of weight.
Select the arc of least weight to start the tree.
Consider the next arc of least weight.
If it would form a cycle with the arcs already selected reject it.
If it does not form a cycle, add it to the tree.
If there is a choice of equal arcs then consider each in turn.
Repeat step 3 until all vertices are connected.

[Prim]
1) Choose any vertex to start the tree.
2) Select an arc of least weight that joins a vertex that is already in the tree to a vertex that is not yet in the tree.
If there is a choice of arcs of equal weight, choose randomly.
3) Repeat step 2 until all the vertices are connected.

(on a matrix)
Choose any vertex to start the tree.
Delete the row in the matrix for the chosen vertex.
Number the column in the matrix for the chosen vertex
Put a ring round the lowest undeleted entry in the numbered columns (If there is an equal choice, choose randomly)
The ringed entry becomes the next arc to be added to the tree.
Repeat 2,3,4 and 5 until all rows are deleted.

Question 23

How to do dickstra

Answer 23

Label the start vertex, S with the final label, 0.
Record a working value at every vertex, Y, which is directly connected to the vertex, X, which has just received its final label.
- Working value at Y = final value at X + weight of arc XY
- If there is already a working value at Y, it is only replaced if the new value is smaller.
- Once a vertex has a final label it is not revisited and its working values are no longer considered.
3) Look at the working values at all vertices without final labels. Select the smallest working value. This now becomes the final label at that vertex. (If two vertices have the same smallest working value either may be given its final label first.)
4) Repeat 2-3 until the destination vertex T, receives its final label.
5) To find the shortest path, trace back from T to S. Given that B already lies on the route, include arc AB whenever final label of B – final label of A = weight of arc AB.

Question 24

How to do Floyd’s

Answer 24

Complete an initial distance table for the network. If there is no direct route between 2 vertices label the distance as infinity (∞)
Complete an initial route table by making every entry the same as the label at the top of the column
In the first iteration, copy the first row and the first column values of the distance table into a new table. Shade these values
Consider each unshaded position in turn. Compare the value in this position in the previous table with the sum of the corresponding shaded values.
If 𝑋+𝑌≥𝑍 then copy 𝑍 into the new table (i.e. there is no change – you keep the smallest value)
If 𝑋+𝑌<𝑍 then copy 𝑋+𝑌 into the new table and write A in the corresponding position in the route table. Once all areas of the unshaded region have been considered the first iteration is complete.
For the second iteration copy the second row and second column values of the distance table into a new table. Shade these values
Repeat step 4 with the new unshaded values. This time any changes write B in the new route table
Continue until you have complete an iteration for all vertices (n iterations for n vertices)

Question 25

Distance vs route table

Answer 25

Distance shows weight of route, Route shows what vertex to go through

Question 26

How to know if a graph is directed from looking at a final distance matrix

Answer 26

If it isn’t symmetrical about leading diagonal

Question 27

Draw a graph w 2 odd nodes that’s neither eulerian or semi eulerian

Answer 27

two dots not connected - Eulerian graphs gotta be connected