1. Breadth First Search (BFS) algorithm traverses a graph in a breadthward motion and uses a __________ to remember to get the next vertex to start a search, when a dead end occurs in any iteration. (1 mark)
2. The BFS (Breadth first algorithm) employs the following rules. What is the third rule?(1 mark)
Rule 1: Visit the adjacent unvisited vertex.
Mark it as visited. Display it. Insert it in a queue.
Rule 2: If no adjacent vertex is found, remove the
first vertex from the queue.
Rule 3: ????
3. Referring to the image below, and employing the BFS algorithm, what order would the nodes be traversed? (1 mark)
Write your answer in the following format:
If it went from A to B to C to D first
then to E and F lastly to S, write your
answer in a list as shown below:
[A,B,C,D,E,F,G,S]
Note: Traverse alphabetically for this example. Don't forget the square brackets in your answer so that our algorithm marks you as correct.
4. A version of depth-first search was investigated in the 19th century by French mathematician Charles Pierre as a strategy for solving mazes. What B is often used in a depth first search? (1 mark)
5. Programmer Elliot has created a maze game. For one part of the system he has the following data structure. State the name of the data structure shown (1 mark)
6. Samuel suggests that Elliot use a breadth first traversal but Hans suggests a depth first traversal. Can you explain the difference (4 marks)
7. Callum wants a simple comparison. Describe one advantage and one disadvantage of depth-first search compared with breadth-first search (2 marks)
8. Referring to the image below, and employing the DFS (depth first search) algorithm, what order would the nodes be traversed? (1 mark)
Write your answer in the following format:
If it went from A to B to C to D first
then to E and F lastly to S, write your
answer in a list as shown below:
[A,B,C,D,E,F,G,S]
Note: Traverse alphabetically for this example. Don't forget the square brackets in your answer so that our algorithm marks you as correct.
9. A binary search tree, numbers, stores numbers that are entered into a computer. The contents of the tree are shown below. Explain, using the binary search tree numbers as an example, how a depth-first (post-order) traversal is performed. (1 mark)
10. Explain, using the above example, how a breadth first traversal is performed(1 mark)
11. In this slightly peculiar tree, E is a child of both A and F. A depth first search searches the tree going as deep (hence the term depth) as it can first. Write out the traversal that would result going from left to right (1 mark)
Write your answer in the following format:
[A,B,C,D,E,F,G]
Don't forget the square bracket around the letters so that our algorithm picks it up.
12. In reference to the above image, note that a breadth first search evaluates all the children first before proceeding to the children of the children. What would the result be for a BFS?(1 mark)
Write your answer in the following format:
[A,B,C,D,E,F,G]
Don't forget the square bracket around the letters so that our algorithm picks it up.
13. The following excerpt contains a list of real-life (non-computing) applications of _________________.
_______ is a step in solving a computing problem after all
possibilities have been identified, for example all combinations
of a chess move. Some of these possibilities can be eliminated
if checked against a constraint.
Real-life application 1:
========================
Answering multiple-choice questions –
they rely on elimination of first, obviously wrong alternatives,
and then once the options are narrowed, eliminating the options
that are true some times (but not all the time), living the only true answer.
Real-life application 2:
========================
Police detectives compile a list of
suspects and then eliminate those against a constraint
which could be an alibi or the lack of a motive.
Real-life application 3:
========================
Employers recruiting new workers
have a stack of CVs to go through. By setting a constraint
(e.g. an experience with a certain machine), they can
eliminate a whole subset of applicants.
Other examples include: Navigating a maze,
performing genetic selection – creating a dog
breed with particular attributes, applying ‘gut
feelings’(e.g. this doesn’t look right, too good
to be true, just run), behavioural experiments.
14. Given the adjacency matrix and a starting vertex of 1, one can find all the vertices in the graph using the following _______ _________ search function in Python. (2 marks)
def dfs_function(graph, vertex, path=[]):
path += [vertex]
for neighbor in graph[vertex]:
if neighbor not in path:
path = dfs_function(graph, neighbor, path)
return path
adjacency_matrix = {1: [2, 3], 2: [4, 5],
3: [5], 4: [6], 5: [6],
6: [7], 7: []}
15. Dominic writes a similar but different function that also demonstrates a depth-first function. How is this code/function different from the one above in question 14? (2 marks)
def dfs_iterative(graph, start):
stack, path = [start], []
while stack:
vertex = stack.pop()
if vertex in path:
continue
path.append(vertex)
for neighbor in graph[vertex]:
stack.append(neighbor)
return path
adjacency_matrix = {1: [2, 3], 2: [4, 5],
3: [5], 4: [6], 5: [6],
6: [7], 7: []}
print(dfs_iterative(adjacency_matrix, 1))
# [1, 3, 5, 6, 7, 2, 4]
