MWA

Question 1

Define an algorithm

Answer 1

a finite sequence of operations for carrying out a procedure or solving a problem

Question 2

define heuristic algorithm

Answer 2

a algorithm which will usually find a solution efficiently but has no guarantee it is optimal

Question 3

Are first fit and first fit decreasing heuristic or not

Answer 3

they are heuristic

Question 4

what is the worst case complexity of First fit and First fit decreasing

Answer 4

O(n²)

Question 5

What is the worse case amount of comparisons for First fit and First fit decreasing

Answer 5

1/2 n(n+1)

Question 6

What is the worse case complexity of the quick sort algorithm

Answer 6

O(n²)

Question 7

what is a pass

Answer 7

when you have completed an algorithm once

Question 8

In quick sort what is the pivot

Answer 8

The first number in each sub-list

Question 9

what is the worse case scenario number of comparisons in a quick sort

Answer 9

1/2 n(n−1)

Question 10

what is a graph

Answer 10

a set of nodes (or vertices) together with a set of arcs (or edges).

Question 11

what is a loop

Answer 11

an edge with the same vertex at both ends

Question 12

what is the order of a node

Answer 12

is the number of edges incident on it.

Question 13

how else can a graph be represented

Answer 13

by an incidence matrix.

Question 14

what is a connected graph

Answer 14

one in which every vertex is joined, directly or indirectly, to each of the other vertices.

Question 15

what is a simple graph

Answer 15

a graph with no loops and no ‘repeated’ edges.

Question 16

what is a simply connected graph

Answer 16

a graph that is both simple and connected.

Question 17

what is a tree

Answer 17

a simply connected graph with the minimum possible number of arcs and no cycles

Question 18

how many edges does a tree have based on vertices

Answer 18

n-1

Question 19

what is a complete graph

Answer 19

A simply connected graph with the maximum possible number of arcs

Question 20

How many edges does a complete graph have

Answer 20

1/2 n(n−1)

Question 21

what is a digraph

Answer 21

a graph where some of the arcs are directed. The incidence matrix for a digraph will usually not be symmetric about the leading diagonal.

Question 22

what is a bipartite graph

Answer 22

where the vertices partition into two sets and edges cannot join vertices that are in the same set.

Question 23

what is a network

Answer 23

a graph with weighted arcs

Question 24

What is the complexity of kruskal’s, prim’s and dijkstra’s algorithm

Answer 24

O(n²)

Question 25

How do you perform kruskal’s algorithm

Answer 25

• Start at smallest and work up
• No cycles allowed
  Finding MST

Question 26

How do you perform Prim’s algorithm

Answer 26

• Start anywhere (or told specific vertex)
• Select shortest edge coming out of initial vertex
• Then select edge with least weight which doesn’t create cycle from all connected vertices

Question 27

How do you perform prims algorithm with a matrix

Answer 27

• Mark stating column one and delete the corresponding row
• Select value of least weight in starting column and circle - write this value on the side
• Write 2 on the column corresponding to your chosen value and delete this row
• Now look down both columns and chose the least value -write this down
• Write 3 on new column and delete the row
• Repeat until all rows deleted

Question 28

what are Kruskal’s and prim’s a algorithms used for

Answer 28

to find the MST

Question 29

what is dijkstra’s algorithm used for

Answer 29

to find shortest distance between 2 points

Question 30

How do you perform dijkstra’s algorithm

Answer 30

• Start at given node
  
  • Look t all routes out and write down the distance from the origin to each one in the working values box
  • chose the node with the smallest working value and write down 2 in the order box and the distance in the top right box
  • Now look at all routes out of the 2nd node, write down the distance to that node + the distance in the top right of the 2nd nodes box in the new nodes working values
  • Now chose next smallest working value and write 3 on it
    Continue until all boxes filled

Question 31

how do you find the route in dijkstra’s algorithm

Answer 31

Start at end with the shortest distance
Go along each arc and subtract the weight from the shortest distance if that equals the distance top right then it is part of the route
Continue until at start

Question 32

what is dijkstra’s algorithm complexity

Answer 32

O(n²)

Question 33

• The maximum flow through a network =

Answer 33

the minimum cut

Question 34

First fit is only +