Project 21 - Josephus

 due  before 11:59pm Fri Apr 1st 2016
 project id

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.
  2. Repeat the experiment of project performance. Let the number of soldiers be N = 20000 to 200000 with steps of 20000 as the number of soldiers and a count of K. Set number of trials to 10. Record your result and draw two plots for LinkedList and ArrayList. If you program the solution correctly, then one plot will be a straight line and the other will be quadratic. Use an Excel spreadsheet to record your result, one column for N values, one for average time with LinkedList and one for average time for ArrayList. Use Scatter-Plot tools to graph the whole experiment. Using plot tools, add a trend line to each plot (choose best between quadratic and linear fitting for each graph). Use the option to show the 'r' value and the formula. Then Copy/Paste your plot into Microsoft Paint and save it as array_performance.png and linked_performance.png and turn them in (also turn in your program). Please label the graphs appropriately as well as ensuring that each performance graph is in the correct file.

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
java Josephus 10000 3 java.util.ArrayList
Last Soldier: 2692
Average Running Time: 0.0236288286

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.
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.

sadistics check
Analyze the file (this may take a while):
java logo
submit server
Control code:
file 1 =
file 2 = array_performance.png
file 3 = linked_performance.png

Ebad Ahmadzadeh,
Oct 27, 2015, 12:37 AM
Ebad Ahmadzadeh,
Mar 31, 2016, 5:45 AM