15110 Spring 2013 [Kaynar/Gunawardena]

Problem Set 11 , Due Monday April 22

Reading Assignment

This assignment covers simulations and artificial intelligence. 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

Question 1: (3 pts) Give 3 examples where simulation can be very helpful before actually building a real system.

Question 2 (3 pts) The following question is based on the solar system simulation in Chapter 11 (and also displayed in class). In the simulation, you can watch how the planets orbit around the sun. By adjusting the masses of the planets, you can see how a change in mass affects the orbits. In the simulation, the program computes the force between every pair of objects in the simulation to determine their velocity and direction.

To run the simulation of our solar system using RubyLabs, we might type this in irb:
```
include SphereLab
b = make_system(:solarsystem)
view_system(b[1..5], :dash => 1)
30.times {update_system(b, 86459)}
```
What bodies of our solar system are visible in this simulation? Approximately what length of time is represented by this simulation?
Suppose you are simulating a solar system with 15 bodies. How many force calculations need to be computed for each time step?
If you ran a simulation for one time step for a solar system with n bodies, how many force calculations would be needed, expressed in big O notation?

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

What is the Turing Test? Describe this in your own words.
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? Think about the reasons for the differences in the quality of responses, based on what you know about natural language processing.

Question 4 (2 pts) In the game of Nim, we start with a pot of 15 marbles. Players take turns removing 1, 2, or 3 marbles from the pot. The player forced to take the last marble loses. Draw the root node and the next two levels of the game tree for Nim.

What is the maximum depth of the game tree?
Give a rough estimate or upper bound on the total number of nodes in the game tree. Explain your reasoning.