Programming Assignment 2 - Minimum Spanning Trees and Mazes

By three methods we may learn wisdom: First, by reflection, which is noblest; Second,
by imitation, which is easiest; and third by experience, which is the bitterest.
- Confucius

Due Thursday, Decemeber 1 at 11:59pm

Starting withyour lab1 implementation for either Java, C++or C#, perform the following tasks:

  1. Implement a Maze class, which creates and contains a grid and implements the IGraph interface. Add a edge data function that returns random values (make sure they are seeded by the two nodes, such that each direction has a random probability). Your maze should store an array (or arrays) of walls. Note, only have two edges per cell, since the neighbor shares an edge.
  2. Create a non-recursive graph traversal that uses a PriorityQueue or Heap (Java PriorityQueue), (C++ std::heap) to determine the next edge to traverse.
  3. Implement a concrete Visitor class within your maze class that knocks down walls as they are traversed.
  4. Use the above implementations to implement Prim's algorithm for a minimum spanning tree.
  5. Test you Maze generation.
  6. (Extra credit) Add some logic to print out your maze. You can use Unicode characters like the following (change you browser's encoding to UTF-8 or Unicode by right-clicking to get the context menu - IE). These are from: http://www.vidarholen.net/cgi-bin/labyrinth.
  7. (Extra credit) Implement a Dijkstra's Shortest Path to solve the maze. Test and validate.

chars=[' ','╶','╷','┌','╴','─','┐','┬','╵','└','│','├','┘','┴','┤','┼']

Include a README.txt file that explains how to build and run your program, the test cases selected and other implementation details.

Note, The traditional way of using Prim's algorithm to generate a maze would be to randomly pick an edge. Assigning random edge weights and getting the Minimum-Spanning Tree results in this random pick. However, as I mentioned in class, rand()/srand() and hence Random() is severely broken as rand is monotonic from srand. Use a large prime seed factor and a modulus operator to fix it.

Frameworks

You may use the following code base as a start if you wish or you can use your Lab1 results (with corrections pointed out by the grader). The sample provides an interface for the visitor and data accessor:

Submit Guidelines

Students in the 10:30 section should submit their labs to /submit/c680ab - use the UNIX command "submit c680ab lab2 projDir".

Students in the 2:30 section should submit their labs to /submit/c680ab - use the UNIX command "submit c680ab lab2 projDir".