Introduction
stage1，
Requirement
School of Computing and Information Systems
COMP10002 Foundations of Algorithms
Semester 2, 2017
Assignment 2
Learning Outcomes
Inthisprojectyouwilldemonstrateyourunderstandingofdynamicmemoryandlinkeddatastructures,
and extend your skills in terms of program design, testing, and debugging. You will also learn about
graph labeling, and implement a simple shortest path mechanism (broadly speaking, the equivalent
of bubblesort) in preparation for the more principled approaches that are introduced in comp20007
Design of Algorithms.
Path Planning
Any process that involves movement requires path planning. If we are at location A and wish to get
to location B, we seek out and follow the “best” route between them, where “best” might be shortest
(in terms of distance), or fastest (in terms of time taken), or cheapest (in terms of cost), or most scenic
(in terms of appeal), or any weighted combination of those factors. This simple operation happens
when we use Google maps, when we request quotes for airline tickets, and when we use our phone to
request an Uber pickup.
Rectangular Grids
The founders of Gridsville were a mix of mathematicians and computer scientists. So when they
discovered an uninhabited rectangular island off the south coast of Antarctica that they could use for
their new colony, they planned a town using a rectangular grid of streets running north-south and east-
west. The diagram on the next page shows the seven north-south streets that they built, and the five
east-west streets. Streets are named with digits (“0” to “6”) or letters (“a” to “e”), and intersections are
labeled by their locations on the grid that results, for example, “4c”. (They were very boring people.)
Hundreds of years later, Gridsville is finally getting an Uber-like service, provided courtesy of the
Gridsville City Council (gcc, get it?). But the Gridsville Council has remained very traditional and
is insisting that pick-ups and drop-offs may only happen at street corners, that is, locations that are
addressable via the grid coordinates. To help prepare for the arrival of the new service, the Council has
approached a local software company, Algs-R-Fun, and has commissioned software to help manage
the vehicle fleet. In particular, each time a customer (standing at an intersection in the grid) calls for a
pickup, the “best available” car should be directed to go and pick them, where “best” means “the one
that can get there the fastest”. The Council has already collected some travel-time measurements, and
has recorded for each street, and for each city block on that street, how long it takes to travel in that
direction along that block. For example, looking at Figure 1, travel east from “4c” to “5c” takes 34
seconds. Some streets cannot be used in some directions because they are one-way, and in that case
the Council notes them as having a cost of 999 seconds. In the example in Figure 1, it is not possible
to travel south from “4c” to get to “4d”.
Stage 1 – Reading the Data (marks up to 8/15)
Write a program that reads data from stdin in the format illustrated on the right-hand side of Figure 1
(see test2.txt linked from the LMS page for the full file) where the two numbers on the first line
are always the grid dimensions, x and y (they will be 7 and 5 respectively for Gridsville, but might be
different for other towns elsewhere in the world, and the GCC has bold ideas about being able to sell
1
3 0 1 2 4 5
e
d
c
b
a
6
34
999
9
38
9
10
17
8
15
26
Input test2.txt
39 lines in total:
7 5
0a 9 999 999 38
1a … 999 … …
2a … 999 … …
…
4c 34 15 26 999
…
4e … … … 999
5e … … … 999
6e 999 10 17 999
4c
5c
1e
Figure 1: Street layout in Gridsville. Intersections are labeled by their grid coordinates. See the FAQ
page for the full test2.txt input file for this example.
their software to other towns), followed by x×y lines, each line describing the travel times out of one
intersection; and where “…” in the figure represent further integer values. Those x × y lines (35 of
them for Gridsville) will always be presented in row-at-a-time order of intersection name, and each
intersection name will always be an integer immediately followed by a single alphabetic character
starting from a, and is followed by exactly four more integers on that line, representing the time in
seconds needed to travel (respectively) one block east, one block north, one block west, and one block
south of that intersection.
Your program should build an internal representation of the specified intersections, using structs
whereeverappropriate. Youmayassumethatallinputfilesyouwillbeprovidedwithwillbe“correct”,
according to the description given above, that all of the times will be strictly positive integers, and that
there won’t be any tricksy-wicksy special cases introduced during the testing, nor any missing lines,
nor any incorrect or wacky values in the lines; but you may not assume any upper limit on the number
of streets involved in the city grid. Note also that the input values will be int, to keep it simple and
avoid the rounding problems associated with floating point representations.
The grid size line and grid cost data lines are is followed by a third section of data in the input file:
one or more grid references, one per line. You are also to read those grid references into a suitable
data structure. Required output from this stage is the following summary:
mac: ass2-soln >>> 27
S3: | ^ ^ ^ ^ v
S3: | ^ ^ ^ ^ v
S3: c | 42 43 25 26 >>> 26 >>>> 60 8 47
S3: | ^ ^ ^ v ^
S3: | ^ ^ ^ v ^
S3: e | 13 >>> 5 >>>> 26 >>>> 70 26 >>>> 37
Figure 2: Example of Stage 3 output. More examples are linked from the FAQ page. If there is
disagreement between the examples on the FAQ page and this handout, follow the ones in the FAQ.
The boring stuff…
This project is worth 15% of your final mark. A rubric explaining the marking expectations will be
provided on the FAQ page.
Submission will again be done via dimefox and the submit system. You can (and should) use
submit both early and often – to get used to the way it works, and also to check that your program
compiles and executes correctly on our test system, which has some different characteristics to the lab
machines. Only the last submission that you make before the deadline will be marked.
You may discuss your work during your workshop, and with others in the class, but what gets
typed into your program must be individual work, not copied from anyone else. So, do not give hard
copy or soft copy of your work to anyone else; do not “lend” your “Uni backup” memory stick to
others for any reason at all; and do not ask others to give you their programs “just so that I can take
a look and get some ideas, I won’t copy, honest”. The best way to help your friends in this regard
is to say a very firm “no” when they ask for a copy of, or to see, your program, pointing out that
your “no”, and their acceptance of that decision, is the only thing that will preserve your friendship.
A sophisticated program that undertakes deep structural analysis of C code identifying regions of
similarity will be run over all submissions in “compare every pair” mode. Students whose programs
are so identified will be referred to the Student Center for possible disciplinary action without further
warning. This message is the warning. See for
more information. Note also that solicitation of solutions via posts to online forums, whether or not
there is payment involved, is also taken very seriously. In the past students have had their enrolment
terminated for such behavior.
Deadline: Programs not submitted by 10:00am on Monday 16 October will lose penalty marks
at the rate of two marks per day or part day late. Students seeking extensions for medical or other
“outside my control” reasons should email as soon as possible after
those circumstances arise. If you attend a GP or other health care professional as a result of illness, be
sure to take a Health Professional Report form. with you (get it from the Special Consideration section
of the Student Portal), you will need this form. to be filled out if your illness develops in to something
that later requires a Special Consideration application to be lodged. You should scan the HPR form
and send it in connection with any non-Special Consideration assignment extension requests.
Marks and a sample solution will be available on the LMS before Tuesday 31 October.
And remember, algorithms are fun!