15110 EXAM 2A - Key


1(a)

                                    f(4)=f(3)+2*f(2)=11
                          +-----------------+---------------------+
                  f(3)=f(2)+2*f(1)=5                     f(2)=f(1)+2*f(0)=3
        +----------------+------------------+             +------+------+
 f(2)=f(1)+2*f(0)=3                      f(1)=1         f(1)=1        f(0)=1
  +-----+------+
 f(1)=1       f(0)=1


 f(4) = 11


1(b)
  - binary search
  - 30

1(c)

def power3(n)
  if _n == 0_ then
     return _1_
  else
     return _3*power3(n-1)_
  end
end

1(d)
   3 co-centric circles, 
      - one inscribed in the outer-square of the grid (radius of 5 grid marks)
      - one with a radius of 3 grid marks
      - one with a radius of 1 grid mark


2(a) 255
2(b) -1
2(c) D9
2(d) 1
2(e) B
2(f) 0x40 = 01000000 = 2*6 = 64
2(g) lossy
2(h) STARE
2(i) 4


3(a)
          0    1    2    3    4    5    6    7    8    9   10
        ---  ---  ---  ---  ---  ---  ---  ---  ---  ---  ---
              34                            18             98
                                            29

  table = [[],[34],[],[],[],[],[],[18,29],[],[],[98]]

  O(1)

3(b)
  - array
  - linked list
  - array

3(c)

                                        1               
               2         6         3    3    2          
          5    5    7    7   42   42   42   42   21     
     9    9    9    9    9    9    9    9    9    9   30

3(d) [graph figure]


4(a)
            73
          /    \
        31      92
         \      /
         56    80
        /  \
       42   66


4(b)
  - 10
  - 1000

4(c)

       71
      /  \
    39    43
   / \   /  \
 28  17  12  20
 /
4


4(d)
  - 9
  - 10

4(e)
  Start by considering the root of the tree.  As long as the node being
  considered has a right child, go to the right child, and repeat 
  using that right child as the node being considered.  When you reach
  a node without a right child, that is the maximum node of the binary
  tree.


5(a)

          A B C    A^C  B^!A    S
          - - -    ---  ----    -
          0 0 0      0     0    0 
          0 0 1      0     0    0 
          0 1 0      0     1    1 
          0 1 1      0     1    1 
          1 0 0      0     0    0 
          1 0 1      1     0    1 
          1 1 0      0     0    0 
          1 1 1      1     0    1 

5(b) [Circuit diagram figure.]

5(c) 2**7 = 128

5(d) 
      x <= 0 and y != 100