**Note** (added Feb 9): Part A has been modified; you can do either the
original problem or a different problem (see Part A). For problem 2 in
Part B (the one with the shells), you can assume that no two of the shells in
your possession have the same value.

**Note: **Please include your Cornell NetID on your each section of your
homework. This simplifies the process of recording your grades.

**Note:** Because of scheduling constraints for homework grading, homework
assignments will usually be due on Wednesday instead of Friday as originally
planned.

- [Charged Particles] Do Problem 4 in Chapter 5 of the text.
*The solution to this problem requires the use the the FFT (Fast Fourier Transform) which is not usually covered as part of 482. For Part A, you can do this problem or the one below.*__OR__[Equivalent Bank Cards] Do Problem 3 in Chapter 5 of the text.

- [Local Minimum on a Tree] Do Problem 6 in Chapter 5 of the text.

- [Median-Only Sorting] Due to a series of unfortunate and unlikely events,
you find yourself on the island of
People-with-Very-Strange-Customs-Who-Only-Exist-in-Math-Puzzles. They
have an economy based on shells, but the value of each shell is determined
via some method that you haven't been able to comprehend (i.e., all the
shells look alike to you). Because you are a stranger, the islanders,
according to their custom, will always refuse to tell you which of two
shells is more valuable in any set of two shells, but they'll happily tell
you which shell is the median shell in any set of three shells. Also,
according to their custom, they refuse to tell you anything at all for sets
of more than three shells.
- Give an algorithm to find the pair of largest and smallest value shells
in a collection of
*n*shells using just O(*n*) three-shell queries. - Give an algorithm to sort your set of n shells using O(
*n*log*n*) three-shell queries.

- Give an algorithm to find the pair of largest and smallest value shells
in a collection of

- Al Gore-ithm has become concerned about global warming and has decided to
modify his energy consumption in order to minimize the amount of carbon
dioxide (CO
_{2}) produced. There are three electricity providers in his area, but all three providers, depending on seasonal weather and various other factors, change their electricity generating methods from week-to-week. Thus, for some weeks of the year company A might produce less CO_{2}and for other weeks companies B or C might produce less CO_{2}. Al would like to switch providers each week to make use of the one that produces the least CO_{2}, but switching creates extra CO_{2}(e.g., the companies have to send trucks out to his house).Here's an example using just two companies. Suppose that changing providers costs 40 units of CO

_{2}and that, over two weeks, using company A will cause the release 130 and 77 units of CO_{2}while using company B will cause release of 85 and 101 units of CO_{2}. If we use company B for the first week and then change to company A for the second week then the total released is 85 + 77 + 40 = 202. If we stay with company B for the whole two weeks then the total released is 85 + 101 = 186.

- So here's the problem: We have lists, a
_{1}, a_{2}, ..., a_{n}and b_{1}, b_{2}, ..., b_{n}and c_{1}, c_{2}, ..., c_{n}, of CO_{2}amounts over n weeks for companies A, B, and C, respectively. We also know p, the amount of CO_{2}released due to changing providers. Give an algorithm to determine which provider to use for each week so that total CO_{2}released is minimized. (Hint: think Dynamic Programming.)

- Suppose that company A has switched to trucks that burn only
bio-fuels. Now the amount of CO
_{2}released when switching to company A is reduced (but the switch-over cost remains the same for the other companies). Briefly explain how your algorithm should be changed to reflect this new information.

- So here's the problem: We have lists, a