Gourd Clocks

Dennis Shasha

Omniheurist Course

Computer Science


 

Description

You are given identical gourds having the property that opening one hole will make the gourd drain at a rate r1 and opening two holes will make the gourd drain at a rate r2. Refilling an empty gourd takes zero time. You want to mark time based on one form of observable event: a gourd becomes empty. Your task is to construct a sequence of hole opening, refilling, and pouring (from one gourd or several gourds into anothrr one) that will allow you to count minutes as soon as possible starting from the beginning.

For example, suppose you have five gourds. r1 is 1/11 per minute and r2 is 1/5 per minute. How can you construct a sequence of pourings, refillings etc. to begin to count minutes after 9 minutes? You are to program this on your own using a synchronous, cooperative parallel algorithm. You will be given r1 and r2 and are to figure out how to make the gourds count minutes in as short a time as possible.

Architecture Team Spec