Problem 1: The Josephus problem is the following mass suicide "game": n people,
 numbered 1 to n, are sitting in a circle. Starting at person 1, a handgun is
 passed. After m passes, the person holding the gun commits suicide, the body
 is removed, the circle closes ranks, and the game continues with the person
 who was sitting after the corpse picking up the gun. The last survivor is
 tried for n - 1 counts of manslaughter. Thus, if m = 0 and n = 5, players
 are killed in order and player 5 stands trial. If m = 1 and n = 5, the order
 of death is 2, 4, 1, 5. 
a). Write a program to solve the Josephus problem for general values of m and n.
 Try to make your program as efficient as possible. Make sure you dispose of cells.
b). What is the running time of your program?
c). If m = 1, what is the running time of your program? How is the actual speed
 affected by the free routine for large values of n (n > 10000)?



Problem 2: 
a) Write an array implementation of self-adjusting lists. A self-adjusting list
 is like a regular list, except that all insertions are performed at the front,
 and when an element is accessed by a find, it is moved to the front of the list
 without changing the relative order of the other items.
b). Write a linked list implementation of self-adjusting lists.



Problem 3:
A deque is a data structure consisting of a list of items, on which the
 following operations are possible:
push(x,d): Insert item x on the front end of deque d.
pop(d): Remove the front item from deque d and return it.
inject(x,d): Insert item x on the rear end of deque d.
eject(d): Remove the rear item from deque d and return it.

Write routines to support the deque that take O(1) time per operation.