15110 Fall 2011 [Cortina/von Ronne]

Written Homework 11 - due Friday, December 2 in class

Reading Assignment

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

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, lab section (A-N), and the assignment number.
• You must hand in your homework at the start of class on the given due date.

Exercises

1. (2 pts) The following questions are based on the simulations described in Chapter 11 (and in class).
   1. Write a function star() that guides the robot to draw a five-pointed star:

      

      Your function should use a loop since each side is drawn the same way.

   2. Suppose you are simulating a solar system with 20 bodies. How many force calculations need to be computed for each time step?

   3. If you ran a simulation with m time steps for a solar system with n bodies, how many force calculations would be needed, expressed in big O notation?

2. (2 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? How does the yearly contest determine if a program passes the Turing Test?

   2. The Loebner Prize for Artificial Intelligence was awarded in 2008 to Fred Roberts and Artificial Solutions. They created an online "bot" called Elbot. Hold a conversation with Elbot and observe some of its responses to your comments and questions. 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.

3. (1 pt) For each of the following regular expressions, describe specifically what type of strings would match.
   1. .a.e

   2. ch.*e

4. (3 pts) Visit the IBM Watson website and view the videos A System Designed For Answers, The Science Behind An Answer, and How Watson Works.
   1. How does Watson use concurrency?

   2. Outline the four main steps that Watson uses to answer a question on the Jeopardy! game show. Describe each step briefly in your own words.

   3. Watson also uses the principle of machine learning as it plays the game. Give an example of how Watson uses correct answers during a game to adjust its algorithms to improve its game play.

5. (2 pts) In the game of Connect Four, the play area consists of a vertical grid of 6 rows and 7 columns. Players (Red and Black) alternate turns, dropping a single disc of their own color into one of the columns. The disc will slide down as far as it can go. The object is to be the first player to get four discs in a straight line (horizontally, vertically or diagonally). We wish to build a game tree that analyzes all the available moves in the game to find the best 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?