Implementation Challenges

 

1. (*) Many types of products sold appeal more to members of one ethnic group than another. Perhaps Greeks eat more pasta per capita than Russians do, while Japanese find baseball more appealing than do Italians. A market researcher might be interested in having a program scan the names on a mailing list to select the ones most likely to be, say, Greek to target for a given mailing.

   Develop a program that makes reasonable mappings between pairs of first/ last names and ethnicities. One approach would be to compute the edit distance between query names and a family of names of known ethnicity. Feel free to experiment with other approaches.

2. (*) In the game of Battleship, the first player hides a collection of, say, three ships on a grid. The second player guesses a series of grid positions and is informed whether they hit or miss a battleship. The second player continues to query until each of the battleship positions has been probed. While the second player must succeed after making 100 different probes, we seek a strategy to use as few probes as possible to achieve the goal.

   Develop a program that tries to efficiently sink all the battleships. One reasonable algorithmic approach would be based on divide-and-conquer or binary search.

3. (*) A Caesar shift (see Section ) is a very simple class of ciphers for secret messages. Unfortunately, they can be broken using statistical properties of English. Develop a program capable of decrypting Caesar shifts of sufficiently long texts.