You have just been hired by the brand new startup Moogle, which is hoping to make money off the (so far untapped) market for internet services among cows. You have been assigned to work on their Moogle Maps project, which will help grazing cows find the shortest routes between various landmarks of interest (salt licks, water, etc.).
Specifically, you are to implement the all-pairs-shortest-paths algorithm. It reads in a graph from a file and then allow a cow to make a query against that graph. (Admittedly, a more complete version might allow more queries, but what are the chances that a cow will make more than one query?)Here is the output of the run described above:
> java fw Enter a filename: [[user types --->]] map0.txt Now trying to open map0.txt Read the number of cities = 3 The FW tables: fw[0] is [0, 1, -1] [-1, 0, 1] [1, -1, 0] fw[1] is [0, 1, -1] [-1, 0, 1] [1, 2, 0] fw[2] is [0, 1, 2] [-1, 0, 1] [1, 2, 0] fw[3] is [0, 1, 2] [2, 0, 1] [1, 2, 0] The "previous vertices": pv is [0, 0, 1] [2, 1, 1] [2, 0, 2] From what city (1-3)? [[user types --->]] 3 To what city (1-3)? [[user types --->]] 2 From city # 3 to city# 2 the minimum cost is 2 And the path is 3 --> 1 --> 2
Your job is to define a class named fw (lowercase), in a file fw.java (also lowercase). You will not create any objects of the fw class; all of your work can be done inside
public static void main(String[] args) { ... }
(Rather than putting all the code into main, you are free to define helper functions in the fw class
and then call them from main. Don't forget that, since there are no fw object around,
like main these helper functions will all have to be declared static.) When run, your
main function should behave as described above.
We recommend writing the code in the following sequence. Don't forget to test your code at each step.
To start with, I recommend reading the input into a 2D array of ints.
You may assume the file will be in the following format:
3
0 1 -1
-1 0 1
1 -1 0
Here, the first line of the file contains a positive integer, n,
indicating the number of vertices in the graph.
This is followed by n lines of data, each of which
contains n integers. The integer in row src and
(column) position dst indicates the cost of the edge
from vertex src to vertex dst in the graph. If there
is no edge from vertex src to vertex dst then the
length of this edge is "infinity" which is represented by the
value -1.
Note, too, that the cost of the edge from vertex src
to dst may be different from the cost of the edge from
vertex dst to src, due to hills,
streams with strong currents, or other unusual field conditions.
For the purposes of this program, we are numbering vertices starting from 1, instead of the traditional 0. Indexing from 1 is helpful in Floyd-Warshall, because it means you can use the 0 for other purposes (described more below).
WARNING: If you want indexes 1 through n to be accessible, you need an array of length at least n+1.
Watch out: we are using -1 to stand for "infinity." You will have to watch out for these edges, and treat them specially.
As you'll recall, vertices should be numbered from 1 upwards rather than from 0. Here's why:
The algorithm builds a series of tables of path lengths from every src to every dst. The kth table represents, "the shortest path-length from all src vertices to all dst vertices going through no intermediate vertex numbered higher than k. By starting at 1, the zeroth table then goes through no intermediate vertices at all, which means it's simply the original graph. By starting vertex-counting at 1, we avoid having to have a special case for the original graph.
Note that (despite the sample run above) your code is not required to display the shortest path, or the previous-vertex matrix used to compute this shortest path. You may do this for extra credit, as described below.
In this assignment you will have the opportunity to try out the very nifty JFLAP Automata Simulator developed by Dr. Susan Rodger at Duke University. JFLAP allows you to create automata on the screen and then simulate their operation with any input string you like. You will also be proving that certain tasks are unsolvable by finite automata (read: computers!)
WARNING - Running JFLAP on the lab macs JFLAP is present on the CS lab Macs - it's located in Go -- Applications -- Additional Applications -- Programming -- JFLAP.jar. However, if you want to double-click it to start it, you need to double-click the Start JFLAP application located in the same directory. Alternatively, you can start it from the command line (and no need to log in to knuth, either!) by running
cd /Network/Applications/Programmingand then, from that directory, run
java -jar JFLAP.java
You can download a copy of JFLAP for your own computer (or onto the Desktop of the PCs in the LAC lab) for free from this JFLAP software website. The smaller one, JFLAP_Thin.jar is all you will need.
A local copy of this file is also avaiable at this JFLAP_Thin.jar link.
JFLAP is written in java; a jar file packages a group of Java classes in one place. Double-clicking that JFLAP.jar file should start the program (if Java is set up).
Similar to previous assignments, you will submit a different file for each of the problems on this assignment. Here, however, there will be 10 or more of them! Some will be JFLAP files, which you should name as the problem specifies -- this will make it easy on the graders. Others will be plain-text files (.txt) which will hold your proofs. Submit the files via the website as usual, but please do name them according to the problem specification!
When you start JFLAP, you will see a menu that looks something like this:
with a Help menu at the top. In fact, the help option directs you to
the
tutorial available from this link..
The documentation is not only thorough, it even has various "haiku-help"
versions scattered through it... . (Actually the haiku-help has been made
hard to find in recent versions.)
For each of the problems below, you should assume that the input will consist of zero or more 0's and 1's. Thus, keep in mind that every state in a DFA [Deterministic Finite Automaton] must have one outgoing transition labeled 0 and one outgoing transition labeled 1. Remember also that a DFA must accept every string in the desired language and reject every string not in the language. Finally, the empty string (λ, lambda) corresponds to no input at all. As a concrete example, consider a language L, defined to be the set of all strings with an even number of 0's. The empty string must be in this language since the empty string has zero 0's -- and zero is even! Thus, a DFA for this language must have its initial state be an accepting state -- that way it accepts even if it gets no input! Be sure that your automata accepts the empty string if it is in the specified language -- we'll be checking this!
In addition, because you will be applying some of the theorems from class to write your own proofs, a sample proof using the nonregular language theorem is available at this link. You are welcome to "copy" as much as you like from this sample proof when writing your own proofs. Simply submit each proof in an ASCII plain-text file with a name as designated by the specific problem.
The first several subparts, #1 through #4, should be done
individually.
{w | w contains at least two 0's and at most one 1.}
For example, the string 01000 is in the language but
01 and 0110 are not.
Save and submit your DFA in a file called part1.jff.
{w | The number of 0's in w is a multiple of 2 or a multiple of 3 or both.}
For example, the empty string, 0101, and 01000100 are
in the language but 01 is not. Your DFA should have at
most 6 states. The empty string, with zero 0s should be accepted.
Save and submit your DFA in a file called part2.jff.
{w | The number of 0's in w is a multiple of 3 or a multiple of 5 or both.}
Notice that this machine would require at least 15 states if you were to
build a DFA. (Make sure you see why -- though you need not prove it.)
However, for credit for this NFA, it may have at most 9 states. Again, since 0 is a multiple
of 3 (or 5, for that matter), the empty string should be accepted.
Save your NFA in a file called part4.jff and submit.
The subsequent problems, #5 through #8, may be done in pairs or
individually.
{w | w is the BINARY representation of a number which is a multiple of 7.}
For example, the inputs 0, 111, 1110,
10101, 11100, and 100011 would all be accepted because they are the binary
representations of the numbers 0, 7, 14, 21, 28, and 35, respectively.
Note! Keep in mind that the DFA reads input from left to right, so that the
first digit seen will correspond to the most significant digit and the last digit
seen is the least significant digit.
The number may is permitted to begin with
leading zeroes (for example, 010101 is OK because it is still 21).
For this problem the empty string should
be interpreted as the number 0 and, thus, the empty string should be accepted.
This problem is somewhat more challenging than the ones above.
You'll need to think about this some before starting to construct
your DFA. For full credit, your solution may not use more than 8 states (it's
possible, in fact, to use fewer).
Caution: this problem is tricky - consider carefully how
reading a 1 or a 0 changes the value of
the binary number being built... especially because the number is being
built in the "wrong direction," so to speak.
Save and submit your DFA in a file called part5.jff.
{w | w is made of 0's and 1's and is the same forwards as backwards}
For example, 0, 11, 101, and 00100 are all in
the language but 01, 100 and
010111 are not in the language.
Prove that that this language is not regular by using the Nonregular
Language Theorem. Save and submit your proof in a file named
part6.txt.
As an example of what such a proof should look like,
take a look at the file sampleProof.txt.
Notice that simply
giving an infinite set S does not suffice. You must also
argue that an arbitrary pair of strings from S are always
distinguishable!
{w | w is a string of 0's whose length is a power of 2}
For example, the strings 0, 00, 0000, 00000000
are all in the language since their lengths are 1, 2, 4, and 8, all
of which are powers of 2. On the other hand, 000, 00000,
any string containing a character other than 0, and the empty
string are all not in this language.
Prove that this language is not regular by using the Nonregular Language Theorem. Your proof must be clear and precise. Leave your proof in electronic form in a file called part7.txt.
{w | w contains an equal number of 0's and 1's in any order.}
is not regular.
However, now consider the following closely related language:
{w | w contains an equal number of occurrences of the substrings 01 and 10.}
The substrings may overlap -- thus, this language contains 0110, which contains the pattern 01 once
and the pattern 10 once, as well as 101 (this contains the pattern
10 once and the pattern 01 once - they overlap, but that's fine!).
Amazingly, this language is regular! Show that this is true by building
a DFA or NFA for this language using JFLAP. Save and submit your solution in a
file named part8.jff.
This entry could start as src for all entries (src,dst) for which there is a valid direct edge, and it could start at -1 for those cells that do not have a direct edge. Then, the entries of this table could be updated appropriately as the Floyd-Warshall algorithm progresses!
Include these changes in your fw.java submission. Additionally, put a comment at the top of the file, to remind the graders that you did the extra credit.
L = { w | w contains only 0's and the length of w is a power of 2 }.
Although it is not regular, it is decidable. That is to say, there is a Turing machine that accepts it.
We highly recommend spending some time thinking about this problem and sketching a solution on paper before using JFLAP. If you design the Turing Machine carefully, you can build it using fewer than nine states. (Perhaps far fewer, especially if you let yourself write symbols other than 0 and 1 on the tape!)
Save your Turing Machine in a file called part9.jff.