$Id: review1.txt,v 1.1 2005/09/13 16:05:12 locasto Exp $
Fall 2005 COMS1003                                        
----------------------------------------------------------------------

0. Translate the following numbers from binary (base 2) to decimal
    (base 10).

    a) 10011001
    b) 00000001  
    c) 10000000  
    d) 11011010  
    e) 00000000010110110000000111110111

    answers:
    a) 153
    b) 1
    c) 128
    d) 218
    e) 5964279

1. Translate the following numbers from decimal to binary.

    a) 1,024
    b) 554
    c) 4,342,119
    d) 4490
    e) 2048
    f) 4096
    g) 11223

    answers:
    a) 10000000000
    b) 1000101010
    c) 10000100100000101100111
    d) 1000110001010
    e) 100000000000 
    f) 1000000000000
    g) 10101111010111

2. Add these binary numbers.

   a) 10010000 + 00110111
   b) 0000 + 1111
   c) 01 + 01
   d) 1000 + 0010

   answers:
   a) 11000111
   b) 1111
   c) 10
   d) 1010

3. Give the 1 and 2's complement of the following binary numbers.

  a) 1001
  b) 0000
  c) 00100010
  d) 11110000
  e) 01
  f) 11100010
  g) 00110000000011111111111000010011

  answers:
  a) 0110 and 0111
  b) 1111 and 0000
  c) 11011101 and 11011110
  d) 00001111 and 00010000
  e) 10 and 11
  f) 00011101 and 11110
  g) 11001111111100000000000111101100 and 
     11001111111100000000000111101101

4. Show the truth table for the following expressions:

   a) p AND q
   b) p OR q
   c) NOT p
   d) p AND q OR q
   e) (q IMPLIES p) AND (q OR p)
   f) p AND q AND r
   g) (p OR q) IMPLIES r

   answers:
   a)     p| q| p AND q|    b) p| q| p OR q|
          --------------       -------------
          T  T    T            T  T    T
          T  F    F            T  F    T
          F  T    F            F  T    T
          F  F    F            F  F    F

   c)  p  !p           d) p  q  p AND q OR q
       -----              ------------------
       T   F              T  T       T
       F   T              T  F       F
                          F  T       T
                          F  F       F

   e) p  q   q->p AND q OR p
      ----------------------
      T  T       T      
      T  F       T     
      F  T       F     
      F  F       F      

   f)  p  q  r    p and q and r  |g) p or q -> r 
       ----------------------------------------
       T  T  T        T                 T
       T  T  F        F                 F 
       T  F  T        F                 T
       T  F  F        F                 F
       F  T  T        F                 T
       F  T  F        F                 F
       F  F  T        F                 T
       F  F  F        F                 T


5. Draw the circuits (using AND, NOT, and OR gates) for the following
  expressions:

   a) a OR b AND c OR d
   b) a AND b OR (NOT c OR NOT d)

   answers:
   a)

      a ---\---\
            >   >------------+----\
      b ---/---/             |    |
                             |     )------
      c ---\---\             |    |
            >   >------------+----/
      d ---/---/

   b)

      a ---+--|
           |   )------------\------\
      b ---+--|              \      \
                              >      >----
      c ---+--|              /      /
           |   )------------/------/
      d ---+--|

    
6. If C is a set with n elements, how many elements 
    are in the power set of C?

    2^n

7. Write a formal description of these sets:

   a) The set contains 23, 45, 10, and 13.
   b) The set contains all even integers less than 10.
   c) The set contains nothing.
   d) The set contains all the natural numbers.

   answers:
   a) {23,45,10,13}
   b) {0,2,4,6,8}
   c) {null}
   d) {1,2,3,4,...}

8. Draw the following graph.
   G = (V,E)
   V = {NY,NJ,CA,VA,FL}
   E = {{NY,CA},{NJ,NY},{CA,VA},{NY,FL},{NJ,FL},{NJ,CA},{CA,FL}}


          +---+ 
     +----|NY |----+
     |    +---+    |
     |      |      |
   +---+    |    +---+
   |FL |----+----|NJ |
   +---+    |    +---+ 
     |      |      |
     |    +---+    |
     +----|CA |----+
          +---+
            |
          +---+ 
          |VA |
          +---+


9. For the above graph, answer the following questions:

   a) Are there any cycles in the graph?
   b) Rank the vertices in order of degree, greatest to least.
   c) Name a path from FL to VA.

   answers:
   a) yes, for example: FL,NJ,CA,FL
   b) CA(4), FL(3), NJ(3), NY(3), VA(1)
   c) FL,CA,VA