Lab 1
Today we'll implement a circular linked list and use it to solve the Josephus problem. The problem is the following: in the "PG" version there are N people who wish to elect a leader by arranging themselves in a circle, and eliminating every Mth person, until one person is left. The question is which person will be the last one remaining. In the "R" version there are N people in a circle and every Mth person is executed, and the question is to find which one survives. We may act out the PG version of the problem in class :) You will need to write a program that takes N and M as arguments, and prints the identity of the last person remaining. Assume that the identities are 1,2,...,N and we start by eliminating the first person and go in ascending order. Use Josephus.java to start with, it already has an inner Node class, which holds an integer "id" and a reference to the next Node (this is all we need). You will need to create a circular linked list of N Nodes (the last Node points to the first), and then write code to remove every Mth Node until there is only one remaining. The identity of the remaining Node is the solution to the problem. Josephus.java already has a main that takes two arguments (M and N). As a reminder, you will first need to comple this program by executing javac Josephus.java, and then run it by executing java Josephus arg1 arg2. Please save your work in a directory called lab1 and gsubmit it at the end of the lab (we will be submitting labs from now on to encourage attendance :)).

Lab 1

Today we'll implement a circular linked list and use it to solve the Josephus problem. The problem is the following: in the "PG" version there are N people who wish to elect a leader by arranging themselves in a circle, and eliminating every Mth person, until one person is left. The question is which person will be the last one remaining. In the "R" version there are N people in a circle and every Mth person is executed, and the question is to find which one survives. We may act out the PG version of the problem in class :)

You will need to write a program that takes N and M as arguments, and prints the identity of the last person remaining. Assume that the identities are 1,2,...,N and we start by eliminating the first person and go in ascending order. Use Josephus.java to start with, it already has an inner Node class, which holds an integer "id" and a reference to the next Node (this is all we need).

You will need to create a circular linked list of N Nodes (the last Node points to the first), and then write code to remove every Mth Node until there is only one remaining. The identity of the remaining Node is the solution to the problem. Josephus.java already has a main that takes two arguments (M and N). As a reminder, you will first need to comple this program by executing

javac Josephus.java,

and then run it by executing

java Josephus arg1 arg2.

Please save your work in a directory called lab1 and gsubmit it at the end of the lab (we will be submitting labs from now on to encourage attendance :)).