Hi!! I need help with this problem please.. This is an Algorithm problem.. I don't need the code for it, just give the answer, analyze and explain it.... TIA

1. You are given k bricks, arranged in k stacks of height 1. In general, a "move" involves choosing a stack and redistributing all of its bricks into other stacks, but when doing this each of the stacks can receive at most one brick. During the move, you are allowed to make new stacks (in fact this is unavoidable if you don't have enough existing stacks in which to place all the bricks), but again only one brick can go in each new stack The reward of one move is precisely the number of bricks in the stack that you choose to redistribute. Suppose that you get to make some huge number of moves (say, n, far greater than k) (a) Develop a strategy to maximize your average reward per move (equivalent to max imizing the total reward over n moves). Express this as a function of k, using - notation. In other words your maximization doesn't have to be entirely precise; you may assume that k is any convenient number that will make the math easier for your strategy, but you cannot assume that k(1). Notice that any strategy provides a lower bound on reward optimality. The better the strategy, the better (higher) the lower bound (b) Use amortization (specifically, the potential method) to obtain an upper bound on the best possible average reward. This upper bound should match what you get in part (a), using -notation. If it helps to think in terms of cost instead, pretend that your friend is playing this game and it will cost you because you must pay their reward In this context, you want to find an upper bound on the total cost of your friend's n moves, without having the slightest idea of what their strategy is For amortization, as usual, you want to take advantage of the fact that "expensive" moves do not happen that often. Your potential function should create a potential difference that offsets expensive moves, making their amortized cost relatively smaller So, first think about defining what an expensive move is, and what a non-expensive move is. It will help to have a good strategy in part (a) to determine what the cutoff should be. Then think about something that changes a lot in the configuration of stacks whenever you have an expensive move, and use that as your then reverse- engineer . Always remember that when you evaluate , at any given time, you are taking a snapshot of the current state of the world. cannot be a function of "what changed" between two iterations. That is the job of (c) Instead of the potential method, use the accounting method. Explain why your accounting wor ks 1. You are given k bricks, arranged in k stacks of height 1. In general, a "move" involves choosing a stack and redistributing all of its bricks into other stacks, but when doing this each of the stacks can receive at most one brick. During the move, you are allowed to make new stacks (in fact this is unavoidable if you don't have enough existing stacks in which to place all the bricks), but again only one brick can go in each new stack The reward of one move is precisely the number of bricks in the stack that you choose to redistribute. Suppose that you get to make some huge number of moves (say, n, far greater than k) (a) Develop a strategy to maximize your average reward per move (equivalent to max imizing the total reward over n moves). Express this as a function of k, using - notation. In other words your maximization doesn't have to be entirely precise; you may assume that k is any convenient number that will make the math easier for your strategy, but you cannot assume that k(1). Notice that any strategy provides a lower bound on reward optimality. The better the strategy, the better (higher) the lower bound (b) Use amortization (specifically, the potential method) to obtain an upper bound on the best possible average reward. This upper bound should match what you get in part (a), using -notation. If it helps to think in terms of cost instead, pretend that your friend is playing this game and it will cost you because you must pay their reward In this context, you want to find an upper bound on the total cost of your friend's n moves, without having the slightest idea of what their strategy is For amortization, as usual, you want to take advantage of the fact that "expensive" moves do not happen that often. Your potential function should create a potential difference that offsets expensive moves, making their amortized cost relatively smaller So, first think about defining what an expensive move is, and what a non-expensive move is. It will help to have a good strategy in part (a) to determine what the cutoff should be. Then think about something that changes a lot in the configuration of stacks whenever you have an expensive move, and use that as your then reverse- engineer . Always remember that when you evaluate , at any given time, you are taking a snapshot of the current state of the world. cannot be a function of "what changed" between two iterations. That is the job of (c) Instead of the potential method, use the accounting method. Explain why your accounting wor ks