Simulation - Data Structures and Problem Solving Using Java - page 524

Give a general formula for the winner of an N -player Josephus game
with M = 2.

13.8

Using the algorithm for N = 20, determine the order of insertion into
the BinarySearchTreeWithRank .

13.9

IN PRACTICE
13.10

Suppose that the Josephus algorithm shown in Figure 13.2 is imple-
mented with a TreeSet instead of a LinkedList . If the change worked,
what would be the running time?

Write a program that solves the historical version of the Josephus
problem. Give both the linked list and search tree algorithms.

13.11

Implement the Josephus algorithm with a queue. Each pass of the
potato is a dequeue , followed by an enqueue .

13.12

Rework the simulation so that the clock is represented as a double , the
time between dial-in attempts is modeled with a negative exponential
distribution, and the connect time is modeled with a negative expo-
nential distribution.

13.13

Rework the call bank simulation so that Event is an abstract base class
and DialInEvent and HangUpEvent are derived classes. The Event class
should store a reference to a CallSim object as an additional data mem-
ber, which is initialized on construction. It should also provide an
abstract method named doEvent that is implemented in the derived
classes and that can be called from runSim to process the event.

13.14

PROGRAMMING PROJECTS
13.15

Implement the Josephus algorithm with splay trees (see Chapter 22)
and sequential insertion. (The splay tree class is available online, but
it will need a findKth method.) Compare the performance with that in
the text and with an algorithm that uses a linear-time, balanced tree-
building algorithm.

Rewrite the Josephus algorithm shown in Figure 13.3 to use a median
heap (see Exercise 6.31). Use a simple implementation of the median
heap; the elements are maintained in sorted order. Compare the run-
ning time of this algorithm with the time obtained by using the binary
search tree.

13.16