1.Jeff and Diamond like playing game of coins,One day they designed a new set of rules:

1)Totally 10 coins

2)One can take away 1,2or 4 coins at one time by turns

3)Who takes the last loses.

Given these rules Whether the winning status is pre‐determined or not

2. The UI specialist Dafna found a problem that some of the Items on the marketing

document form overlapped with each other. Because this form was implemented by different

developers and they didnʹt care the particular appearance of one item. Product manager

Tidav decided to write one small checking tool to generate the overlapped items on all forms.

He called in his guys to discuss about it. Suppose the input is the integer coordinates (x,y)od

the items (all rectangles) on one form. Construct an efficient method to find out the

overlapped items. Hint: The most direct way to do so is comparing each items with the others,

Given 1000 forms. Each with 100‐1000items on average. The O(n2) algorithm is costly.Some

guru suggested that one O(n) method could help only if 6.5 kilobytes extra storage is

available. One elite argued that he could cut down the number to 1%,Itʹs now your turn to

describe the idea. Write out the pseudocodes, vertify his algorithm and propose more

advanced optimization if possible.

3 in a file system ,data need not be sequentially located in physical blocks, We use a number

of tables storing nodes imformation. Suppose now we use a fixed node size of variable‐length

n, it takes [n/(k‐b)] nodes to store this item.(Here b is a constant, signifying that b words of

each node contain control information, such as a link to the next node).If the average length n

of an Item is N,what choise of k minimizes the average amount of storage space required?

(Assume that the average value of (n/(k‐b)) mod 1 is equal to 1/2 ,for any fixed k, as n varies)