CS209 lab4
http://www.maths.nuigalway.ie/~gettrick/teach/cs209/l4.html
-
For this lab you should submit all source code (python
files), and the result(s) of running the program on (a few)
test cases.
The source code must
be well presented (indenting, spaces, reasonable variable/function names,
etc.) and must include comments (as a rough guideline - aim to have nearly as
many comments as lines of code).
-
The above material should be uploaded to BLACKBOARD
before
the deadline of midnight
Thursday 22nd. February 2018. You will lose 20% for each day
(or part of day) the lab is late.
-
Plagiarism (the unattributed copying of work from other sources
(internet, fellow students,....)) will not be tolerated. Please see
http://www.nuigalway.ie/engineering/documents/plagiarism_guide_students
_v4.pdf. You risk getting zero for your lab if it is found to be
plagiarized.
http://www.maths.nuigalway.ie/~gettrick/teach/cs209/progs/
This lab is an extension of last weeks lab on the
Floyd "all pairs shortest path" algorithm.
-
As described in lectures - there are 2 standard ways of coding up the
Floyd algorithm:
-
Using iterations (e.g. FOR loop) to build up tables/matrices - complexity
O(n3).
-
Using recursion via a function - O(2n).
If last week you wrote an iterative solution - this week write the
recursive one, and vice versa!
-
Build in to your program this time an answer to the user of the actual
shortest route, i.e. the list of nodes we must travel through, and
have your program print this out to the screen.
Run your program on the data given at
http://www.maths.nuigalway.ie/~gettrick/teach/cs209/nums.txt.
Hence, list the shortest route between nodes
-
9 and 11 [here - node 9 means in normal counting - in PYTHON this will be
index 8 in some list]
-
13 and 3
(We are not worried about how to read in the data - you
can read it in from a file, from the user, or just "hard wire" it in
to the program.)
Note: Instead of the "infinity" talked about in lectures, or the "zero"
in the actual data, corresponding to points that are not connected, do
the following. Assume the data is, as given, with 0 in positions where
i and j are not directly connected. To "mimic" infinity, your program
should put in a large
positive number in this position. More precisely: that large positive
number can be just (sum of all the non-zero entries of the matrix)+1,
to guarantee it will be bigger than the other entries. Do this calculation
and replacement in PYTHON.
(Example - were the matrix [[0,0,2],[0,0,5],[2,5,0]] we would replace the
zeros by 15 = 2+5+2+5+1).
©
NUI, Galway