Part 6 Flashcards
How would the expression (a+7)*b be represented in a tree?
times
/ \
plus id(b)
/ \
id (a) number(7)
What is a parser?
A program that converts text into parse trees
What two pieces of information does a node in a parse tree need to hold?
Type of node, i.e. number, identifier, Operator etc.
Value, e.g. 7, myId or +
What are the two approaches for parse tree nodes in Java?
Use Object to store the data
write an abstract class and subclasses for each kind of node
What is a graph?
A collection of vertices and edges where each edge connects two of the vertices
What is the difference between a directed and undirected graph?
Directed - edges have direction so (u, v) is not the same as (v, u)
Undirected - edge has no direction so (u,v)==(v,u)
What is a path from vertex v1 to vk?
A sequence of edges, e.g.
(v1, v2), (v2, v3), …, (vk-1, vk)
What is a connected graph?
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
What is a cycle (in graphs)?
A non-empty path from a vertex to itself comprising distinct edges
What is an acyclic graph?
A graph that contains no cycles
What is a weighted graph?
A graph where each edge has some numeric value associated with it, i.e. as a measure of distance, cost or capacity
Which letters denote the number of vertices and edges in graphs?
n = number vertices
e = number edges
For any graph, what is e less than?
n^2
For any undirected graph, what is e less than?
n^2 / 2
For a connected graph, what is e greater than or equal to?
n-1
For an acyclic graph, what is e less than?
n
If a graph is connected and acyclic what is e equal to in terms of n?
n-1
What are the two most common methods for representing edges in a graph?
Adjacency matrix
Adjacency graph
How does an adjacency matrix work?
array of boolean[u][v]
cell [u][v] has the value true iff there is an edge (u,v)
How does an adjacency list work?
For each vertex v, a list of its neighbours (with weights if appropriate) stored in a master list
How many entries does an adjacency matrix contain?
n^2
How many entries does an adjacency list contain?
n+e
When is an adjacency list better than a matrix in terms of space?
When the graph is sparse
What is a spanning tree for a connected undirected graph?
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
What is the cost of a spanning tree in a weighted connected graph?
The sum of all the weights of the edges in the spanning tree
What is a minimum cost spanning tree?
The spanning tree for a graph with the lowest cost
How does prims algorithm work?
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
How many times is the body of prims algorithm executed?
n-1
How is prims alrogithm made efficient?
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
What is the time complexity of prims algorithm? Why?
O(n2)
Finding the lowest cost is O(n), and updating the list is O(n) so the whole loop body is O(n2)
Initialisation is O(n)
How does kruskal’s algorithm work?
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…
How is MCST made efficient?
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
What is the time complexity of Kruskal’s algorithm?
O(eloge)
What does Dijkstra’s algorithm do?
Determines the shortes path from one vertex to another
What two sets does Dijsktra’s algorithm maintain?
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
What happens at each step of Dijsktra’s algorithm?
