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;
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
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.)