Prepare a polynomial-time algorithm

Reference no: EM13700071

Question: Consider a game with k piles of coins. Two players alternate turn. In each turn, they must remove some non-zero number of coins from one of the piles.

The player who takes the last coin loses.

An initial configuration is a sequence of values (P_1, P_2, ..., P_k) which show that pile i has P_i coins in it. We call such a configuration winning if the first player to act can force a win (i.e., force the other player to eventually take the last coin).

Program: Write a polynomial-time algorithm that, given an initial configuration (P_1, P_2, ..., P_k), decides if it is a winning configuration.

Prepare a polynomial-time algorithm that decides if it is a winning configuration.

Reference no: EM13700071

Questions Cloud

Prepare a function comp : We will use 'ft' 'mi' and 'm'.The function should return -1 if D1 in u1 is a smaller distance than D2 in U2; it should return 0 if they are equal distances. Should also return 1 otherwise.

Find there are still some left over in standard enumeration : find that there are still some left over in our standard enumeration. Does this mean that there are more Turing machines than programs?

Write an abstract data type : Write an abstract data type in C++ or Java (find which language you used) for rational numbers (a numerator and a denominator, both in integers).

Function that finds the smallest item in an arraybag : Write me a function that finds the smallest item in an ArrayBag (by reference) and returns true if the arrayBag is not empty and false otherwise.

Prepare a polynomial-time algorithm : Write a polynomial-time algorithm that, given an initial configuration (P_1, P_2, ..., P_k), decides if it is a winning configuration - Prepare a polynomial-time algorithm that decides if it is a winning configuration.

Algorithm to find the regular language : Exhibit an algorithm for determining whether or not a regular language L contains any string w such that \(w^{R} \in L\) - You need to prepare this algorithm to find the regular language.

Describe processes of top-down design stepwise refinement : Frank complains that defining functions to use in his programs is a lot of extra work. He says he will finish his programs much more quickly if he just writes them using basic control and operations statements.

Write a function fromhosttonetwork in c : Write a function fromHosttoNetwork in C that will accept an integer variable and covert it from host byte order to network byte order and write a function fromNetworktoHost in C that will accept an integer in network byte order and return an integ..

Suppose biological cell membrane has a specific capacitance : Suppose biological cell membrane has a specific capacitance of ~1μF/cm^2. Calculate the capacitance of a typical cell with diameter of ~10 μm. Suppose the membrane potential is -60mV, calculate the amount of net charge kept inside the cell. Calcul..

User Account

All Pages