Assume that you have a grid of live and empty cells, as in Assignment 0, plus a list of the locations of that grid containing live cells. The locations in the list are in row major order. This means that all the locations of live cells in a row come before all locations in lower rows and, within each row, the live locations occur in order from left to right. For example, the list of live locations in the first grid illustrated in Assignment 0 is
and, for the second grid, the list is
After your algorithm finishes, the grid must contain the next generation of cells and the list must consist of the locations of the live cells in this next generation (arranged in row major order). This means that your algorithm can be applied repeatedly to generate many generations.
The amount of work performed by your algorithm should be proportional to the number of live cells in the current generation. In particular, this means that your algorithm cannot create a new copy of the grid each time. (Why?)
Your algorithm should NOT depend on how the list is implemented (i.e. what data structure is used to represent the list). It should be written in English, not in Java or any other programming language. Use different levels of indentation to indicate the different levels of your design.
This part of your assignment must be typed on only one
piece of
paper (front and back). It is due 10 days before the rest of the assignment.
You are NOT allowed to hand in this part of the assignment late!
This includes implementing the new NextGeneration method described in part 1 and should include reimplementations of some of the other methods in the Grid class provided with Assignment 0. It may also include some new classes that are used by your new version of the Grid class. Your new version of Grid should not affect any other classes. In particular, the interface to Grid must remain unchanged. All code that you write should be properly commented.
In your report, state explicitly which methods in the Grid Class you changed and describe briefly how you changed them. Justify why you chose to change those methods, but not the others. Also explain and justify any decisions you made concerning the representation of the list, for example, what fields each node of your linked list contains and whether your linked list has a dummy node.
Thoroughly test your new version of the Grid class for correctness. Hand in the input and output from your testing. Explain what each test case is testing for. Justify the thoroughness of your testing.
This part of the assignment will be marked both by a person and by a computer program. Therefore, in addition to handing in a printed version of your Grid class and any auxilliary classes you have written, you should export them and hand them in electronically using the ``Hand in (submit)'' command.
Use the extended version of the Life.java class, called TimeOfYourLife.java, which is available from the course WEB page. It is the same as Life.java, except that it prints timing information after the last generation. There are also two new options for the command-line argument (in addition to text and pretty) to make the timing less tedious. The first is 'nodelay'. It works just like 'pretty' except that there is not a one-second delay between generations. The other option is 'none', which will give you no output other than the number of milliseconds it takes to run the program.
To get meaningful results, make sure you have no other applications running when performing your experiments. Note that, depending on how fast your computer is, you may need to run the program with a really large Grid or for lots of generations in order to notice any differences in time between versions. Also, your program may actually perform worse than the original did, especially if the grid size is small or you have lots and lots of cells that survive a long time. (Why?)
In your report, describe what experiments you performed, why you chose those experiments, what the results were, and your conclusions based on those results. You may find that graphs or charts may be helpful for presenting your results.
Because this part of the report is going to the boss of the company, it is particularly important that it is well written. It should not only have good English grammar and no spelling mistakes, but should state its case well.