15110 Fall 2011 [Cortina/von Ronne]
Written Homework 12 - Practice Problems only
Reading Assignment
Read chapter 12 in the textbook
Explorations in Computing.
Exercises
-
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.
-
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.
-
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)
-
Is this formula satisfiable? Why or why not?
-
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 | |
| | | | |
|______|_________________|_______________|________|
-
Using only 3 colors of paint (tan, white and yellow), how many different
ways can the owner paint the house? Explain your answer.
-
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.
-
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.
-
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.
-
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.
-
Explain why Y is one of the programs in set A.
-
Explain why there is a contradiction if Y outputs 1.
-
Explain why there is a contradiction if Y outputs 2.
-
What does all of this say about the existence of program X?