« Lecture #Syllabus for all sect | Main | Homework Syllabus for all sect »

January 17, 2006

Homework Syllabus for all sect

Consider the following algorithm for getting a drink of water in an apartment in which n roomates share n cups. 

 

Procedure get-drink (dirty: int, clean: int, n:int)

if (clean = 0) then 

   for (j = 1 to n) do wash-cup(j); 

   dirty = 0; 

   clean = n; 

drink-water(); 

return (dirty+1, clean-1,n)

Question 1 Use the accounting trick method to show that this algorithm runs in amortized constant time (meaning that it is O(1) when using amortized anlaysis). How many "tokens" will you deposit with each procedure call? Which instruction will you pick as the barometer instruction to measure withdrawals on each function call? Can you prove that the account will never go negative?

Question 2 Suppose that rather than using the get-drink algorithm above, the roomates decided to implement a "you use it, then you wash it" policy instead. Under policy, one would get a drink of water then immediately wash the cup so that all cups were clean at all times. Compare and contrast the amount of time required to get a drink of water under both policies. How does this related to the design of algorithms and data structures?

Question 3 Problem 4.19 page 142

Question 4 Problem 6.1 page 214


Note: Problem 6.2 and the question about Nephite Coinage were moved to Homework #4 for Jan. 23 (so if you started them already, you are still ahead on your homework).

Posted by jones at January 17, 2006 12:03 PM

Comments

Post a comment

Thanks for signing in, . Now you can comment. (sign out)

(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)


Remember me?