Instruction Set for an Ambitious Ant In this exercise, you will specify an instr
ID: 3541375 • Letter: I
Question
Instruction Set for an Ambitious Ant
In this exercise, you will specify an instruction set. This is just a list of primitive
operations, not an algorithm. Analogy: When you bake a cake, the list of ingredients is
everything you need to buy, but the recipe is a step-by-step procedure (algorithm). All
we want here is the list of ingredients, not the procedure. However, you may need to
briefly sketch an algorithm anyways, to convince yourself and the reader that your
instruction set is complete enough.
An ant has N job offers. These are arranged in a straight line along a branch.
The ant can move in any direction. He can detect each job site as he moves past.
He knows theyre all on this branch. He knows when hes at the end of the branch.
Each job offer pays in sugar grams per hour. No two offers pay the same amount.
The ant doesnt know arithmetic, but he carries a gram-weight pan scale, which can
weigh any two amounts. A pan scale returns 3 possible qualitative results: tips left,
balances, and tips right. The ant understands these 3 results.
Each job site will weigh out, on request at its help desk, an amount of sand equal to
1 hour of its sugar pay rate.
The ant can carry sand in either or both pans as he moves, without spilling any. He
can distinguish an empty pan from a non-empty pan. He can pour out a pan at will.
The ants goal is to find the job that pays the most sugar mass per hour, and move in
there. Describe an instruction set that the ant could use to accept his highest-paying job.