SAMPLE ANSWERS - Computability

1. 
a.         Similar to the game with the monkeys, the canvases can be 
arranged in N! ways since the first can be arranged N ways with each next 
canvas after being able to be arranged 1 less way.
        
        N! = 12! = 479,001,600 ways
        
b. 479,001,600 minutes = 7,983,460 hours = 332,644 days = about 911 years

2.         
a.        There is no valid coloring of the map with three colors.  For 
example, you could not color each country surrounding Paraguay a different 
color since there are 3 surrounding nations.

b.        There would be 3**N possibilities for colors.
        3**13 = 1,594,323 color combinations
        
3.
a. (15-1)!/1000 checks per second = 87178291.2 seconds = approximate 2 3/4 
years. You use the (n-1)! because the first city (LA) is already 
determined so you don't actually have 15 cities to put into the tour but 
14 while always starting from LA.

b.
Adding one more city will increase the number of routes from 14! to 15!, an
increase of a factor of 15.

4.
a. 3^11=177147 ways
This is because each room has three color options and then multiplied 
together, we have a total of 11 rooms.

b.
It is possible to paint in the requested fashion.
T=Tan
W=White
Y=Yellow
 _________________________________________________
|               |    |         |         |        |
| MASTER   |    |    |            DINING |        |
| BEDROOM  |BATH|BATH| KITCHEN |  ROOM   |        |
|   (T)    | (W)| (T)|   (T)   |   (W)            |
|________  |____|__  |_  __   _|__     __|        |
|      |    HALLWAY(W)   |               | HOME   |
|       ________    _____                  OFFICE |
|      |      |          |                   (T)  |
| BED- | BED- |  FAMILY  |     LIVING    |        |
| ROOM | ROOM |  ROOM          ROOM      |        |
| (T)  |  (W) |   (T)             (Y)    |        |
|______|_________________|_______________|________|

c.
This is an instance of the map coloring problem. Given a color
assignment, we can check its validity in polynomial time.
(If there are n rooms, the maximum number of adjacent rooms is
n * n-1 which is O(n^2) which is polynomial.) To find the valid coloring, 
we could check every possible coloring of rooms which is an exponential 
algorithm (n!). We do not know if there is a faster, polynomial time 
algorithm to solve this problem in general. 

5.
Once tiles are allowed to rotate, we can technically use tile pattern 
to tile any room and simply turn it 180 degrees to match it up with 
itself.
 ___________
|  2  |  4  |
|1   3|3   1|
|  4  |  2  |
|-----------|
|  4  |  2  |
|3   1|1   3|
|  2  |  4  |
------------

6.
A problem is NP when it is P is because if you can solve the problem in 
polynomial time, you can obviously verify an answer in polynomial time
(just run the algorithm and see if you get the given solution).  
However, if a problem's solution is verifiable in polynomial time (NP) it 
does not necessarily mean that you can solve the problem in polynomial 
time.  

7.
 a) This is a decision problem because the algorithm must answer YES or 
    NO.

 b) If F executes itself as input then we get a contradiction.
    (When it runs with itself as input, program P is F itself.)
    If V responds that F will spread a virus, it outputs DONE and
    does not spread a virus, contradicting V.
    If V responds that F will not spread a rius, F spreads a
    virus, contradicting V.
    So no matter what V answers, F will do the opposite, so V cannot
    analyze F.

 c) This says that a universal virus checker V cannot exist in general
    to examine ANY program since F is one program it cannot examine.