Part 6

Question 1

How would the expression (a+7)*b be represented in a tree?

Answer 1

times

/ \

plus id(b)

/ \

id (a) number(7)

Question 2

What is a parser?

Answer 2

A program that converts text into parse trees

Question 3

What two pieces of information does a node in a parse tree need to hold?

Answer 3

Type of node, i.e. number, identifier, Operator etc.

Value, e.g. 7, myId or +

Question 4

What are the two approaches for parse tree nodes in Java?

Answer 4

Use Object to store the data

write an abstract class and subclasses for each kind of node

Question 5

What is a graph?

Answer 5

A collection of vertices and edges where each edge connects two of the vertices

Question 6

What is the difference between a directed and undirected graph?

Answer 6

Directed - edges have direction so (u, v) is not the same as (v, u)

Undirected - edge has no direction so (u,v)==(v,u)

Question 7

What is a path from vertex v1 to vk?

Answer 7

A sequence of edges, e.g.

(v1, v2), (v2, v3), …, (vk-1, vk)

Question 8

What is a connected graph?

Answer 8

Every pair of vertices u and v has a path from u to v

I.e. you can go from any vertex to any vertex, somehow

Question 9

What is a cycle (in graphs)?

Answer 9

A non-empty path from a vertex to itself comprising distinct edges

Question 10

What is an acyclic graph?

Answer 10

A graph that contains no cycles

Question 11

What is a weighted graph?

Answer 11

A graph where each edge has some numeric value associated with it, i.e. as a measure of distance, cost or capacity

Question 12

Which letters denote the number of vertices and edges in graphs?

Answer 12

n = number vertices

e = number edges

Question 13

For any graph, what is e less than?

Answer 13

n^2

Question 14

For any undirected graph, what is e less than?

Answer 14

n^2 / 2

Question 15

For a connected graph, what is e greater than or equal to?

Answer 15

n-1

Question 16

For an acyclic graph, what is e less than?

Answer 16

n

Question 17

If a graph is connected and acyclic what is e equal to in terms of n?

Answer 17

n-1

Question 18

What are the two most common methods for representing edges in a graph?

Answer 18

Adjacency matrix

Adjacency graph

Question 19

How does an adjacency matrix work?

Answer 19

array of boolean[u][v]

cell [u][v] has the value true iff there is an edge (u,v)

Question 20

How does an adjacency list work?

Answer 20

For each vertex v, a list of its neighbours (with weights if appropriate) stored in a master list

Question 21

How many entries does an adjacency matrix contain?

Answer 21

n^2

Question 22

How many entries does an adjacency list contain?

Answer 22

n+e

Question 23

When is an adjacency list better than a matrix in terms of space?

Answer 23

When the graph is sparse

Question 24

What is a spanning tree for a connected undirected graph?

Answer 24

An acyclic connected graph whose vertices are those of the original graph and whose edges form a subset of those of the original graph.

I.e. connection between every vertex without cycles

Question 25

What is the cost of a spanning tree in a weighted connected graph?

Answer 25

The sum of all the weights of the edges in the spanning tree

Question 26

What is a minimum cost spanning tree?

Answer 26

The spanning tree for a graph with the lowest cost

Question 27

How does prims algorithm work?

Answer 27

Randomly select a vertex from the graph

while(not complete)

add the lowest cost edge connecting a connected vertex and non connected vertex to the mcst

Question 28

How many times is the body of prims algorithm executed?

Answer 28

n-1

Question 29

How is prims alrogithm made efficient?

Answer 29

For each vertex keep a record of its lowest cost connected neighbour by storing the cost. If the vertex is connected itself, put a cost of 0 and if no neighbours, -1

When an edge is added to the MCST need to update entries

Question 30

What is the time complexity of prims algorithm? Why?

Answer 30

O(n²)

Finding the lowest cost is O(n), and updating the list is O(n) so the whole loop body is O(n²)

Initialisation is O(n)

Question 31

How does kruskal’s algorithm work?

Answer 31

select the lowest cost edge from the graph

Until there are n-1 edges in the MCST:

if it won’t make the MCST cyclic, add it to the mcst

Select the next lowest edge…

Question 32

How is MCST made efficient?

Answer 32

Easily determine whether the MCST will be acyclic after adding an edge:

maintain collection of connection sets (sets of vertices that form connected subgraphs in the incomplete MCST) - if the two vertices of the new edge are both in the same connection set a cycle will be introduced

Question 33

What is the time complexity of Kruskal’s algorithm?

Answer 33

O(eloge)

Question 34

What does Dijkstra’s algorithm do?

Answer 34

Determines the shortes path from one vertex to another

Question 35

What two sets does Dijsktra’s algorithm maintain?

Answer 35

Known set - vertices to which the shortest path has been found

Frontier set - vertices to which there is an edge from one of the vertices in the known set

Question 36

What happens at each step of Dijsktra’s algorithm?