15110 SUMMER SESSION TWO - 2014

Problem Set 10 - due Monday, August 4 at 9:00AM in class

Instructions

• Type or neatly write the answers to the following problems.
• Please STAPLE your homework before you hand it in.
• On the first page of your homework, include your name, andrew ID, and the assignment number.
• You must hand in your homework at the start of class on the given due date.

Exercises

1. (2 pts) In the simulation for the spread of the flu virus demonstrated in class, there were some subtle issues that we overlooked.
   1. When a person contacted four random people to see if any were contagious, the person could contact himself/herself. Why? (Explain using code from the simulation.)

   2. In the simulation, can such a person get infected by contacting himself/herself? Explain why or why not using the code in the simulation.)

   3. In the simulation, when a person contacts four people, they are not guaranteed to be different people. Explain why using the code in the simulation.

   4. Describe how you might use a list so a person can avoid contacting the same person twice or himself/herself in the simulation.

2. (1 pt) In a simulation for a solar system, there are n bodies that are moving around. Due to the effects of gravity, each pair of bodies exerts a force on each other. To determine this effect, we need to compute the force between two bodies. The force between two bodies is proportional to the product of the mass of the two bodies divided by the square of the distance between the two bodies. One time step in this simulation consists of the computation of this force for all pairs of bodies and then the repositioning of the bodies on the screen based on these force calculations. Note that the force between body A and body B is the same as the force between body B and body A, so this computation needs to be done only once for each pair of bodies, not twice.
   1. For a solar system with 9 bodies (the sun and eight planets), how many force computations need to be computed for one time step in this simulation?

   2. For a system with n bodies, how many force computations need to be computed per simulation time step, expressed using big O notation? Show your work.

3. (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.

   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?

4. (2 pts) ELIZA is a computer program that emulates a psychotherapist and was one of the first examples of natural language processing which is very important in the field of computing today (think: Siri, automated phone menus, etc.).
   1. Try a short conversation with the following "conversation bot" that simulates the ELIZA program:

      Eliza program

      Provide a transcript of your conversation until it is clear that you are typing with a bot, not a real human. Explain what it was in the responses that gave it away. (Remember that it is possible for a human to pretend to be a bot, so don't give up on the first odd response.)

   2. Read the following paper, written in 1966 as the field of artificial intelligence was emerging:

      ELIZA - A Computer Program for the Study of Natural Language Communication between Man and Machine by Joseph Weizenbaum

      (Focus on the introduction and the general description of the program, and on the implications in the Discussion section. You do not need to follow all of the detailed examples in the middle of the paper, although feel free to explore these if you wish. Note all of the data structures you know that are mentioned in the paper!)

      What is the function of a decomposition rule? What is the role of a keyword?

5. (1 pt) 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. Based on the website for the 2014 contest, how is a winner selected? If there is a winner, does this mean that a computer/application is truly intelligent?

   2. This year's contest is being held in Bletchley Park in the UK. What is the significance of this location?

6. (2 pts) View the following videos on Youtube: A System Designed For Answers, The Science Behind An Answer, and The Face of Watson.
   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 its machine learning power has been demonstrated on the Jeopardy! game show?

   4. Describe one challenge designers had in representing Watson visually to the viewer or one challenge designers had in representing Watson's voice.