15110 Fall 2011 [Cortina/von Ronne]

Written Homework 12 - Practice Problems only

Reading Assignment

Read chapter 12 in the textbook Explorations in Computing.


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

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

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

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

  5. The floor tiling problem described in class in undecidable with the condition that we cannot rotate the tile designs that we are given. Explain why this problem becomes decidable (in fact, the answer is always YES) if we allow rotations.

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