Scribd
Upload
60 views

Algorithms Worksheet 6

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
60 views

Algorithms Worksheet 6

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/ 4

Worksheet 6 Optimisation algorithms

Unit 12 Algorithms

Task 1
1. The questions below refer to the following weighted graph.
(a) The priority queue at the start is shown below. Complete the priority queue to show
temporary “costs” and mark these “costs” at each vertex.

A= B= C= D= E= F=

(b) Dijkstra’s algorithm is used to find the shortest distance form the start node A to every
other node.
Show the temporary distances assigned to each node, and the state of the priority
queue after A and C have been visited.

Priority queue:

1
Worksheet 6 Optimisation algorithms
Unit 12 Algorithms

Once these distances have been added to the priority queue, the algorithm proceeds
as follows:
While the priority queue is not empty:
Remove the node at the front of the queue. This is the current node.
For each neighbour, compute new distance by adding together the temporary
distance at the current node and the length of the edge going to that neighbour.
If the new distance is less than the neighbour’s current distance, replace the
neighbour’s distance by the new distance.

(c) Which is the next node to be visited? What will be the state of the priority queue, and
the temporary distance at F, after this node has been visited?

Priority queue:

(d) Will any further changes be made to temporary distances after this step? Explain.

2. Use Dijkstra’s algorithm to find the shortest distance from A to every other node. Colour
each node as it is completed or visited (dequeued) and enter the temporary distances on
the graph, changing them if and when required to end up with the shortest distances.

Show the state of the priority queue as each node is visited.

2
Worksheet 6 Optimisation algorithms
Unit 12 Algorithms

Priority queue

A=0 B=∞ C=∞ D=∞ E=∞ F=∞ G=∞ H=∞

Task 2

3. Which of the following statements are true about the Travelling Salesman problem?

(a)  The TSP is a non-computable problem

(b)  The TSP can sometimes be solved using a brute-force algorithm

(c)  Assuming a specific start city, the number of possible routes for 8 cities is double
the number of routes for 4 cities

(d)  Assuming a specific start city, there are fewer than 700 possible routes for 7 cities.

4. What is a tractable problem? Include in your answer the time complexities of tractable and
intractable problems, using Big-O notation.

3
Worksheet 6 Optimisation algorithms
Unit 12 Algorithms

5. (a) Complete the table below for different values of n.

n 8 16 128

log2n

n log2n

n2

n3

340,282,366,920,938,463,463,374,607,431,
2n
768,211,456 (a 39-digit number)

n! 20,922,789,888,000 A very large number!

(b) Algorithms for problems A, B and C have time complexities O(n log2n), O(n!) and O(n4).
Which of these problems are tractable, and which are intractable?

6. Choose a password of 8 lowercase alphabetic characters. Write the password below:

What is the big-O notation for a brute force algorithm to crack this password?

Log on to a site to test the strength of the password. You could try
https://howsecureismypassword.net/ or type into Google “How secure is my password” to
find a different site.
How long will it take an average PC to crack the password?

How long would it take to crack a password with 16 lowercase letters?

If you use a mixture of eight uppercase and lowercase letters, digits and 28 other symbols,
what is the big-O notation for the time complexity of the brute force algorithm?

How long will it take an average PC to crack it?

Is cracking a password an intractable problem?

Is cracking a password an insoluble problem?

You might also like