CLICK HERE TO DOWNLOAD THIS ANSWER INSTANTLY $24 Only
Q1) The linked list, L, and linked list, P, contain integers sorted in ascending order. The
operation PrintLots(L,P) will print the elements in L that are in positions specified by P.
For instance, if P = 1, 3, 4, 6, the first, third, fourth, and sixth elements in L are printed.
Write the procedure PrintLots(L,P). You should use only the basic list operations you
define. Your main program and data structure list are given on the course website, which
read data in the following format from DataIn file, and then call PrintLots(L,P) to print
the selected elements.
Sample input data format:
N1 N2
X X X . . .
X X X . . .
/* N1 is the num of data items in L, and N2 is the num of data items in P. The second
line contains the data items in L, and third line the data items in P. */
Q2) The Josephus problem is the following game: N people, numbered 1 to N, are sitting
in a circle. Starting at person 1, a hot potato is passed. After M passes, the person holding
the hot potato is eliminated, the circle closes ranks, and the game continues with the
person who was sitting after the eliminated person picking up the hot potato. The last
2 remaining person wins. Thus, if M=0 and N=5, players are eliminated in order, and
player 5 wins. If M=1 and N=5, the order of elimination is 2, 4, 1, 5 and winner is 3.
a. Write a C 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 disclose of cells
eliminated (hint: use linked list).
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 > 10,000)?
Sample input data format:
N M
/* N and M are as defined by the question. Your program should print out both the order
of elimination and winner. Show the answers for question Q4 (b), (c) in a text file named
Q4-ans under the same subdirectory Q4. */
