VCAA Algorithmics
Member since@vcaa_algorithmics-
VCAA Algorithmics Account
Hexa Quest
Extended Response10 MarksShared
HexaQuesta is a game played on a board that is divided into hexagonal regions. There are three kinds of borders between regions:
• Normal borders take one move to cross.
• River borders take two moves to cross.
• Mountain borders cannot be crossed.
Game boards may contain thousands of hexagonal regions.
The objective of the game is to travel across the board from the start, S, to the finish, X, with the fewest number of moves possible.
Samarth would like to write a program that determines how to win the game.
(a).
Describe an ADT that appropriately models a board of the HexaQuesta game.
[2](b).
Write an algorithm, in pseudocode, that Samarth could use to efficiently find a winning path from the start to the finish on any board.
[5](c).
Samarth would like to find the best starting region on a given board. He decides that the best starting region is the one with the lowest average number of moves to travel to every other region on the board.
[3]Describe how Samarth could efficiently find the best starting region on the board and derive a running time for your solution. Do not provide pseudocode in your answer.
0Uses1View0Likes
Chemical Reactions & ADTs
Extended Response5 MarksShared
Alex is developing a computer simulation to model a chemical reaction. In the simulation, the reactor is initially empty and the reaction starts when one or more chemicals are added. More chemicals may be added while the reaction is in progress. A chemical reaction is characterised by what chemicals are added, how much of them are added and when they are added.
(a).
To store a description of a chemical reaction for simulation, Alex needs the following information about each addition into the reactor:
• the name of the chemical added
• the time the chemical was added, in seconds, after the reaction begins
• the amount of the chemical added, in milligrams
Describe a combination of ADTs that Alex could use to store a description of a chemical reaction. Justify your answer.
[3](b).
Alex intends to use the combination of ADTs described in part a. often and decides to define the combination of ADTs as a new ADT called ChemEvents.
For the ChemEvents ADT, as described in part a., write the signature specification of the following operations:
• Add a new chemical to the reaction.
• Look up what chemical was added to the reaction at a given time.
[2]0Uses4Views2Likes
Number Box
Multiple Choice1 MarkShared
Consider the following algorithm.
Algorithm numberbox(n)
a ← 1
b ← 1
For each digit in n Do
If digit is even Do
a ← a + b
b ← b + 1
If digit is odd Do
a ← a × b
b ← b - 1
Return a
What does the algorithm numberbox output when n = 2023?
(a).
11
(c).
12
(b).
3
(d).
28
0Uses2Views0Likes