NAME:
DECV Student ID:
2019
ALGORITHMICS UNIT 4
School Assessed Test 2: Advanced Algorithmic Design Patterns
Outcome 2
(To be completed in the week: 9th -13th Sept 2019)
Type
Extended Response
Number of questions
4
Number of questions to be answered
4
Number of marks
44
Reading Time: 10 minutes Writing time: 60 minutes
QUESTION AND ANSWER BOOK
School Assessed Task 2 consists of 4 questions requiring extended response analysis. Materials supplied
Question and answer book of 12 pages Materials permitted
Pens/StationaryandoneScientificCalculatorpermitted.
No Reference material permitted.
Instructions
Write your name in the space provided above on this page.
AllwrittenresponsesmustbeinEnglish,pointformispreferred.
Students are NOT permitted to bring mobile phones and/or any other unauthorised electronic devices into the test room.
VSV Algorithmics Unit 4 SAT Test 2 2019: Page 1
(This page deliberately left blank)
VSV Algorithmics Unit 4 SAT Test 2 2019: Page 2
Answer all questions in the space provided.
Question 1 (14 marks)
You receive a delivery of n balls of extra fine merino wool yarn. They all look identical and should weigh 50g. But one is a fake, and is made of a heavier poorer quality material.
Your neighbour has an old-fashioned balance scale that enables you to compare any two sets of knitting wool balls. If it tips either to the left or to the right, you will know that the one of the sets is heavier than the other.
Sadly, you aren’t on speaking terms with the neighbour, so she charges you $10 each time you weigh anything.
a) How much would it cost using naïve “Brute Force” methods to determine the heaviest ball of yarn? Justify your answer using time complexity notations and terminology. (3 marks)
b) What kind of design pattern could be used to more efficiently find the heaviest ball of yarn? Justify
your answer.
(2 marks)
VSV Algorithmics Unit 4 SAT Test 2 2019: Page 3
Question 1 (continued)
c) Write an algorithm in pseudocode to find the fake ball of yarn more efficiently than the Brute Force
method.. (6 marks)
d) How many times must you use the scale with your Algorithm if there are “n” balls of wool? Justify your answer using time complexity notations and terminology. (3 marks)
VSV Algorithmics Unit 4 SAT Test 2 2019: Page 4
Question 2 (6 marks)
Given a directed tree/network representing pipes with the numbers on the pipe representing the maximum flow through each pipe, as shown in the diagram below.
a) Describe a method for determining the maximum flow through the network shown above. Describe the design pattern used in your method. Describe in detail the importance of the central pipe in determining the maximum flow. (3 marks)
b) What is the maximum flow through the network shown above? (1 mark)
c) What is the space complexity of the method you have defined for solving this problem? Justify your
response.
(2 marks)
VSV Algorithmics Unit 4 SAT Test 2 2019: Page 5
Question 3 (14 marks)
You are going on a walking trip. You start on the road at the starting point 0.
Along the way there are n hotels, at distance posts 0