The first homework for this course will be a programming assignment in ZPL. You can look here to find out how to set up your environment to run zpl for this course. Look here for information on how to turn in homework files. This assignment involves writing two programs, as described below.
You are to write a ZPL program to implement the game of life. The rules of the game are fairly simple. I may be modifying the rules somewhat, so follow what I say here, rather than the form followed by versions you may have played with. The world is represented as a 2D square array. At each point in the array, there is either an organism or nothing. The initial world will be read in from a file named "life.in". This file will look something like the following example:
1 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1
The dimension of the space should be in a config var. This var should be set as a command line argument, or default to 4 if none is given. This is followed by the array, with a 1 indicating a life form, 0 indicating nothing. You will display the world, then prompt the user to evolve or quit. If they choose to quit, your program should exit. If they choose to evolve, it should do so according to the following rules:
Note that neighbor means adjacent up, down, left or right or diagonal.
1 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
Hit 'q' to quit, 'e' to evolve
e
0 1 1 0
1 1 1 1
0 1 0 1
0 0 0 0
Hit 'q' to quit, 'e' to evolve
e
0 1 1 0
1 1 0 1
0 1 1 0
0 0 0 0
Hit 'q' to quit, 'e' to evolve
e
0 1 1 0
1 1 0 0
0 1 1 0
0 0 0 0
Hit 'q' to quit, 'e' to evolve
e
0 1 0 0
1 1 1 0
0 1 0 0
0 0 0 0
Hit 'q' to quit, 'e' to evolve
q
We are learning about parallel computation here, so the world should be represented as a parallel array.
BONUS: Now that you have programmed life, can you explain it to us? I.e., what is the meaning of life (aside from a Monty Python movie)?
Given a directed graph G = (V, E), where V is a set of n vertices and E is a set of edges, the task is to find the shortest path between every pair of vertices. Initially, each vertex is assumed to be length 0 from itself, a given edge length from the nodes it shares an edge with, and infinite length from all other vertices. This initial set of edges should be read from a file "apsp.in". An example of such a file is below:
0 1 0 2 1 0 0 5 0 0 0 3 2 5 3 0
This matrix represents a graph like the following:
As in the previous problem, the dimension of the space should be in a config var. This var should be set as a command line argument, or default to 4 if none is given. I have used the value 0 for unconnected edges. You can assume the values will not be too large and simulate infinity by a big value (99999). To find the shortest paths (according to the Floyd-Warshall algorithm) you now go through n iterations. On each iteration k, set each element d[i,j] to min(d[i,j], d[i,k]+d[k,j]). The result for the above input should be:
0 1 5 2
1 0 6 3
5 6 0 3
2 3 3 0
As in the previous algorithm, the matrix here should be a 2D parallel array. Hint: use flooding.