### Project 21 - Josephus

 deliverable Josephus.java array_performance.png linked_performance.png due before 11:59pm Fri Apr 1st 2016 project id josephus

In this Lab, we will find out a solution to Josephus problem which is a famous problem in computer science. This is the definition of the problem according to Wikipedia:

"The problem is named after Flavius Josephus, a Jewish historian living in the 1st century. According to Josephus' account of the siege of Yodfat, he and his 40 comrade soldiers were trapped in a cave, the exit of which is blocked by Romans. They chose suicide over capture and decided that they would form a circle and start killing themselves using a step of three. Josephus states that by luck, or maybe by the hand of God, he and another man remained the last and gave up to the Romans."

The goal is to implement a method to solve this problem and compare performance like you did for project performance

1. Implement a method to simulate the Josephus problem. The parameters of the method should be a List<Integer> object and the count number. Because you are going to measure the time complexity of your method with different data structures, you can pass a List<Integer> object to your function so you could create a list in the main function and pass it to the method. Initialize the list with numbers 1 to N before passing it to the method. Do not shift members of the list when you want to remove an element, instead use the ListIterator<Integer>.remove method. The return value of the method should be the number of the last soldier standing.

Alternative settings that may be used for higher speed, but probably more noisy. (K=3)

• N=10000 to 100000 step:10000 trial:10
• N=5000 to 50000 step:5000 trial:10
Sample1:
java Josephus 10000 3 java.util.ArrayList
Last Soldier: 2692
Average Running Time: 0.0236288286

Sample2:
java Josephus 10000 3
Last Soldier: 2692
Average Running Time: 0.0013827713

Note1 You may not get the same timing as in sample output because of differences of computer speed and configuration. Always use 10 trials. Use a count of 3 for your Excel data and graphs.
Note2
Number the soldiers starting from one. Start the simulation from soldier #1 (0th index).
Note3 In Excel use red square markers for LinkedList and blue triangles for ArrayList, and add trendlines to them. Do not forget to enable the option to display the equation and the r squared value.

 Josephus.java Analyze the file (this may take a while):