Overview:

Josephus Flavius was a famous Jewish historian of the first century at the time of the Second Temple destruction. During the Jewish-Roman war he got trapped in a cave with a group of 39 soldiers surrounded by romans. The legend has it that preferring suicide to capture, the Jews decided to form a circle and, proceeding clockwise around it, to kill every seventh person until only one was left, who must then commit suicide. Josephus, an accomplished mathematician, quickly found the safe spot in the circle (24th) to be the last to go. But when the time came, instead of killing himself he joined the Roman side.

The problem rightfully raises the question of how someone might be able to quickly compute the correct place to stand.

Objectives:

• Practice implementing and using a LinkedList data structure.
• Practice using interfaces

Instructions:

In this lab you are to simulate the Josephus problem. In the main driver Josephus.java you choose two integer parameters. The first number is the amount of soldiers in the problem (which will be ≥ 1), and the second number is an elimination order - the amount you rotate the list to remove the next soldier (it can be positive or negative integer or zero).

You remove nodes from the list according to the elimination order, for example, if that number is 2 than you need to remove each second person. You always start with the first node (labeled "1") and go to the end of the list removing nodes as it is specified. When you remove a node you continue the process moving to the next node. Once you reach the end you wrap around to the begining of the list. You repeat these steps until only one node is left. The following example demonstrates the sequence of steps:

size  = 5;       <- number of people
rotation = 2;    <- elimination order

        : 1 2 3 4 5        <- starting sequence
1st step: 1   3 4 5
2nd step: 1   3   5        <- wrap around
3rd step:     3   5
        :     3            <- survivor

size  =  5;        <- number of people
rotation = -3;     <- elimination order

        : 1 2 3 4 5         <- starting sequence
1st step: 1 2 3   5         <- to arrive at this result, count "1, 5, 4"
2nd step:   2 3   5         <- count "3, 2, 1"
3rd step:     3   5
        :     3             <- survivor

You are to implement DoublyCircularLL class and then solve the Josephus problem. This class implements ListInterface which shows which methods that you are expected to complete. After the class is properly implemented you can finish the josephusDCLL() method in the Josephus class.

Notes:

• you always start your rotations at node marked 1.
• the length of the list is always ≥ 1
• the elimination order could be larger than the list length
• in case of error throw an exception.

Test Cases

(size, rotation) = answer

(5,2) = 3
(5,-10) = 3
(5,1) = 5
(5,-5) = 5
(1, 5) = 1
(13,1) = 13
(40,7) = 24
(40,-7) = 18
(100,-2) = 29
(66,1) = 66
(66,100) = 7
(66,-100) = 61
(1000,123) = 2
(1000,-123) = 1000
(1000,1000) = 609
(1000,-1000) = 393
(-3,2) = exception
(3,0) = exception

Starter Code:

• MainDriver.java
• Josephus.java
• DoublyCircularLL.java
• ListInterface.java

What to submit:

1. Josephus.java
2. DoublyCircularLL.java

Do not submit anything else like zip files, folders, desktops, class files. Failure to do so will result in 10 points penalty.

Grading:

Your assignment will be graded first by compiling and testing it. After that, we will read your code to determine whether appropriate method/classes were used, as well as judge the overall style and modularity of your code. Points will be deducted for poor design decisions and un-commented, or un- readable code..