15110 Spring 2012 [Cortina/von Ronne]

Problem Set 11 - due Friday, April 27 in class

Reading Assignment

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

Instructions

Exercises

  1. (1.5 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.

    1. 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?

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

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

  2. (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?

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

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

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