SUPERVISOR TO ATTACH PROCESSING LABEL HERE

Victorian Certificate of Education

2015

Letter
STUDENT NUMBER

ALGORITHMICS (HESS)
Written examination
Monday 2 November 2015
Reading time: 11.45 am to 12.00 noon (15 minutes)
Writing time: 12.00 noon to 2.00 pm (2 hours)

QUESTION AND ANSWER BOOK

Structure of book
Section Number of Number of questions Number of
questions to be answered marks
A 20 20 20
B 14 14 80
Total 100

• Students are permitted to bring into the examination room: pens, pencils, highlighters, erasers,
sharpeners, rulers and one scientific calculator.
• Students are NOT permitted to bring into the examination room: blank sheets of paper and/or
correction fluid/tape.
Materials supplied
• Question and answer book of 23 pages.
• Answer sheet for multiple-choice questions.
Instructions
• Write your student number in the space provided above on this page.
• Check that your name and student number as printed on your answer sheet for multiple-choice
questions are correct, and sign your name in the space provided to verify this.
• All written responses must be in English.
At the end of the examination
• Place the answer sheet for multiple-choice questions inside the front cover of this book.

Students are NOT permitted to bring mobile phones and/or any other unauthorised electronic
devices into the examination room.
© VICTORIAN CURRICULUM AND ASSESSMENT AUTHORITY 2015
2015 ALGORITHMICS EXAM 2

SECTION A – Multiple-choice questions

Instructions for Section A

Answer all questions in pencil on the answer sheet provided for multiple-choice questions.
Choose the response that is correct or that best answers the question.
A correct answer scores 1, an incorrect answer scores 0.
Marks will not be deducted for incorrect answers.
No marks will be given if more than one answer is completed for any question.

Question 1
[Link](6)
[Link](3)
[Link]( )
[Link](2)
[Link]( )
Given an empty queue Q, what does Q look like after the operations above?
A. 6
B. 3
C. 2
D. It is empty.

Use the following information to answer Questions 2 and 3.

3 9
6
1
5
2
4
8

Question 2
The first six nodes visited, starting at node 1, in a depth-first search could be
A. 123456
B. 124637
C. 124853
D. 136798

Question 3
The first six nodes visited, starting at node 1, in a breadth-first search could be
A. 124653
B. 123456
C. 124563
D. 123458
SECTION A – continued
 3 2015 ALGORITHMICS EXAM

Question 4
Eight network devices are arranged so that every device is connected to every other device by a single link.
The total number of links can be calculated by
A. 82
B. 82 – 1
C. log 8
8  1
D. 8
2

Question 5
A graph that is a tree where each edge weight appears a maximum of two times can have
A. only one minimal spanning tree.
B. only two minimal spanning trees.
C. only three minimal spanning trees.
D. four or more minimal spanning trees.

Question 6
To guarantee a unique minimal spanning tree in a graph
A. there must be no cycles.
B. running Prim’s algorithm is sufficient.
C. each edge must have a unique weight.
D. repeated edge weights must be odd in number.

Question 7
To show that (u, v) is in the transitive closure of graph G, it is necessary to show that
A. a u-v path exists in G.
B. no u-v path exists in G.
C. G is a connected graph.
D. u and v have the same degree.

Question 8
Which one of the following statements is correct?
A. All directed graphs are also undirected graphs.
B. Undirected graphs can also be represented as directed graphs.
C. There is no relationship between directed and undirected graphs.
D. Only undirected graphs with positive edge weights can be represented as directed graphs.

Question 9
Which one of the following recurrence relations represents the time complexity relationship for mergesort?
A. T(n) = T(n/2) + O(1)
B. T(n) = 2T(n/2) + O(n)
C. T(n) = 2T(n/2) + O(log n)
D. T(n) = 2T(n/2) + O(n log n)

SECTION A – continued
TURN OVER
2015 ALGORITHMICS EXAM 4

Question 10
A search algorithm satisfies the following recurrence relation.

 n
T + O(n), n > 1
T (n) =   2 
O(1) , n =1


Which one of the following is the time complexity of this search algorithm?
A. Ө(n)
B. Ө(1)
C. Ө(log n)
D. Ө(n log n)

Question 11
Which one of the following statements may not always be true?
A. A loop invariant is satisfied throughout the loop.
B. A loop invariant is satisfied immediately before the loop.
C. A loop invariant is satisfied after each iteration of the loop.
D. A loop invariant is satisfied immediately after the last iteration of the loop.

Question 12
Which one of the following problems is known to be solvable for large values of N in Polynomial-time?
A. Find all subsets in N items.
B. Find all permutations of N items.
C. Find a minimal spanning tree in a graph of N edges.
D. Find the solution of the travelling salesman problem with N nodes.

Question 13
When considering computability, the Halting Problem is
A. complete when executed on a Turing machine.
B. decidable when executed on a Turing machine.
C. incomplete when executed on a Turing machine.
D. undecidable when executed on a Turing machine.

SECTION A – continued
 5 2015 ALGORITHMICS EXAM

CONTINUES OVER PAGE

SECTION A – continued
TURN OVER
2015 ALGORITHMICS EXAM 6

Use the following information to answer Questions 14 and 15.

A Turing machine is configured with the instructions represented in the state diagram below.

qh
0/0:R

blank/1:R

blank/blank:L
q1

0/0:R q2

blank/0:R 1/blank:R

1/blank:L

q3

1/1:R
0/blank:R

Each edge is labelled i / j : k, where:

• i is the input
• j is the output
• k is the direction the head moves (L = left, R = right) after the output.
The machine begins in state q1.
The machine is given the following tape. For this machine, the tape remains stationary while the head moves.
The arrow shows the starting point of the head.

0 1 blank 1 1 1 blank 0 H

SECTION A – continued
 7 2015 ALGORITHMICS EXAM

Question 14
After the fifth step, the Turing machine will be in
A. state q2 and the head will be one position to the right.
B. state q1 and the head will be one position to the right.
C. state q2 and the head will be two positions to the right.
D. state q3 and the head will be two positions to the right.

Question 15
Which one of the following best represents the tape’s appearance and the position of the head when the
Turing machine halts?

A. 0 1 blank 1 1 1 blank 0 H

B. 0 blank 0 blank 1 1 0 0 H

C. 0 blank 0 blank 1 1 0 0 H

D. 0 1 blank 1 1 1 blank 0 H

SECTION A – continued
TURN OVER
2015 ALGORITHMICS EXAM 8

Question 16
David Hilbert’s 1927 program and its connections to the origin of computer science imply that, if
mathematical reasoning is fully formalised, then computers will be able to
A. solve all mathematical problems.
B. detect when a mathematical problem is unsolvable.
C. create different methods of solving a particular mathematical problem.
D. create different methods of determining if a mathematical problem is unsolvable.

Question 17
After measuring the running times of two algorithms, A and B, using increasing size of input n, the following
data is recorded.

n 1 2 4 8 16 32
Algorithm A 0 2 8 24 64 160
Algorithm B 1 4 16 64 256 1024

Which Big-O notations best describe the running times of the two algorithms?
A. Algorithm A is O(n) and Algorithm B is O(n).
B. Algorithm A is O(n) and Algorithm B is O(n2).
C. Algorithm A is O(log n) and Algorithm B is O(n3).
D. Algorithm A is O(n log n) and Algorithm B is O(n2).

Question 18
Consider the following pseudocode, where the input value, n, is a positive integer.
x = 0
for i in the range of 1 to n
for j in the range of 1 to n
x = x + i + j
return x
The runtime is best described as
A. O(n)
B. O(n2)
C. O(log n)
D. O(n log n)

SECTION A – continued
 9 2015 ALGORITHMICS EXAM

Use the following information to answer Questions 19 and 20.

Consider the following weighted graph.

A B C
3 –1

Question 19
Which one of the following statements about the graph is true?
A. There is no finite shortest path from A to C.
B. The shortest path from A to C has weight 2.
C. Dijkstra’s algorithm will not terminate on this graph.
D. The Bellman-Ford algorithm will not terminate on this graph.

Question 20
If T is a set of edges representing a minimal spanning tree of the graph, which one of the following
statements is true?
A. T = {}
B. T = {(A, B)}
C. T = {(B, C)}
D. T = {(A, B), (B, C)}

END OF SECTION A
TURN OVER
2015 ALGORITHMICS EXAM 10

SECTION B

Instructions for Section B

Answer all questions in the spaces provided.

Question 1 (3 marks)
The Church-Turing thesis states that a function on natural numbers is manually computable by a
human being if, and only if, it can also be computed by a Turing machine.
Explain what this statement means. In your answer, include reference to the limitations of this thesis.

Question 2 (4 marks)
a. Describe the difference between an array and a dictionary. 2 marks

b. Justify, with two real-world examples, when a priority queue is the more suitable abstract data
type than a queue. 2 marks

SECTION B – continued
 11 2015 ALGORITHMICS EXAM

Question 3 (3 marks)
Consider an algorithm that takes as its input a positive whole number, n, where n ≥ 3. The algorithm
computes the number of ways an n-gon can be divided into n-2 triangles, where different orientations are
counted separately.
Given some value of n, is determining whether the output of the algorithm is equal to some value x
decidable? Justify your answer with reference to limits of computability.

SECTION B – continued
TURN OVER
2015 ALGORITHMICS EXAM 12

Question 4 (9 marks)
Shara is a scientist who has developed a vaccine for a new type of disease. She left this vaccine
on a table overnight and a laboratory monkey stole it. The monkey escaped through a vent into an
underground drainage system.
The drainage system consists of a maze-like structure with drains between buildings connecting
to other buildings in the area. Shara needs to retrieve the vaccine quickly, but as no human can
fit into the underground drainage system, she has approached the robotics department within her
organisation to borrow one of its unmanned ground vehicle robots to search the drains and set
traps for the monkey. The robot will travel down the drains and search each one, leaving behind
a humane trap to capture the monkey if it comes through that drain after the robot has already
checked it.
The diagram below shows Shara’s building (labelled ‘A’) and the buildings closest to it, including
their drainage connections. It does not show all of the connected buildings in the area.

a. Describe an algorithm that could be used in the robot to search for the monkey. In your
answer, explain how the algorithm would meet Shara’s needs. 4 marks

SECTION B – Question 4 – continued

 13 2015 ALGORITHMICS EXAM

b. Shara discovers that some of the drains have been partially blocked by different amounts of
debris from recent rains. This will need to be considered within the algorithm used in the
robot, that is, when searching, the robot should consider the amount of debris blocking each
drain.
Describe a method that can be used to accommodate this new condition. 3 marks

c. If the robot does not find the monkey in the drains shown in the diagram, Shara will need to
expand the search area.
Explain one consequence this will have in relation to successfully finding the monkey. 2 marks

SECTION B – continued
TURN OVER
2015 ALGORITHMICS EXAM 14

Question 5 (4 marks)
A government wants to track tourists in its city and their travel habits. In particular, the government would
like to know how much money the tourists are spending on travel and collect this data in the form of an
undirected weighted graph.
Each node in the graph will be a location where tourists change transport modes; for example, train stations,
car hire shops, bus stops, and so on. Each weight on the edge in the graph will be based on the profit that the
government gets from one tourist travelling along that edge. Note that some edges have a negative weight as
the government subsidises the transport route; for example, by supplying free trams or buses.
The government wants to compute the most profitable destinations originating from a particular train station
that it has codenamed ‘Station-X’. A government advisor recommends applying Dijkstra’s single-source
shortest path algorithm to compute the profit at each node using Station-X as the source and then taking the
maximum as the answer.
Do you agree with this advice? Explain why or why not.

SECTION B – continued
 15 2015 ALGORITHMICS EXAM

Question 6 (5 marks)
CallMe Inc. is planning to build an app that helps people find the mobile phone numbers of their
friends. The app will automatically detect a caller’s name by using speech recognition during
a telephone conversation and match the name with the number. This pair (name and telephone
number) will then be stored in a database. Assume that the speech recognition is 100% accurate,
so that the pairs are always correct.
a. In addition to inserting name–number pairs, if the only other functionality of the app is to look
up a mobile phone number when given a person’s name, would a dictionary or a list ADT be
better for storing this data? Use Big-O notation to justify your selection. 3 marks

b. CallMe Inc. has decided that instead of looking up a mobile phone number when given a
person’s name, it wants the app to offer a browse function, where the names of people are
listed in alphabetical order.
Which ADT could be used for storing the data in this scenario and why? 2 marks

SECTION B – continued
TURN OVER
2015 ALGORITHMICS EXAM 16

Question 7 (6 marks)
Some black-box tests for an algorithm that computes information about a given node, u  V, in a
connected, unweighted, undirected graph, G(V, E), are required.
a. The size of the graph is not known in advance, but the number of nodes is limited to be
between 1 and 220.
State the four boundary cases for |V| that should be tested. 4 marks

b. In terms of |V|, what is the smallest and largest |E| that could occur for the graph? 2 marks

Question 8 (5 marks)
A new extension to the National Broadband Network (NBN) is required in rural Australia to
connect towns labelled A to I. The diagram below represents the roads between towns, with road
distances shown (in kilometres). Fibre optic cable is to be placed underground along each road such
that the total length of the cable is minimised.

60 D 60
A
H
45 35
25 55
40
45 C 40
B 40 E 65
50 25 40
45 F
60 G I
40

a. Name an algorithm that can be used to determine the minimum total length of cable needed. 1 mark

b. Draw the connections in the following diagram to minimise the total length of fibre optic
cable, thereby the cost of connecting all the towns to the NBN. 4 marks

A D
H

C
B E
F
G
I

SECTION B – continued
 17 2015 ALGORITHMICS EXAM

Question 9 (4 marks)
Turing machines are an abstract model of computation.
Outline four key characteristics of a Turing machine.

SECTION B – continued
TURN OVER
2015 ALGORITHMICS EXAM 18

Question 10 (13 marks)

Consider the following 6 × 6 grid.

START

X X

X X

X END

Suppose there is a robot that starts in the cell labelled ‘START’. This robot can only move to the
immediate right or down and it is not allowed to visit any cells labelled ‘X’.
a. i. In the grid above, for each blank cell, insert the number of different paths to that cell that
the robot could follow. 3 marks

ii. How many different paths can the robot take to get to the cell labelled ‘END’? 1 mark

SECTION B – Question 10 – continued

 19 2015 ALGORITHMICS EXAM

b. Write an algorithm, in pseudocode, that, for a given n × n grid, determines the number of
different paths from the top-left corner of the grid to the bottom-right corner of the grid.
Assume that the elements of the grid are either X, if the robot is not allowed to visit the
corresponding cell, or 0, if the robot can visit that cell. 9 marks

SECTION B – continued
TURN OVER
2015 ALGORITHMICS EXAM 20

Question 11 (8 marks)
Explain whether DNA computing is a threat to computer security. In your answer, include a discussion of
Non-deterministic Polynomial-time (NP) completeness.

SECTION B – continued
 21 2015 ALGORITHMICS EXAM

Question 12 (4 marks)
Describe how backtracking could be used to solve the travelling salesman problem.

SECTION B – continued
TURN OVER
2015 ALGORITHMICS EXAM 22

Question 13 (9 marks)
The following algorithm, named f, has three inputs and one output. For this algorithm, index
values start at 0.
Algorithm f(A, i, j)
First Input: A, an array of integers sorted in increasing order
Second Input: i, a valid index into A
Third Input: j, a valid index into A
If i equals j and A[i] is not equal to i
Output –1
Let m be (i+j)/2 rounded down to the nearest integer
If A[m] < m then
f(A, m+1, j)
else if A[m] > m then
f(A, i, m)
else
Output m
a. Draw a tree representing the execution path of Algorithm f if it begins with the following
inputs.
A = [–1, 0, 4, 5, 10, 11, 15, 20]
i=0
j=7
Include these first inputs as the root of your tree. Each node in the tree is a subsequent call to
the algorithm. 6 marks

SECTION B – Question 13 – continued

 23 2015 ALGORITHMICS EXAM

b. If A is any array of n integers sorted in increasing order, what does f(A, 0, n-1)
compute? 1 mark

c. Write a recurrence relation that gives the worst-case running time of Algorithm f. 2 marks

Question 14 (3 marks)
For a graph G with n nodes, a student runs the Bellman-Ford algorithm for n-1 iterations. She then
runs one more iteration and notices the shortest path between two nodes has reduced.
a. What property of G has the testing established? 1 mark

b. Explain whether the Bellman-Ford algorithm should be used to find a shortest path solution in
this example. 2 marks

END OF QUESTION AND ANSWER BOOK