15110 SUMMER SESSION ONE - 2013

Problem Set 11 - due Wednesday, June 26 at 10:30AM in class

Reading Assignment

Read chapters 10 and 11 in the textbook Explorations in Computing.

For additional help with the last two questions, you might go to the OLI system and look at the last module on Computability.

Instructions

Exercises

  1. (2 pts) In the game of Gomuku, the play area consists of a 15 X 15 grid. Two players alternate turns, placing a piece (black or white) on the intersections of the grid lines as shown below:


    Source: http://en.wikipedia.org/wiki/Gomoku

    The object is to be the first player to get five adjacent pieces in a row, column or diagonal. move.

    1. Assume a game tree is built to analyze all possible moves in this game. Starting with a root node that represents an empty grid, how many nodes will be on the first level of the game tree below the root?

    2. How many nodes will be at the second level of the game tree below the root?

    3. At what level would the first leaf of the game tree occur? Why?

    4. Why would we use a heuristic to determine a player's move rather than a game tree?

  2. (2 pts) For each of the following patterns, describe specifically what strings would match.

    1. p1 = Pattern.new("pirates")

    2. p2 = Pattern.new("Eggs and (bacon|sausage|ham) for breakfast")

    3. p3 = Pattern.new("t...e")

    4. p4 = Pattern.new("t.*e")

  3. (1.5 pts) The Loebner Prize for Artificial Intelligence is awarded each year to the computer application that holds a conversation that most closely passes the Turing Test.

    1. What is the Turing Test? Describe this in your own words.

    2. The Loebner Prize for Artificial Intelligence was awarded in 2009 to David Levy of Intelligent Toys Ltd for Do-Much-More, a chatbot that converses with a user much like the Eliza program demonstrated in class. Read about the chatbot and observe some of its responses to the comments and questions from the judges of the competition. Were some answers better than others? Give an example of a good answer and why you think it was a good response (based on the principles of natural language processing), and give an example of a poor answer and why you think it was a poor response.

  4. (2 pts) View the following videos on Youtube: A System Designed For Answers, and The Science Behind An Answer.

    1. How does Watson use concurrency?

    2. List the four main steps that Watson uses to answer a question on the Jeopardy! game show.

    3. What can Watson really be used for, now that it's machine learning power has been demonstrated on the Jeopardy! game show?

  5. (1 pt) Britney Spears' management team is scheduling a concert tour for her comeback which will visit 15 cities including the first concert in her home town of Los Angeles. She will perform one show in each city. She has a private jet that will fly her directly from any city to any other city on her tour. The cost of each flight depends on many factors including availability of staff, landing fees at airports, etc. A computer can compute the total travel cost for 1000 potential concert tour schedules per second.

    1. How long will it take to determine the sequence of cities in a concert tour schedule that has the lowest total flight cost? Show your work.

    2. If Britney adds a 16th city to her tour, how many times longer will it take the computer to compute the lowest total flight cost? Explain your answer.

  6. (1.5 pts) A one-story house is shown below. The owner does not want any multi-colored rooms. Put another way, the owner wants to paint each room with a single color, but the colors of all rooms do not have to be the same color (but they could be). Hallways are considered rooms, but closets are not rooms and are not shown in the diagram. 

     _________________________________________________
|               |    |         |         |        |
| MASTER   |    |    |            DINING |        |
| BEDROOM  |BATH|BATH| KITCHEN |  ROOM   |        |
|          |    |    |         |                  |
|________  |____|__  |_  __   _|__     __|        |
|      |    HALLWAY      |               | HOME   |
|       ________    _____                  OFFICE |
|      |      |          |                        |
| BED- | BED- |  FAMILY  |     LIVING    |        |
| ROOM | ROOM |  ROOM          ROOM      |        |
|      |      |                          |        |
|______|_________________|_______________|________|

    1. Using only 3 colors of paint (tan, white and yellow), how many different ways can the owner paint the house? Explain your answer.

    2. Now, the owner adds another requirement that no two rooms that share a doorway can be painted the same color. Can this be done for the owner's house? Either show a valid color assignment for each room or explain why no such assignment is possible.

    3. Why is this problem considered intractable in general?