C++ Question: The Josephus problem is the following game: N people, number 1 to N, are sitting in a circle. Starting at person 1, 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.

Write a program to solve the Josephus problem for general values of M and N.

The goal of this assignment is to identify the performance and implementation tradeoffs between various ADTs (linked list, vector).

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:

VectorMyJosephus.h

ListMyJosephus.h

Using the above source code, implement your own VectorMyJosephus.cpp and ListMyJosephus.cpp. Feel free to add more functions as needed for your implementation. The above source code is provided to give you a template to start with. You will have to make whatever changes necessary to complete, compile and get it working.

For your testing, conduct the following two sets of experiments separately:

Experiment #1: Keep M fixed at 3, and vary N in powers of two starting from 4,8,16,32,.. up to at least 262,144. Go even higher if possible, as long as the overall time is under a few minutes.

Experiment #2: Keep N fixed (at say 262,144) and vary M in powers of two starting from 2,4,8,... up to the largest power of 2 less than N.

What to submit:

Complete set of source code.

A simple report (in doc or PDF) on your experimental Results. You should report and compare the performance (running time) of the list and vector implementations based on your observations, and provide justification for your observations.