Math 55 - Fall 2000 - Midterm 1 - Answers

Complete answers to all versions of each question are shown.

Q1) (10 pts) Determine whether or not the following expression is a tautology:
xor means exclusive or.
If it is, prove it using rules for simplifying logical expressions,
without using a truth table. If not, give a counterexample.

    1) (p or not q) -> ( (p xor not q) or (p and not q) )

            [<=> not(p or not q) or (p xor not q) or (p and not q)
                    definition of ->
             <=> (not p and q ) or (p xor not q) or (p and not q)
                    DeMorgan
             <=> (not p and q ) or (p and q) or (not p and not q) or 
                  (p and not q)
                    definition of xor
             <=> [ q and (not p or p) ] or [ (not p or p ) and not q]
                    distributive law (twice)
             <=> q or not q
                    not p or p = T
             <=> T
                    q or not q = T ]

    2) (not p or q) -> ( (not p xor q) or (not p and q) )

            [<=> not(not p or q) or (not p xor q) or (not p and q)
                    definition of ->
             <=> (p and not q ) or (not p xor q) or (not p and q)
                    DeMorgan
             <=> (p and not q ) or (not p and not q) or (p and q) or 
               (not p and q)
                    definition of xor, not not cancels
             <=> [ not q and (p or not p) ] or [ (p or not p ) and q]
                    distributive law (twice)
             <=> not q or q
                    p or not p = T
             <=> T
                    not q or q = T ]

    3) (not p or not q) -> ( (not p xor not q) or (not p and not q) )
            [<=> not(not p or not q) or (not p xor not q) or (not p and not q)
                    definition of ->
             <=> (p and q) or (not p xor not q) or (not p and not q)
                    DeMorgan
             <=> (p and q ) or (p and not q) or (not p and q) or 
                   (not p and not q)
                    definition of xor
             <=> [ p and (q or not q) ] or [ not p and (q or not q)]
                    distributive law (twice)
             <=> q or not q
                    not p or p = T
             <=> T
                    q or not q = T ]


Q2) (10 pts) Classify f as one-to-one, onto, both, or neither. R+ is
the set of nonnegative real numbers. Justify your answers.

     1a) h:R->R+, h(x) = x^4, g:R+->R, g(x) = x^(1/8), f(x) = g o h

          [neither: note that f:R->R f(x) = (x^4)^(1/8) = sqrt(abs(x)), 
              f(4) = f(-4) = 2, so f is not one-to-one
              since f(x) >= 0 for all x, and the codomain includes
                  negative numbers, f is not onto]

     1b) h:R->R+, h(x) = x^4, g:R+->R, g(x) = x^(1/8), f(x) = h o g

          [both: note that f:R+->R+, f(x) = (x^(1/8))^4 = sqrt(x)
             since the equation y=f(x) = sqrt(x) has a unique solution
             x = y^2 for every y in the codomain R+, f(x) is a bijection]

     1c) h:R+->R, h(x) = x^(1/8), g:R->R, g(x)=x^4,    f(x) = g o h

          [one-to-one: note that h:R+->R, f(x) = (x^(1/8))^4 = sqrt(x)
              since the equation y=f(x) = sqrt(x) has a unique solution
              x = y^2 for all nonnegative y, and no solution for
              negative y, f(x) is one-to-one but not onto]

     2a) f:D->D, D={0,...,4}, f(x) = x^3+7 mod 5

          [both: we compute f(0)=2, f(1)=3, f(2)=0, f(3)=4, f(4)=1.
              Since each d in D appears as a value of f(x) exactly once,
              i.e. the equation y=f(x) has a unique solution x for every
              y in D, f(x) is a bijection.]

     2b) f:D->D, D={0,...,4}, f(x) = 3*x^2+6 mod 5

          [neither: we compute f(0)=1, f(1)=4, f(2)=3, f(3)=3, f(4) = 4.
             Since the equation f(x)=4 has 2 solutions x=1 and x=4, 
                      f is not one-to-one
             Since the equation f(x)=2 has no solutions, f is not onto]

     2c) f:D->D, D={0,...,5}, f(x) = x^3+1 mod 5

          [neither: we compute f(0)=2, f(1)=3, f(2)=0, f(3)=4, f(4)=1, f(5)=2.
             Since the equation f(x)=2 has 2 solutions x=0 and x=5, 
                       f is not one-to-one
             Since the equation f(x)=5 has no solutions, f is not onto]

     3a) f:BxB -> BxB, B= bit strings of length 8, 
         Let f(a,b)=(c,d), where a,b,c,d are all in B.
         Denote the i-th bit of  b by b(i).
         Then c(i) = a(i) or b(i), d(i) = a(i) and b(i)

            [neither: Let 0 denote the string of 8 zero bits, and
               1 denote the string of 8 ones bits.
              Since f(0,1)=f(1,0)=(1,0), f is not one-to-one.
              Since f(a,b)=(0,1) has no solution, f is not onto
                (this has no solution because a and b = 1 implies
                  a=1 and b=1, but a or b = 0 implies a=0 and b=0,
                  a contradiction)]
 
     3b) Same set up but c(i) = a(i), d(i) = a(i) xor b(i)

            [both: we show that f(a,b)=(c,d) has a unique solution (a,b)
                   for every (c,d): choose a(i)=c(i), and b(i)=d(i) xor c(i).
                   To show this is a solution we can use a truth table:
                      c(i) d(i) a(i)  b(i)  a(i) xor b(i)
                        0    0    0     0         0
                        0    1    0     1         1
                        1    0    1     1         0
                        1    1    1     0         1
                   and note that the a(i) xor b(i) column matches d(i)
                   to show this solution is unique, we can try the
                   only other possibility, which is b(i) having the
                   complement of its value in the above table:
                      c(i) d(i) a(i)  not b(i)  a(i) xor not b(i)
                        0    0    0       1         1
                        0    1    0       0         0
                        1    0    1       0         1
                        1    1    1       1         0
                   since the a(i) xor not b(i) column never agree with d(i),
                   the solution is unique]
                     

     3c) Same set up but c(i) = a(i) -> b(i), d(i) = b(i)

            [neither: Let 0 denote the string of 8 zero bits, and
               1 denote the string of 8 ones bits.
              Since f(0,1)=f(1,1)=(1,1), f is not one-to-one.
              Since f(a,b)=(1,0) has no solution, f is not onto
                (this has no solution because b=d=0, and a -> 0 = 1
                 implies a=0, a contradiction]
 

Q3) (10 pts) Find a simple expression for 

    1) prod_{k=1 to n} x^k       

           [prod_{k=1 to n} x^k = x^{sum_{k=1 to n} k} 
                                = x^(n(n+1)/2)]

    2) prod_{k=1 to n} x^(2^k)

           [prod_{k=1 to n} x^(2^k) = x^{sum_{k=1 to n} 2^k}
                                    = x^(2^(n+1)-2)]

    3) sum_{k=1 to n} log (4^k)

           [sum_{k=1 to n} log (4^k) = sum_{k=1 to n} k * log 4
                                     = n*(n+1)*(log 4)/2]

Show your work to get full credit.

Q4) (10 pts) In the expressions below log x means log_2 x. Show your work
    to get full credit.

    1a) Find the smallest integer n such that
            f(x) = 18x^3*log x + 2x^2*sqrt(x)*(log x)^3 - 7*x*sqrt(x^5) -8 
              is O(x^(n/2))  Note the exponent is n/2.
            
        [O(18x^3*log x + 2x^2*sqrt(x)*(log x)^3 - 7*x*sqrt(x^5) -8)  is
         O(x^3*log x + x^(5/2)*(log x)^3 + x^(7/2) + 1) is
         O(x^(7/2)) since the largest exponent is 7/2, and the other
           terms have smaller exponents and log factors, and so are
           strictly smaller than x^(7/2). Thus n=7]

    1b) Find the smallest integer n such that
            f(x) = 7x^5*(log x)^2 + 8x^4*sqrt(x^1.5)*(log x)^2 - 
                   7*x*sqrt(x^7*log x) -8 
             is O(x^(n/2))  Note the exponent is n/2.

          [O(7x^5*(log x)^2 + 8x^4*sqrt(x^1.5)*(log x)^2 - 7*x*sqrt(x^7*log x) -8) is
           O(x^5*(log x)^2 + x^(4.75)*(log x)^2 + x^(4.5)*sqrt(log(x)) + 1) is
           O(x^5*(log x)^2) since the largest exponent is 5, and the other
             terms have smaller exponents and log factors, and so are
             strictly smaller than x^5. Now x^5*(log x)^2 is not O(x^5)
             but it is O(x^(5.5)), since x^.5 is larger than any power of
             log x. Thus n=11.]

    1c) Find the smallest integer n such that
            f(x) = -3x^3*(log x)^3 + 7x^2*sqrt(x)*(log x)^3 - 7*sqrt(x^7)*log x -8 
              is O(x^(n/2))  Note the exponent is n/2.

           [O(-3x^3*(log x)^3 + 7x^2*sqrt(x)*(log x)^3 -7*sqrt(x^7)*log x -8) is
            O(x^3*(log x)^3 + x^(2.5)*(log x)^3 + x^(3.5)*log x + 1) is
            O(x^(3.5)*log x) since the largest exponent is 3.5, and the other
             terms have smaller exponents and log factors, and so are
             strictly smaller than x^(3.5). Now x^(3.5)*log x is not O(x^(3.5))
             but it is O(x^4), since x^.5 is larger than any power of
             log x. Thus n=8.]

            [n=8]

    2a) Find a simple, small function g(x) such that
            f(x) = x^4*2^(3*x) - x^5*7^x is O(g(x))

        [We take the ratio (x^4*2^(3*x))/(x^5*7^x) = (x^4*8^x)/(x^5*7^x) 
                                                   = (8/7)^x / x
               which goes to infinity as x does, since an exponential
               b^x for any b>1 grows faster than any power of x.
               Therefore g(x) = x^4*8^x is larger.]

    2b) Find a simple, small function g(x) such that
            f(x) = x^3*8^x - x^2*3^(2*x) is O(g(x))

        [We take the ratio (x^3*8^x)/(x^2*3^(2*x)) = (x^4*8^x)/(x^2*9^x) 
                                                   = x^2 / (9/8)^4
               which goes to 0 as x does, since an exponential
               b^x for any b>1 grows faster than any power of x.
               Therefore g(x) = x^2*9^x is larger.]

    2c) Find a simple, small function g(x) such that
            f(x) =  x^3*2^(4*x) + x^2*4^(2*x) is O(g(x))

        [We simplify f(x) = x^3*16^x + x^2*16^x.
              since 16^x is a common factor, all that matters is
              the power of x, so g(x) = x^3*16^x is larger.]

    3a) Find a simple, small function g(x) such that
            f(x) = (4*x^3 + 8*x^5 - 27*x^2 - x + 27)^3 *
                   (15*x^3 - (log x)*x^3 + log log x^7)^2 *
                   (x^(-2)/log x - x^(-3)*log log x)^4
               is O(g(x))

        [O(f(x)) is O( (x^5)^3 * ((log x)*x^3)^2 * (x^(-2)/log x)^4 
                 is O(  x^15 * (log x)^2 * x^6 * x^(-8)/(log x)^4
                 is O(  x^13 / (log x)^2 ) ]

    3b) Find a simple, small function g(x) such that
            f(x) = (5*x^3 - 13*x^2 + 2x - 6 x^4 + 2)^4 *
                   ( (log x)^2*x + (log log x^7)^4 - 22*x^2)^3 *
                   (x^(-1)/log log x - x^(-2)* log x)^2
               is O(g(x))

        [O(f(x)) is O( (x^4)^4 * (x^2)^3 * (x^(-1)/log log x)^2
                 is O( x^16 * x^6 * x^(-2)/(log log x)^2 )
                 is O( x^20 / (log log x)^2 ) ]

    3c) Find a simple, small function g(x) such that
            f(x) = (- 8*x^4 + 13*x^3 + 2x + -5*x^6 + 2)^2 *
                   (- (log x)^2*x^3 + x^2*(log log x^7)^4 -19*x^4 )^4 *
                   (x^(-4)/log x - x^(-5)* (log x)^2)^3
               is O(g(x))

        [O(f(x)) is O( (x^6)^2 * (x^4)^4 * (x^(-4)/log x)^3 )
                 is O( x^12 * x^16 * x^(-12)/(log x)^3 )
                 is O( x^16 / (log x)^3 ) ]

Q5) (10 pts) Use the Euclidean Algorithm to compute d=gcd(a,b) and find integers
    s and t such that a*s+b*t=d for

    a)   a=121, b=15 

          [if we begin the Euclidean algorithm with x=a,y=b,
           here are the values of x,y,sx,tx,sy and ty, where
           x = a*sx+b*tx and y = a*ty+b*ty, at the end of
           each pass through the inner loop of the algorithm.
           at the end, d=x, s=sx and t=tx:
            x:  121=a  15     1=d
            y:   15=b   1     0
            sx:   1     0     1=s
            tx:   0     1    -8=t
            sy:   0     1   -15
            ty:   1    -8   121    ]

    b)   a=118, b=13

          [if we begin the Euclidean algorithm with x=a,y=b,
           here are the values of x,y,sx,tx,sy and ty, where
           x = a*sx+b*tx and y = a*ty+b*ty, at the end of
           each pass through the inner loop of the algorithm.
           at the end, d=x, s=sx and t=tx:
            x:  118=a  13     1=d
            y:   13=b   1     0
            sx:   1     0     1=s
            tx:   0     1    -9=t
            sy:   0     1   -13
            ty:   1    -9   118    ]

    c)   a=99, b=14

          [if we begin the Euclidean algorithm with x=a,y=b,
           here are the values of x,y,sx,tx,sy and ty, where
           x = a*sx+b*tx and y = a*ty+b*ty, at the end of
           each pass through the inner loop of the algorithm.
           at the end, d=x, s=sx and t=tx:
            x:   99=a  14     1=d
            y:   14=b   1     0
            sx:   1     0     1=s
            tx:   0     1    -7=t
            sy:   0     1   -14
            ty:   1    -7    99     ]