PRACTICE EXAM 2 SAMPLE ANSWERS

1.
a) (first (rest (rest ethel)))

b) (null? people) checks if the list named people is empty.  
   
c) (mysteryfunction (list alice bob carol dan ethel fred))
   = (+ 1 (mysteryfunction (list bob carol dan ethel fred)))
   = (+ 1 (+ 1 (mysteryfunction (list carol dan ethel fred))))
   = (+ 1 (+ 1 (+ 1 (mysteryfunction (list dan ethel fred)))))
   = (+ 1 (+ 1 (+ 1 (+ 1 (mysteryfunction (list ethel fred))))))
   = (+ 1 (+ 1 (+ 1 (+ 1 (+ 1 (mysteryfunction (list fred)))))))
   = (+ 1 (+ 1 (+ 1 (+ 1 (+ 1 (+ 1 (mysteryfunction (list ))))))))
   = (+ 1 (+ 1 (+ 1 (+ 1 (+ 1 (+ 1 0))))))
   = (+ 1 (+ 1 (+ 1 (+ 1 (+ 1 1)))))
   = (+ 1 (+ 1 (+ 1 (+ 1 2))))
   = (+ 1 (+ 1 (+ 1 3)))
   = (+ 1 (+ 1 4))
   = (+ 1 5)
   = 6  (This function counts the number of people in the list)

d) Yes, it is recursive because the function calls itself.


2. 
a)                   _______ C(4,2)_______
                    /                     \
              C(3,2)                       C(3,1)
             /     \                     
       C(2,2)      C(2,1)            


b)    C(4,2) = C(3,2) + C(3,1)

               C(3,2) = C(2,2) + C(2,1)
                        C(2,2) = 1 (since R = N)
                                 C(2,1) = 2 (since R = 1)
               Thus, C(3,2) = 1 + 2 = 3

               C(3,1) = 3 (since R = 1)

      So C(4,2) = 3 + 3 = 6.

c) In this case, no. But in general, the answer would be yes, since
   the same recursive computation might show up more than once in the 
   recursion tree.  If we used dynamic programming then we could 
   store the value of that computation after the first time, and just look
   it up when we wanted to use it the second time, instead of 
   recalculating it again.


3. Key:   A = 00
          B = 010
          C = 0110
          D = 0111
          E = 1

a) EBEDEACEAEEB

b) 3 bits, because we have 5 letters.  2 bits only gives us 4 different 
   encodings, so we need one more bit. 3 bits gives us 8 different 
   encodings, which is enough (use 5 of these 3-bit patterns, and
   leave 3 of them unused).

c) message --> letter { letter }
   letter --> 00 | 010 | 0110 | 0111 | 1


4.
a) not easy in a text file - left for the reader :-)

b) L(Z) = 0 by definition
   L(X) = 2 since X leads directly to Z only
   L(Y) = 9 since Y leads directly to Z only
   L(V) = min( weight(V,X)+L(X), weight(V,Y)+L(Y) ) = min(6+2,5+9) = 8
   L(W) = min( weight(W,X)+L(X), weight(W,Y)+L(Y) ) = min(8+2,3+9) = 10
   L(U) = min( weight(U,V)+L(V), weight(U,W)+L(W) ) = min(7+8,4+10) = 14

c) Let us follow a greedy algorithm.  The following is the sequence of 
   edges chosen starting from U.  At each node, choose the lowest cost
   edge as you move toward the destination.
   (U,W) = 4
   (W,Y) = 3
   (Y,Z) = 9
   total = 16.  
   
   But if you look at the answer to part B, you can see that the shortest 
   path actually only costs 14. So the greedy algorithm did not work for 
   getting the shortest path from U to V in this case.


5.
a) result = x * i
   x = x * i  (due to step 1)
   x = x * 1  (due to step 2)
   x = x      (true)

b) At beginning of each iteration, assume:
      result = x*i
   After step a, we add 1 to i:
      result = x*(i-1)  (since i is now one bigger, but result hasn't changed)
   After step b, we add x to the result:
      result = x*(i-1) + x 
             = x * (i-1 + 1) = x * i (which is the invariant again)
   Therefore, if the invariant is true at the start of each iteration,
   it will also be true at the end of each iteration.

c) After loop the invariant should still be true (since it is true at
   the end of the last iteration and the loop condition does not change
   the invariant in any way).  Also, we know that i = y once the loop
   is completed.  Thus we can conclude that 
      result = x * i  AND  i = y    ==>     result = x * y 
   So the loop must be computing what we intended all along.

d) (Assume x and y are both integers.) We know that i starts at 1, and y 
   must be greater than 0.  So i will always start out as less than or 
   equal to y.  If i = y initially, the loop never runs, so we "exit" the 
   loop immediately.  If i < y, then within the loop, i is always 
   incremented by 1, so i will eventually increase until it is the 
   same value as y. Thus, the loop must exit in this condition as well.


6.
a) 1 (step 2) + 1 (step 3) + (n-1)(step 4)*(1 (step 4a) + 1 (step 4b)) = 
   2 + 2(n-1) = 2n
b) O(n), since the 2n is a linear function.
c) Base Case: n = 1. 2^0 + ... + 2^(1-1) = 2^1 - 1
                     2^0 + ... + 2^0 = 2 - 1
                     2^0 = 1
                     1 = 1
   Inductive Step:
   Assume 2^0 + ... + 2^(n-1) = 2^n - 1 for some n.
   Consider the formula for n+1 (substitute n+1 for each n):
   2^0 + ... + 2^(n+1-1)     = 2^(n+1) - 1
   2^0 + ... + 2^n           = 2^(n+1) - 1
   2^0 + ... + 2^(n-1) + 2^n = 2^(n+1) - 1    (show one more term in sum)
   (2^n - 1)           + 2^n = 2^(n+1) - 1    (by our assumption above)
   2(2^n) - 1                = 2^(n+1) - 1
   2^(n+1) - 1               = 2^(n+1) - 1


7.
a) A = true, B = true, C = true, D = false
b) 2^N since each variable has 2 possible solutions.  There are N 
   variables, so the total number of possible solutions to test
   is 2*2*2*...*2 (N times) = 2^N.
c) It says that these problems are intractable except for when N is very 
   small.  (We can solve them but the amount of time is far beyond 
   our lifetime.)


8.
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 because if E 
   says the F will halt, then F will go into an infinite loop and vice versa.  

c) This says that E cannot exist in general since there is at least
   one program (F) that it can't decide.