PS12 SAMPLE ANSWERS - Spring 2018

1. The decomposition rule breaks the human's sentence
   into parts so it can be analyzed for specific keywords.
   Keywords trigger specific responses to be presented.

2. (a) 15x15 = 225 places to move for 1st player's first turn

   (b) 224 places to move for 2nd player's first turn
       so number of nodes on 2nd level is 225*224 = 50,400

   (c) 9th level below the root, because player 1 will have played 
       5 stones, and that player could have a 5-in-a-row, the other 
       player will have played 4

   (d) Complete game trees would be too large - you'd have something on the
       order of 225! possibilities at the end of the tree, and most of them
       are not strategic.  With heuristics, we can compute a reasonably
       good solution fast, so we can eliminate a large number of bad 
       moves at once and be more strategical, and won't have to search
       down possibly 150+ levels of millions of game possibilities to find
       out whether a move is good or not.

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.

       (NOTE: In this problem, flying from city A to city B may not cost
        the same as flying from city B to city A.)

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

4. For the monkey puzzle, if there are N cards arranged in a square,
   the number of monkeys to verify is 2*N - 2*sqrt(N):

   N     Number of monkeys to check
   9     2 * (3 * 2) = 2 * (sqrt(9)  * (sqrt(9) -1)) = 12
   16    2 * (4 * 3) = 2 * (sqrt(16) * (sqrt(16)-1)) = 24
   25    2 * (5 * 4) = 2 * (sqrt(25) * (sqrt(25)-1)) = 40

   For arbitrary N, where N is a perfect square:
   2 * (sqrt(N) * (sqrt(N)-1))      (typo corrected in formula)
   = 2*sqrt(N)*sqrt(N) - 2*sqrt(N)
   = 2*N - 2*sqrt(N)

   2*N - 2*sqrt(N) < 2*N which is O(N). 
   Computing something in linear time is reasonable.

5. (a) 3**11 = 177147 ways
       This is because each room has three color options and there
       are 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) Intractiblility means that to check if there is a valid 
       color assignment, one must check every possible combination 
       and there are an exponential number of possible combinations.  
       We do not know if there is a faster, polynomial time algorithm 
       to solve this problem in general for all instances of this
       problem. With an increase in the number of rooms, the number 
       of combinations that need checking goes up exponentially 
       and is out of our reach very quickly.  

6. (a) This formula is satisfiable because there is at least one
       assignment of variables that makes the expression true:
       A=False, B=True, C=True.

   (b) The only known algorithm to determine the satisfiability for 
       an n-variable logical formula is to try every possible 
       boolean assignment to see if any assignment leads to a 
       result of true. This is equivalent to building a truth table 
       for the n variables. Since each variable has
       2 possibilities (true or false), n variables will lead to 2**n 
       assignments that need to be checked in the worst case so the 
       algorithm is O(2**n).

7. (a) Y is in the set of programs A because it outputs a single integer 
       (1 or 2) and all of the programs in set A output a single integer.

   (b) If X analyzes Y and outputs EVEN, then Y outputs 1, contradicting
       what X says. If X analyzes Y and outputs ODD, then Y outputs 2, 
       contradicting what X says.

   (c) In this case, X cannot give a correct answer for program Y although
       Y is in the set of programs that X must be able to analyze. Thus, 
       a program cannot exist that can analyze ANY program that outputs 
       a single integer to determine if the output will be even or odd.