Task 2: C Problem
Assignment 1
General
Task 1: Algorithmic
Design
Task 2: C Problem
Assignment Submission
Academic Honesty
Late Policy
Requirements: C
Programming
Programming Style
Mark Breakdown
Additional Support
Acknowledgements
Task 2: C Problem
Olivia's grandfather sent her a letter describing the great lost treasures he discovered decades ago while exploring
the Mystic Archipelago. To obscure his ndings, he stored the details of his treasure map in a hexagonal structure
like the one below.
The points in a array correspond to the points shown above. The same behaviour of odd and even columns
in a dierent order generalises to an map.
7 × 4
m × n
Part A.
Write a function in C,
struct point *getAdjacentPoints(struct map *m, struct point *p)
that returns all the adjacent points around an inputted point which would lie on the map.
These should be sorted rst by the rst coordinate, and then the second coordinate.
If the inputted point is not on the map, the point is considered to have no adjacent points.
Part B.
After decades of secrecy, Olivia's grandfather's letter revealed what each number corresponds to in his map.
If the value of the point is negative, it represents the depth of the ocean oor in metres.
If the value of the point is 0, it represents land without treasure.
If the value of the point is 100, it represents an airport.
If the value of the point is positive but not 100, it represents the value of that specic treasure.
Each bit of treasure corresponds to an artefact. Artefacts that belong to the same island are related, and so if you
nd multiple artefacts on the same island, they are worth much more than the sum of their parts. The total value
of artefacts on a specic island is given by this formula
f(x ,x , … ,x ) =1 2 n n × x ×1 x ×2 ? × x n
This means that if there is a treasure worth 20 on island 1, and island 2 has treasures worth 2, 3, 4, then the total
value that can be found is
20 + [3 × 2 × 3 × 4] = 92
This is because artefacts from dierent islands are unrelated and so you can only add the sum
of the value of islands.
Write a function
int mapValue(struct map *m)
That nds the total value of all the treasure found in a map. The map has points of sea, land and treasure
respectively, with an airport counting as land.
S,L,T
Describe the time complexity of the algorithm in terms of .S,L,T
Part C.
Olivia further nds out that her grandfather stored the locations of each treasure in a separate array. Olivia then
uses this information to make a better algorithm to nd the total value of a map. For islands with treasure,
represents the expected value of the number of treasure points on the island. The expected value of the size of
islands with treasure on the map is . The values of and are constants that represent the expected values
taken over every single map. Specic maps do not necessarily follow these constants.
N T
IS N T I S
(i) Briey describe how the new algorithm improves upon the above one. You may but do not have to use
pseudocode.
(ii) Find the best case time complexity of the new algorithm.
(iii) Find the worst case time complexity of the new algorithm.
(iv) Explain a reasonable denition to use for the average case of the new algorithm and nd its time complexity.
(v) Give an example of a map with at least treasure point, land point and sea point where your algorithm in
this question explores as many points in the previous question. Briey explain your answer.
1 1 1
Give each of the time complexities in terms of , , , , when appropriate. When calculating the time
complexities, you are seeing how the time complexity grows with respect to values , , .
S L T N T I S
S L T
Each answer only requires 1-2 sentences of brief justication.
Part D.
Olivia discovers that her grandfather was looking for the location of a mysterious treasure called The Star of
Alhambra. This is far more valuable than any of the previous treasures he mapped out and he narrowed down the
number of locations it could be. Olivia wants to be able to go from one place to another as quickly as possible to
check as many of these locations as she can. The amount of time it takes to move to an adjacent point is
determined by the current point you are on.
It takes minutes to move from a land point to an adjacent point. 5
It takes time to move from a point in the sea. 2 + ceil( )1000
depth2
It takes minutes to y from one airport to any other airport. where are the
x coordinates of the airports.
max(15, ∣x ?1 x ∣ ?2 2 85) x ,x 1 2
It takes minutes to move from an airport or treasure to an adjacent point (treat like land).5
Write a function
int minTime(struct map *m, struct point *start, struct point *end)
that nds the minimum amount of time from the start point to the end point.
If is the number of airports in the map, nd the worst case time complexity in terms of , , , . Briey
explain your algorithm and data structures used to justify your time complexity.
A S L T A
Part E.
Olivia nds some peculiar maps where any ocean has a depth of exactly . She strongly suspects that these
are the ones to contain The Star of Alhambra. Out of all these maps, she noticed that there were never more than
airports. All of these have a known location. Write a function:50m
5
int minTimeDry(struct map *m, struct point *start, struct point *end, struct point *airports, int numAirports
which nds the minimum distance from one point to another faster than the previous algorithm.
What is the worst case time complexity of this algorithm? To get full credit you must nd the algorithm with the
best time complexity.
TIP: If you think you've worked out the most ecient algorithm, but can't work out how to actually write it, check out the
printMap function.