Scribd
Upload
7 views

Algorithms Homework 6 Answers

Uploaded by

Dhruva Trivedi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
7 views

Algorithms Homework 6 Answers

Uploaded by

Dhruva Trivedi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

Homework 6 Optimisation algorithms

Unit 12 Algorithms

Answers
1. The stations in an underground network are represented as a graph, with nodes
representing the stations and weighted edges representing the connections between them.
The weights represent the time taken to travel between two stations.

(a) Show how the graph may be represented as an adjacency list. [7]

(Order of items in each row of the list is not important)


(b) There is a well-known optimisation algorithm for finding the shortest distance between
a start node and all other nodes. What is the name of the algorithm? [1]
Djikstra’s algorithm / Djikstra’s shortest path algorithm
(c) A priority queue may be used as a supporting data structure in the implementation of
the algorithm. What are the main features of a priority queue? [2]
It is a FIFO / first in first out data structure (1 mark) in which items of higher priority are
held nearer the front of the queue than items of lower priority / are held in order of
priority ((1 mark)
(d) The start node is A. Describe the first two steps in the algorithm. Do not include the
use and operation of the priority queue in your answer. [5]
Step 1: Assign a tentative/temporary time/weight of 0 to A, ∞ to all other nodes (2
marks)

1
Homework 6 Optimisation algorithms
Unit 12 Algorithms

Step 2: Mark A as fully explored/visited (1 mark) and assign a tentative/temporary


time/weight to each neighbour,(1 mark) equal to distance at A + edge weight,
(1 mark) giving 2 at B, 5 at D. (1 mark)
OR, if step 2 is given as the first step accept this and give marks for step 3:
Step 3: Move to the node nearest to A (which is B) and mark as visited/fully explored.
For each neighbour of B, update temporary distance to Distance at B + edge
weight. (max 2 marks)
(e) Use the diagram to trace through the algorithm and calculate final distances.
What are the shortest distances from A to E, F and G? [3]
E = 5, F = 7, G = 13
(f) State two other applications of the algorithm. [2]
Finding best move in a game such as chess
scheduling aeroplanes and aircrews
building circuit boards
routing messages across the Internet
[Total 20 Marks]

You might also like