This Problem Asks You to Find One False Coin Among a Set of True Coins: Computer Science Assignment, FI

Practical Activity 2: Algorithm Design

Purpose

To explore a classic computer science algorithmic problem.

Objectives

After completing this practical activity you should be able to:

• Explain a classic algorithmic problem.
• Understand how to approach an algorithmic problem.

Background

For this practical activity, you are not required to write a computer program. You will only be formulating an algorithm. You will follow the four phases used in discovering an algorithm as follows:

• Understand the problem
• Get an idea of how the algorithmic procedure might solve the problem.
• Formulate the algorithm and express it in English. Do not represent it as a program.
• Evaluate the program for accuracy and for its potential as a tool for solving other problems.

Activity

You are required to write a report on the following algorithm problem:

This problem asks you to find one false coin among a set of true coins. The false coin can be found because it doesn’t weigh the same as the rest of the true coins. It is either lighter or heavier, but you do not know in advance. The only method you have to make a decision is a classic balance scale with two trays.

You can put one or more coins on one tray, a similar number on the other tray, and determine which tray has the lighter pile. For instance, if you only have three coins then take coin 1 and coin 2 and weigh them. If the scale balances, then coin 3 must be the odd one out. If the scale doesn’t balance, then compare coin 1 and coin 3. If they balance then coin 2 must be the odd one out, while if they don’t then coin 1 must be the odd one out.

The key to the problem is to find the false coin using the fewest number of comparisons. What are the fewest comparisons for 3 coins? For 4 coins? For 5 coins? For 12 coins? For N, an arbitrary number of coins? This problem is traditionally stated with 12 coins.

Include the following in your report:

• Understand the problem: Describe how you worked with the problem and examples to develop an understanding.
• Get an idea of how an algorithmic procedure might solve the problem: Describe one or more general approaches to solving the problem, including how you got your foot in the door.
• Formulate the algorithm: Describe your algorithm in more detail.
• Evaluate your algorithm for accuracy and for its potential as a tool for solving other problems: Describe why you think your algorithmic solution is correct and why it might be better than other ideas you had.