Preview

04 - Past Paper Simulation -Optimisation Algorithm

 1. _______________ has many applications for finding the shortest path between all possible vertices (nodes) and outputting the results by removing them from a queue of possible traversals (1 mark)

 2. What is the most obvious application (travel related) for the shortest path algorithm. (1 mark)

 3. How could shortest path algorithms be used in networking? (1 mark)

 4. Filling in a table like this can allow us to find the shortest distance from vertex A to every other vertex. Fill in the blanks for #1 and #2 (2 marks)
Write your two answers seperated by commas:

e.g.
x,y
dijkstras_table_fillinblanks1.png

 5. Referring to the image above, what would the shortest path from A to C be? (1 mark)
Write your answer in a list (in square brackets)
to enable our algorithm to give you the mark. End with C

e.g.

[X,Y,Z,C]

 6. If we want to traverse between the nodes 'a' and 'z', during initialisation, our source is set to node 'a' and has the value of ____. This is because to travel from point 'a' to point 'a' would be ____. All other nodes would have the value ______. (2 mark
What are the two words that will fill in the blanks?
dikstrasalgorithm_question1_buildingup.png

 7. What is A*, what are its implementation details, and what are its advantages and drawbacks in regard to traversing graphs towards a target? (3 marks)

 8. State the full name of the data structure shown in the image below (3 marks)
graph_for_optimisationalgorithms.png

 9. State what the heuristic values could represent in the image shown (refer to previous question). The nodes contain the names of different places. (1 mark)

 10. State the purpose of heuristic values in the A* algorithm. (1 mark)

 11. Perform an A* algorithm on the data structure in question 8 to find the shortest distance between H and E (Humppa and Enema). The stages of the process (That would make up an eight mark question are shown below). Use letters instead of the full place name
Visiting H with correct heuristic

Visiting G and N from H

Calculating correct distance+heuristic for G and N

Identifying G as the smallest value

Visiting L and M from G

Calculating distance+heuristic for L and M

Identifying L as the smallest value

Visiting E

Calculating distance+heuristic for E

Final path: [,,,] <<---Fill this in

 12. Give one decision that is made in the A* algorithm, and describe the effect of this decision on the next step(s) of the algorithm. (3 marks)

 13. Describe what is meant by a heuristic approach to problem-solving. (2 marks)

 14. Primary school children need to be taught how to make decisions about when to cross a busy road. Describe how heuristic methods are used to help make these decisions in a computerised system.(2 marks)

 15. This image is a graph representation of the places that the travelling salesman visits. Using this graph, show how Dijkstra's algorithm would find the shortest path from place A to place F (3 marks)
Answer: i) Max 6. 
Typically you would get 1 mark for final solution,
max 5 for showing the stages.

1. Mark A as the ____________.
2. Record B is 5, C is 3, D is 3
3. Mark A as visited
4. ______ is shortest distance from A
5.(C as current) Record E as 6, F as 6
6. Mark C as visited
7.(D as current) Record E as 5 
8. Mark D as visited
9. (B as current) Record F as 7, do not update table as longer (1)
10. Mark B as visited
11. (E as current) Record D as 8, do not update table as longer and E 
has been visited
12. >>>Fill in the blanks here in a list[,,] found as shortest

Write your answer in the following format:
==========================================
first answer,second answer,[A,B,C]
Dijkstrasalgorothm_graph.png