PROGRAM #1
Fall 2008
Due: September 24, 2008, 5pm
General Guidelines:
- Each program project should be accompanied by a COVER SHEET (see details
below). Assignments without cover page will NOT be graded.
- This is an individual programming assignment. No team work
is allowed. You may consult with others (this is encouraged) or
refer materials online, but you MUST reference your sources (people,
books, webpages, etc.). These sources must be listed on the cover sheet
mentioned below (no points will be deducted). However, the final material for
submission should be entirely written by you. Directly reproducing source
codes or verbiage from online resources or other's people's assignments will
be considered plagiarism, and therefore will be awarded ZERO points and
subject to the WSU Academic Dishonesty policy. (Reproducing from the Weiss
textbook is an exception to this rule, and is encouraged wherever possible.)
- Grading will be based on correctness, coding style, implementation
efficiency, exception handling, source code documentation, and the written
report.
- Submission: All assignments with cover sheet should be
zipped or tarred into one archive folder (named after your last name), and
attached by email and sent to the instructor and all the TAs through the
eLearning website. Submissions are due by 5pm. A late penalty of 10% will be
assessed for late submissions within the next 24-hour.
- Note: Submissions will be accepted only through eLearning. Any other
submission outside the eLearning portal will be discarded.
Assignment:
The Josephus 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. The last remaining person wins.
Thus, if M=0 and N=5, players are eliminated in order, and player 5 wins. If M=1
and N=5, the order of elimination is 2,4,1,5 before 3 wins.
Your task is to provide two different implementations for the Josephus
problem using STL list and vector, respectively. Your program should build upon
the following source code:
- ListJosephus.h provides the required class
interface for the list implementation;
- VectorJosephus.h provides the required
class interface for the vector implementation;
- Person.h encapsulates each player in the game; and
- ElapsedTimeExample.cpp is an example
code that shows how to calculate processing time in C++.
Using the above source code, implement your own ListJosephus.cpp,
VectorJosephus.cpp, and Person.cpp. To test and report on your two
implementations, write two test programs called testListJosephus.cpp and
testVectorJosephus.cpp. These programs should follow the below test sequence of
steps:
- Instantiate an object of the corresponding Josephus class with a
user-specified N and M;
- Play a full game until a winner is found;
- Report the elimination sequence and the winner;
- Report the following time statistics: i) total time for playing the game,
ii) average time spent between two consecutive eliminations. The timing
statistics should be in seconds or milliseconds or microseconds
(whichever gives the closest precision to 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 a couple of 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
perhaps figures (if needed).
C: Experimental setup. In this section, you should provide a
description of your experiment setup, which includes but is not limited to
- Machine specification.
- What is your timing mechanism? i.e., what resolutions did you pick for
measuring different operations?
- How many times did you repeat each experiment?
- Were the time averages computed over multiple repeated experiments?
D: Experimental results. In this section, you should compare the
performance (running time) of the list and vector implementations, and provide
justification for your observations.
For your testing and reporting, conduct the following two sets of experiments
separately for each of your two implementations:
- Experiment #1: Keep M fixed at 3, and vary N in
powers of two starting from 4,8,16,32,.. up to 1,024. Go even higher if
possible, as long as the overall time is under a few minutes.
- Experiment #2: Keep N fixed (at say 512 or 1,024)
and vary M in powers of two starting from 2,4,8,... up to the largest power of
2 less than N.
In your report for the results, address the following points:
- Make 4 plots for each of your two implementations.
Plot I) total running time on y-axis vs. N on x-axis;
Plot II) average elimination time on y-axis vs. N on x-axis;
Plot III) total running time on y-axis vs. M on x-axis;
Plot IV) average elimination time on y-axis vs. M on x-axis;
- You must use some electronic tool (e.g., matlab, gnuplot, excel) to create
the plot - handwritten plots will NOT be accepted. The plots should be copied
into the report as an embedded object. Do not attach the source for the plot
generator.
- Provide a discussion of your results, which includes but is not limited
to:
- Which of the two implementations (list vs. vector) performs the
best and under what conditions? Does it depend on the input?
- How does the running time dependency on the parameter N compare
with the dependency on the parameter M?
- Support all your observations made with solid to-the-point
justification. For e.g., are the observations consistent with your
theoretical expectations or are they in contrary? If so, why? Any theoretical analysis
to help understand and explain the observations or discrepancies
conceptually will be the best form of justification.
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)