Class project CISC 7340						Due May 18, 2016

Choose one of the following projects (or one of your own devising) as your final project for the class. The project should involve using pthreads, OpenMP and MPI. Let me know by 04/13/2016 which one you have chosen. If you have an original project that you will be implementing, please write up a description for my approval by 04/13/2016.

  1. Implementing the Game of Life - theoretically an infinite two-dimensional array of cells. Each cell can be empty or holds one "organism". Each cell has eight neighboring cells which includes those diagonally adjacent. The rules of the game are:
    1. Every organism with two or three neighboring organisms survives for the next generation.
    2. Every organism with four or more neighbors dies from overpopulation.
    3. Every organism with one neighbor or no neighbors, dies from isolation (or loneliness.)
    4. Each empty cell adjacent to exactly three occupied nieighbors will give birth to an organism.

    The game is initialized with some cells occupied (this can be done randomly or in some ordered manner.) One generation amounts to inspecting each cell and deciding, according to the rules, what its fate is. The population is followed until:

    Program the game using a large array of cells. You can consider the edges to be special cases (only 3 or 5 neighbors) or use periodic boundary conditions. Try to discover what initial conditions lead to the three possible scenarios for ending the game.

  2. Implement a parallel accounting program. The program has to evaluate and classify thousands of receipts (already in a file) for a fiscal year. The program sums up the total amount spent in the year, and how much is spent in each category and sub-category.

    Categories and Sub-categories (this is just a sample, you can expand the list): 

    Business
	travel
	lunch - Business lunches only
	phone - land line and cell phone expenses
	equipment - miscellaneous office equipment

House
	mortgage
	home-ins - home insurance
	taxes - property taxes
	repair - home repairs

Essentials
	food
	clothing
	medical
	insurance - life, auto

Non-Essentials
	restaurant - non-business meals
	movie
	game
	beer
    A sample input file is shown below. The first line is the number of items. 
    5
movie	9.95
food	142.35
medical 350.00
travel  1455.00
    The program should process all the receipts and write out a nicely arranged summary of the total amount spent, the amount spent in each of the categories and sub-categories.

    Write your program two ways:

    1. Each process or thread gets a certain number of the receipts (in any category or sub-subcategory) classifies them and sums the results up. Then the results from each process or thread are combined and printed out.
    2. Each process or thread considers only a few sub-categories of receipts. For example, thread/process 0 considers travel and lunch receipts; thread/process 1 considers phone and equipment receipts, etc. The sub-category sums are done independently in the appropriate process. Then the results are communicated to the thread/process which will find the totals for the general categories and the final total. This thread/process prints out the results.
    Compare how efficient each of the two approaches are. Of course, they must get the same result.

  3. Given an N-dimensional sphere of radius r, centered at the origin of an N-dimensional coordinate system, compute the number of integer coordinate points inside the sphere. That is, the distance to the point from the origin is less than or equal to the radius. The following are some examples of results for different dimensions and radii:
    1. A three-dimensional sphere of radius 1.5 has 19 integer coordinate points within the sphere: 
      	five points in the circle formed when the first coordinate is -1:
	(-1,0,0), (-1,0,1), (-1,0,-1), (-1,-1,0),(-1,1,0),
	five points in the circle formed when the first coordinate is 1:
	(1,0,0), (1,0,1), (1,0,-1), (1,-1,0),(1,1,0),
	nine points in the circle formed when the first coordinate is 0:
	(0,0,0), (0,1,0), (0,0,1), (0,-1,0), (0,0,-1), (0,1,1), (0,1,-1), (0,-1,1), (0,-1,-1).
    2. A two-dimensional sphere (circle) of radius 2.05 has 13 integer coordinate points within the sphere: 
      	(0,0), (0,1), (0,2), (0,-1), (0,-2), (1,0), (1,1), (1,-1), (2,0), (-1,0), (-1,1), (-1,-1), (-2,0).
    3. A one-dimensional sphere (line) of radius 25.5 has 51 integer coordinate points: 
      	(-25), (-24), ..., (0), (1), (2), ..., (24), (25).
    First write the sequential code that will correctly handle any dimension N and any radius, r. Using the above data, convince yourself that it is working. Then develop the parallel algorithm. Make sure that your algorithm and code will scale as N and r increase.

  4. A two-dimensional array defines a set of streets in a part of a city. Many of the streets are one-way. In addition, there are several tunnels and bridges that allow the driver of a vehicle to drive over or under cross streets. The streets are numbered such that even numbers indicate east-west streets and odd numbers indicate north-south streets. Each row of the array has the form:

    For example, a row might be 13, 4, 6, 1, indicating that it describes a street numbered 13 in the block between streets 4 and 6 (going east-west) and is one-way in the direction from street 4 to street 6. If the row read as 13, 6, 4, 1, it would be one-way from street 6 to street 4. A row that contained 13, 6, 22, 2, indicates that street 13 is a two-way street and either a bridge or a tunnel links streets 6 and 22. You can assume that there are no entrances or exits between streets 6 and 22. Given the two-dimensional array (which you need to create), write a parallel or distributed code that does the following:

    1. Find the shortest path (fewest blocks traveled) that a vehicle could use to get from one intersection to another intersection without passing through any intersection more than once. The only intersections associated with bridges or tunnels are those at the two ends.
    2. Find the longest path (most blocks traveled) that a vechicle could use to get from one intersection to another intersection without passing through any intersection more than once.

    This problem involves a search through the possible paths.

  5. Implement a room assignment algorithm: