PROGRAM #1

Fall 2011

Due: September 21, 2011, 5pm, submission on Angel


General Guidelines:


ASSIGNMENT:

The goal of this programming exercise is to identify the performance and implementation tradeoffs between the linked list and array data structures, by implementing the following game.

The MyJosephus problem is the following game: N people, numbered 0 to N-1, are sitting in a circle. Starting at person 0, a hot potato is passed. After M passes, the person holding the hot potato is eliminated, the circle closes ranks, and the game continues with the person who was sitting after the eliminated person picking up the hot potato to begin the next round of passing. The game is played until only one person is left, and that last remaining person wins. For example, if M=0 and N=5, players are eliminated in order, and player 4 (i.e., the 5th player) wins; If M=1 and N=5, the order of elimination is 1,3,0,4 before 2 wins.

An animated example for M=2, N=5 is provided here.

Your task is to provide two different implementations for the MyJosephus problem using STL list and vector, respectively. Your program should build upon the following source code:

Using the above source code, implement your own ListMyJosephus.cpp, VectorMyJosephus.cpp, and Person.cpp. Feel free to add more functions as needed for your implementation.  The above source code is only given as a template to start with.

For testing and reporting, implement two separate test programs called testListMyJosephus.cpp and testVectorMyJosephus.cpp. These programs should implement the following steps:

  1. Instantiate an object of the corresponding MyJosephus class with a user-supplied parameter values for N and M;
  2. Play a full game until a winner is found;
  3. After each elimination round, output the list of players still left in the game, starting from the lowest player id.
  4. At the end of the game, report the elimination sequence and the winner;
  5. Report the following timing statistics:
        i) total time for playing the game,
        ii) average elimination time which is the average for the time spent between two consecutive eliminations.
        While recording both these times, do NOT include time to print the pending list after each round. Basically, comment out that line which calls the print function for timing measurements.
  6. The timing statistics should  be in seconds or milliseconds or microseconds (whichever gives the closest precision to measure the actual time of the event).

REPORT:

In a separate written document (in Word or PDF), compile sections A through D  as below:

  • A: Problem statement. In one or two sentences, summarize the goal of the problem.
  • B: Algorithm design. Within one page, provide a brief description of the main ideas behind your algorithms for the two implementations. You can do this in the form of a step-by-step pseudocode (in plain English) along with figures (preferred).
  • C: Experimental setup. In this section, you should provide a description of your experiment setup, which includes but is not limited to
  • D: Experimental Results & Discussion. In this section, you should compare the performance (running time) of the list and vector implementations, and provide justification for your observations.

    Results:
    For your testing and reporting, conduct the following two sets of experiments separately for each of your two implementations:

    In your report for the results, address the following points:

    Discussion:


  • COVER SHEET:

        Each submission should be accompanied by a cover sheet which is a single page document that contains all the information listed in this sample cover sheet: Word or PDF. Assignments without a cover sheet will NOT be graded.


    CHECKLIST FOR SUBMISSION:

        ___  Cover sheet

        ___  Zipped folder of the source code

        ___  Written report

        ___  All the above three zipped into another folder archive (named after your last name)