Although each problem ultimately asks for a proof, this does not preclude your using a computer to assist. However, your written explanations must be convincing to a human reader. This is data structure question. please explain all answers.

Buried Treasure. You wake up at the origin of the Cartesian plane. Your cow snuck off in the night, taking your steel MacGuffin with it! Stop, thief! Like all cattle thieves, your cow has buried the treasure exactly six feet below the plane. Fortunately, you have a metal detector, that is sensitive enough to detect the treasure from any point in the plane whose (x,y) coordinates are within one unit of those of the treasure. A friend catches your cow and returns it to you, informing you that it was found within 10 units of the origin. Since your cow is pretty lazy, you decide that the treasure must also be within 10 units of the origin. Your mission: plan a trajectory that brings you within 1 unit of every point where the treasure might be located. Your cost = the distance you have to travel along your trajectory before you detect the treasure, plus 1 for the remaining distance to the treasure, plus 10 for the cost of digging up the MacGuffin and dragging it home. Problems: 1. Specify a deterministic trajectory, and prove an upper bound on its cost. 2. Prove a general lower bound on the worst-case cost for every deterministic trajectory. 3. For the same, or a different deterministic trajectory, prove an upper bound on its competitive ratio, compared with an omniscient trajectory. 4. Prove a general lower bound on the worst-case competitive ratio for every deterministic trajectory. Bonus: solve any of the above problems again with "randomized" in place of "deterministic." Buried Treasure. You wake up at the origin of the Cartesian plane. Your cow snuck off in the night, taking your steel MacGuffin with it! Stop, thief! Like all cattle thieves, your cow has buried the treasure exactly six feet below the plane. Fortunately, you have a metal detector, that is sensitive enough to detect the treasure from any point in the plane whose (x,y) coordinates are within one unit of those of the treasure. A friend catches your cow and returns it to you, informing you that it was found within 10 units of the origin. Since your cow is pretty lazy, you decide that the treasure must also be within 10 units of the origin. Your mission: plan a trajectory that brings you within 1 unit of every point where the treasure might be located. Your cost = the distance you have to travel along your trajectory before you detect the treasure, plus 1 for the remaining distance to the treasure, plus 10 for the cost of digging up the MacGuffin and dragging it home. Problems: 1. Specify a deterministic trajectory, and prove an upper bound on its cost. 2. Prove a general lower bound on the worst-case cost for every deterministic trajectory. 3. For the same, or a different deterministic trajectory, prove an upper bound on its competitive ratio, compared with an omniscient trajectory. 4. Prove a general lower bound on the worst-case competitive ratio for every deterministic trajectory. Bonus: solve any of the above problems again with "randomized" in place of "deterministic