Programming Assignment 1: Survivor using Arrays and Linked Lists
Due: Tuesday, June 26, 2007

Collaboration Policy

You may either work alone, or you may work with one other student if you wish. If you choose to work with someone, when turning in your assignment, you must note your partner's name. Make sure the division of labor is equitable and that you both understand the programming involved in the assignment.

Overview

Topic: Arrays and Linked Lists

The files you may need for this assignment are:

• ArrayGame.cpp
• ArrayGame.h
• Game.h
• GameOverException.h
• LinkedGame.cpp
• LinkedGame.h
• makefile
• Survivor
• Survivor.cpp

"Eeny-meeny-miney-moe, catch a tiger by the toe, if he hollers let him go, eeny-meeny-miney-moe. My mother told me to pick the very best one and you are not it."

Whomever is identified when the last word of the phrase is completed is eliminated from the game (erased from the list) and thus never counted again. The phrase is restarted with the following neighbor of the person most recently eliminated, and again a second person is removed based on the end of the phrase. A third and fourth player are removed in this way, continuing until there is only one person remaining. That person is the survivor!

Modeling the Game

The main parameters in modeling the game are the number of original people in the group, and the number of syllables used in the phrase for removing people. In this assignment, we will let N denote the number of players in the game and K denote the number of consectutive steps which are taken around the circle before the elimination of a player. Once a person has been removed from the group, they should never be counted again when counting steps.

For consistency, you should refer to the original players as if they are numbered from {0, ..., N-1}. Also, please start the game so that the first step is at Player 0. As a simple example, if we play the game with N=5 and K=3, players would be removed in the following order:

Player 2 is removed.
Player 0 is removed.
Player 4 is removed.
Player 1 is removed.
Player 3 has survived!

Please simulate the above example by hand. If you do not get exactly the same result as shown then you are misinterpreting the conventions for this assignment.

Your Task

For this assignment, you will be required to give two different implementations for simulating an abstract class game:

Part 1: ArrayGame

Maintain an array of booleans which will be used to represent whether or not a particular person has been eliminated. After initializing this array, you begin by removing people according to the rules of the game. You will need to take care when counting K steps, as you are not to count any players who had been removed in an earlier round.

Part 2: LinkedGame

Use a circular singly-linked list to represent the circle of players. You will still need to maintain a variable which references some node of the list so that you will be able to find the list!

In this implementation, rather than using a boolean to mark players as removed, you must actually remove each associated node from the linked list. In this way, when you later want to take K steps in the game, you will know that all of the players in the linked list are still part of the game.

Note: You will need to create your own Node structure in the LinkedGame.h file (declare it outside of the LinkedGame class).

Files We Are Providing

Game.h

This file formally defines the abstract class Game. In particular, it includes the following specifications:

The constructor - Subclasses should include a constructor with two, non-negative integer parameters, for specifying N and K, and should leave the game in its initial state with all players remaining, and player 0 the next to be 'counted' when a round begins.

int size() const - Returns the number of players who currently remaining in the game.

int playRound() throw(GameOverException) - Plays a single round, eliminating one player. This method can be called repeatedly to simulate several consecutive rounds of the game.

If there is only one player in the game, throws a GameOverException, rather than removing the last player.

The return value is The ID of the removed player.

int completeGame() - Completes the entire game, from the current state. (i.e. equivalent to calling playRound repeatedly until size is one).

The return value should be the ID of the sole surviving player.

bool toggleVerbose() - This method toggles the 'verbose' setting. The return value indicates the new setting.

The default behavior should be with verbose set to false, in which case no output is to be generated by the other methods.

If verbose is set to true, subsequent steps of the game should produce a message, printed to the standard output stream, to document the play of the game.

This method may be called more than once, if setting changes are desired while a game is in progress.

ArrayGame.h, ArrayGame.cpp

These files provide you with a starting point for implementing the ArrayGame class, though they are incomplete.

LinkedGame.h, LinkedGame.cpp

These files provide you with a starting point for implementing the LinkedGame class, though they are incomplete.

Survivor.cpp

This file provides a main driver to be used in testing your program. You will not need to modify this code.

makefile

This makefile should allow you to rebuild your project by simply typing make rather than in invoking the compiler directly.

Experiments

When the completeGame command is executed through our driver, it reports the amount of running time which was spent during the call to your routine. We would like you to use this in order to run some experiments regarding the relative efficiency of the two implementations.

For evaluating running time, always test your program with verbose set to false. Output to the screen would signficantly skew the measurements of the underlying efficiency of your methods.

Your readme file for this assignment should include two tables, one for each implementation, reporting the running times for each of the following cases:

* N=1000, K=1000.
* N=1000, K=10000.
* N=10000, K=100.
* N=10000, K=1000.
* N=10000, K=10000.

Files to Submit

Programming assignments are due at midnight of the day they are due. You are allowed to submit your assignment via email to the TA, but you must also get a hardcopy of your assignment to the TA by the following day.

Source Code
Please submit all source code files which you have either modified or added. At minimum, we expect this to include the four files (ArrayGame.h, ArrayGame.cpp, LinkedGame.h, LinkedGame.cpp).

Readme File
For every assignment, you will be asked to submit such a text file. In general, this provides a way for you to add any further comments you wish to make to the grader. For this assignment, please make sure to explain the design decisions you made in regard to the ArrayGame and LinkedGame classes.

Testing Your Program

One good test is to make sure that both implementations actually give the same output when run with identical parameters. Secondly, you should certainly test your programs versus the example given earlier in this assignment. If you would like a few more answers to compare to, here is the survivor for several other cases:

* N=5, K=30: player 2 has survived.
* N=30, K=30: player 28 has survived.
* N=100, K=30: player 14 has survived.