15110 SUMMER SESSION TWO - 2014

Problem Set 11 - due Thursday, August 7 at 9:00AM in class

Reading Assignment

Read chapter 5 and Appendix A of the book Blown To Bits .

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 pt) Using the original IPv4 addressing scheme, a computer at Carnegie Mellon University has the IP address 128.2.13.161 .
1. What type of address is this: class A, class B, or class C? Why?
2. Based on your answer from part (a), what is the common prefix for all computers from this organization (i.e. what numbers of the IP address would be the same for all computers at this organization), and what is the maximum number of computers that this specific organization can connect to the Internet at one time?
(1.5 pts) The Internet is based on a number of different communication protocols. Specifically, we saw that TCP/IP is used to send messages on the Internet from one device to another.
1. What parts of the communication process is handled by IP (Internet Protocol)?
2. What parts of the communication process is handled by TCP (Transmission Control Protocol)?
3. Real Time Protocol (which streams voice/video data) is normally layered above UDP rather than TCP. What characteristics of TCP make it less desirable than UDP for streaming voice/video traffic?
(1 pt) Based on your reading in Blown To Bits, Chapter 5, you learned that today's encryption methods allow anyone to encrypt email and other data securely before being sent. The U.S. Government was very concerned about this type of technology since terrorists could use it to communicate without revealing their messages. What did the U.S. Government try to do in the 1990s to control this situation, and why did they give up trying to regulate encryption technology in the 2000s, even after the attacks of 9-11?
(2 pts) Consider a public key encryption system using RSA encryption that starts with two prime numbers p = 97 and q = 233. In this problem, you will compute values for the public and private keys and then encode and decode a message using these keys. (You should use python3 to help you with the large computations for this problem.)
1. Compute the public key pair (e, n) and the private key pair (d, n) for this system. First compute n. Then compute r = (p-1)*(q-1). Then select the smallest value for e such that e and r are relatively prime. Finally select the smallest value for d such that (e*d) % r == 1. Show your work.
  HINT: For e, divide 2 into r and see if it divides in evenly. If so, they're not relatively prime, so try 3 instead. If not 3, try 5, 7, 11, etc. until you find an e that does not divide in evenly. Then e and r are relatively prime.
  HINT: For d, once you know e, write a loop in Python that computes (e*d) % r for each d = 1,2,3, ... until you find a d such that the formula equals 1.
2. Consider the numerical message 15110 that is to be transmitted. What is the encrypted message that should be transmitted using this system? Show your work.
3. Verify that the receiver can decode the message from part (b) using the private key pair. Show your work.
(2 pts) Based on your reading in Blown To Bits, Appendix A, answer the following questions:
1. If you have ten computers at home all connected to the Internet via your ISP, how many unique IP addresses do you get? Briefly explain how traffic is routed to each computer.
2. Suppose an ISP company starts a service to sell music downloads. As part of this new venture, the company examines packets being sent to its users and slows down a user's connection if they detect packets from a competing music provider. Does this violate the principle of net neutrality? Why or why not?
(1 pt) Miley Cyrus' 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. Additionally, the flight from city A to city B may not cost the same as the flight from city B to city A. A computer can compute the total travel cost for 1000 potential concert tour schedules per second. At the end of the tour, she wants to fly directly back to Los Angeles.
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 Miley 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.
(1.5 pts) 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 general problem (i.e. painting any house with an arbitrary number of rooms using 3 paint colors so that no two connected rooms use the same color) considered intractable computationally?