Homework 2

CS 482 - Spring 2007

Due: Wednesday, Feb 14

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.

Part A

  1. [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.

Part B

  1. [Local Minimum on a Tree] Do Problem 6 in Chapter 5 of the text.
     
  2. [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.
    1. 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.
    2. Give an algorithm to sort your set of n shells using O(n log n) three-shell queries.

Part C

  1. 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 (CO2) 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 CO2 and for other weeks companies B or C might produce less CO2.  Al would like to switch providers each week to make use of the one that produces the least CO2, but switching creates extra CO2 (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 CO2 and that, over two weeks, using company A will cause the release 130 and 77 units of CO2 while using company B will cause release of 85 and 101 units of CO2.  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.
     

    1. So here's the problem: We have lists, a1, a2, ..., an and b1, b2, ..., bn and c1, c2, ..., cn, of CO2 amounts over n weeks for companies A, B, and C, respectively.  We also know p, the amount of CO2 released due to changing providers.  Give an algorithm to determine which provider to use for each week so that total CO2 released is minimized.  (Hint: think Dynamic Programming.)
       
    2. Suppose that company A has switched to trucks that burn only bio-fuels. Now the amount of CO2 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.

    2.