Unit 5 Flashcards
Show the order the nodes of the attached tree will be visited in a breadth first search.
Select the lists of nodes that represent possible orderings of vertices as visited in a depth first search of the attached directed acyclic graph.
- [E, B, T, F, M, A, L, R]
- [E, L, R, A, M, B, T, F]
- [E, L, B, A, R, F, T, M]
- [E, L, A, B, R, M, F, T]
- [E, A, M, B, F, T, L, R]
- [E, B, F, T, A, L, M, R]
[E, L, R, A, M, B, T, F]
See Exploratory Activity 5.6 for a visualisation of how a depth first search of a graph works:
https://learn2.open.ac.uk/mod/oucontent/view.php?id=734611§ion=1.1
Create an adjacency list for the attached graph.
A: [B, D]
B: [C]
C: [A, H]
D: [A, C]
E: [C, G]
F: [D, E]
G: [E]
H: []
Complete the following statement, using the labels below:
The _____ problem can be represented as a _____ graph with the _____ corresponding to the _____ between vertices. The version of this problem discussed in the module texts aims to find a _____ with the minimum distance from a given _____ (the source) to each other vertex in the graph. There is a classic way to solve this known as _____ algorithm.
The algorithm uses a _____ data structure. To start the algorithm, we set the source distance to _____ and the other vertex distances to _____ and then add all the vertices to the structure, sorted by _____. We then follow a series of other steps to obtain the required solution.
- -999
- -1
- 0
- 1
- adjacency list
- current distance
- Dijkstra’s
- distances
- Grundy’s
- Hash Map
- infinity
- List
- new distance
- path
- Prim’s
- Priority Queue
- shortest path
- start vertex
- TSP
- weighted
- weights
The shortest path problem can be represented as a weighted graph with the weights corresponding to the distances between vertices. The version of this problem discussed in the module texts aims to find a path with the minimum distance from a given start vertex (the source) to each other vertex in the graph. There is a classic way to solve this known as Dijkstra’s algorithm.
The algorithm uses a Priority Queue data structure. To start the algorithm, we set the source distance to 0 and the other vertex distances to infinity and then add all the vertices to the structure, sorted by current distance. We then follow a series of other steps to obtain the required solution.
How does dynammic programming work?
Dynamic programming works by splitting a problem up into subproblems and then solving these problems in topologically sorted order, which can be represented by a DAG.
This means that as we come to each new subproblem all the other subproblems it relies on have already been solved.
Which of the sequences below represent a topological sort of the attached tasks:
- [TA, TB, TC, TD, TE, TF, TG, TH]
- [TG, TA, TC, TD, TE, TB, TF, TH]
- [TA, TG, TB, TC, TD, TE, TF, TH]
- [TG, TA, TB, TF, TH, TC, TD, TE]
- [TG, TA, TB, TC, TF, TD, TE, TH]
- [TH, TF, TE, TD, TC, TB, TG, TA]
- [TA, TG, TB, TC, TD, TE, TF, TH]
- [TG, TA, TB, TC, TF, TD, TE, TH]
- Identify a vertex with no incoming edges and add it to the topological sort (task TA or TG in this example)
- Remove that vertex and all its outgoing edges from the graph
- Repeat these steps until all vertices have been removed
Find a topological sort for the attached directed acyclic graph (DAG).
Any of these are valid:
- [4, 3, 1, 6, 2, 5]
- [4, 3, 1, 6, 5, 2]
- [4, 3, 6, 1, 2, 5]
- [4, 3, 6, 5, 1, 2]
- Identify a vertex with no incoming edges and add it to the topological sort (task TA or TG in this example)
- Remove that vertex and all its outgoing edges from the graph
- Repeat these steps until all vertices have been removed
What is the goal of Dijkstra’s algorithm?
The goal of Dijkstra’s algorithm is to find a path with the minimum distance from a given start vertex (the source) to each other vertex in the graph.
Complete the table to show the distances after the first and second iterations of the while loop of Dijkstra’s algorithm, starting from the node U:
- create priority queue
- set dist = 0 for start vertex and dist = infinity for all other vertices
- add all vertices to priority queue
- ITERATE while priority queue is not empty
- remove u from the front of the queue
- ITERATE over e in the neighbours of u
- set new distance to dist u + length of edge from u to w
- IF new distance < dist w
- set dist w to new distance
- change priority(w, new distance)
See Exploratory Activity 5.8 for a visualisation of how Dijkstra’s algorithm works:
https://learn2.open.ac.uk/mod/oucontent/view.php?id=734611§ion=1.1
Show the order the nodes of the attached tree will be visited in a depth first search.
Show the order the nodes of the attached graph will be visited in a breadth first search (BFS).
- C
- A, D (any order)
- B, E (any order)
- G, K, F (any order)
- H
See Exploratory Activity 5.5 for a visualisation of how a depth first search of a graph works:
https://learn2.open.ac.uk/mod/oucontent/view.php?id=734611§ion=1.1
