15110 Fall 2012 [Touretzky/Kaynar]

Problem Set 12 - For practice only

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

Chapter 5 of Blown to Bits describes the "key agreement protocol" of Diffie, Helman, and Merkle that allows two people to agree on a secret key even though their communication is conducted in public. The protocol depends on a special one-way function which is written as x*y, but it is not ordinary multiplication. We will use f(x,y) to denote this one-way function.
1. What is a one-way function?
2. Suppose we define f(x,y) to be x**y % 9973. Assume that Alice picks 37 as her secret number a, and Bob picks 52 as his secret number b. Assume the "industry standard" constant g is equal to 29. (In reality all three numbers would be much larger, but we want to keep things simple.) Explain step by step how Alice and Bob arrive at a shared secret key, and what that key is. Use Ruby to do the calculations.
3. Before typing your credit card number into a web browser, you should check to see that the web store is using the https protocol instead of http, so that your communication with the store is encrypted using a standard cipher such as AES (Advanced Encryption Standard) or Blowfish. What role do you think the key agreement protocol plays in keeping your transaction secure?
Consider the flu virus simulation example covered in class. Suppose that we use the Canvas to actually represent the physical proximity of people in the population. That is, any cell represents a person and the cells adjacent to that cell represent that person's "neighbors" (there are at most 4 neighbors of a cell). Moreover, we change our assumption about how a healthy person gets infected. We now assume that a healthy person gets infected if at least one of her neighbors are contagious.
1. Describe what change needs to be made in the function update. Note: Be careful about accessing the cells that may lie outside of the canvas.
2. How would you further modify the function to say that a healthy person gets sick with probability 60% if at least one of hers neighbors are contagious?
3. Suppose that you want to be able to replicate the simulation: whenever you run the simulation you will have the exact same evolution for the spread of the flu virus. What part of the code ( test_update ) you need to change and how?
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?
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.
1. Draw the root node and the next two levels of the game tree for Nim.
2. What is the maximum depth of the game tree?
3. Give a rough estimate or upper bound on the total number of nodes in the game tree. Explain your reasoning.
String matching.
1. Suppose that we create a string s using the following assignment statement in irb.
```
>> s = "The last problem set"
=> "The last problem set"
```
  State what s.scan(r) would return for each of the following values for the regular expression r.
```
r = /./
r = /.*/
r = /..*/
r = /s./
r = /.*m/ 
r = /l|p/
```
2. What would be the output of running the following expression in irb be?
```
"Good morning".scan(/../) {|text| puts text}
```
3. Consider the ElizaLab module in RubyLabs. For each of the following patterns, describe specifically what strings would match.
  - p1 = Pattern.new("pirates")
  - p2 = Pattern.new("Eggs and (bacon|sausage|ham) for breakfast")
  - p3 = Pattern.new("t...e")
  - p4 = Pattern.new("t.*e")
4. What would p4.regexp return? What does it show about how ElizaLab module implements patterns?
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? Think about the reasons for the differences in the quality of responses, based on what you know about natural language processing.
The material needed to answer the following questions will be covered in Unit 14 after Written Exam 3.
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.
The implication operator → is a boolean operation on boolean values A and B such that A → B is false only when A is true and B is false; otherwise, A → B is true.
Consider the following logical formula: ¬(A ∧ B) ∧ (A → C) ∧ (C → B)
1. Is this formula satisfiable? Why or why not?
2. The formula above has 3 variables. If the formula had n variables, what is the only known algorithm (at this time) that can determine if the formula is satisfiable? What is the worst-case order of complexity of this algorithm?
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?
The class P represents those problems that can be solved in polynomial time. The class NP represents those problems with a solution that can be verified in polynomial time. Consider the traveling salesperson problem where we want to find a tour of the N cities that costs at most K. Explain why this problem is in NP.
Let A be the set of all programs such that each program in this set has no input and outputs a single integer as its answer after it does its computation. For example, the program that computes and prints out the sum of the integers from 1 to 100 is one of the programs in this set. Now, let X be a new program that analyzes any program from the set A. If the program it analyzes outputs an even integer, X outputs the word "EVEN"; otherwise it outputs "ODD". Finally, let Y be a new program that runs X to analyze itself (Y). If X outputs "EVEN", then Y outputs 1. If X outputs "ODD", then Y outputs 2.
1. Explain why Y is one of the programs in set A.
2. Explain why there is a contradiction if Y outputs 1.
3. Explain why there is a contradiction if Y outputs 2.
4. What does all of this say about the existence of program X?