Discrete Mathematics (Dow) -- Test 1 Version C
      
      In all questions, clear reasoning must be provided.
      
       1. Perform the indicated computations (in (a)-(c) your answer should
          be between 0 and m-1).
            1. 12^2 * 13  mod 11
     12 is just 1 and 13 is just 2  mod 11, so we have 1^2 * 2 = 2 
            2. -40 mod 13     (use  ==   for 'congruent modulo')
     -40 == -40 + 13 = -27 == -27 + 13 = -14 == -1 == 12
            3.  3 * (5600000002) mod 56
     5600000002 = 5600000000 + 2 == 2 mod 56, so answer is 6
            4. 17 is inverse of 2 mod m . What are the possible values of m.
      Well, 17 * 2 == 1 (mod m), i.e.  34 == 1 (mod m), i.e. 33 == 0 (mod m)
    The only values for m then are   1, 3, 11, 33
          
       2. In this question we are only interested in values of x between 0
          and the modulus m. You must justify your answers.
            1. 3x==5(mod 7) . Find all solutions.
    Inspection is fine:  x=4 gives 3x=12 which is congruent mod 7 to 5
            2. 4x==6 (mod 402) . Is there 0, 1, or more than one solution?
    I wanted,  gcd(4,402) = 2 (I thought it easy: 402/2 = 201 so 4
   doesn't divide).  Then  2  does divide 6 so there is a solution and
   since gcd > 1, there is more than one.
   
            3. 6x==4(mod 3333) . Is there 0, 1, or more than one solution?
      I thought it obvious that gcd(6,3333)=3 and  3 doesn't divide 4
   so there's no solutions.
          
       3. Throughout this question replace d by the value that you obtain in
          Part (a).
          (a) Express d=gcd(65,91) as a linear combination of 65 and 91.
    First go through Euclidean algorithm:
      91=1*(65)+26  and  65 = 2*(26) + 13   and 26 = 2(13)   so 
   d=13 is the gcd.  Now   13 = 65 - 2(26)   and  26 = 91 -1*(65)
   plug the second equation into the first
        13 = 65 - 2(26) = 65 - 2(91-65) = simplify = 65 -2(91) + 2(65)
    hence   13 = 3(65) - 2(91)
         (b) Explain how to use your answer in 
                    Part (a) to solve 65 y == d (mod 91)
    Well just use the coefficient 3=y  since  3(65)= 13 + 2(91).
          (c) Is there an x which is a solution to the system
                          x==0(mod 65)  and   x==d(mod 91)
   Yes, x==0 (mod 65)  means that  x = 65 t for some integer t.
   Then  x==d (mod 91) means that t is such that 
            x=65 t == d (mod 91)  well, we know the solution for t, it is 3.
    So finally  x = 65*3.       
          
          
       4. Consider the function f(n) = n^2 + (-1)^n * (n^2-10).
            1. Compute some values (n even), (n odd).
    I wanted you to pick up the pattern that 
       f(n) = 2*n^2 - 10  for n even, and  f(n) = 10  for n odd
            2. Find the smallest integer m  such that is O(n^m).
    As hinted,  |f(n)| <=  2*n^2+10 for all n and this is clearly O(n^2),
    hence  f(n)  is  O(n^2).
            3. Find the largest j such that n^j is O(f(n)) .
   Well the value of  j  is just 0, because even with  j=1,  
       n  is not O(f(n)) because for all those odd integers n,  f(n)
   is just 10   which means there is no constant C  such that 
       n < C*10  for all odd n.
      
          
       5. The following algorithm uses m as a moduli, and a, c as seeds to
          generate a sequence of pseudorandom numbers. For each i, it uses
          the binary search algorithm to test which of the are in the
          (increasing) list . Discuss the worst case big-O complexity. Of
          course we know that the binary search algorithm is O so take that
          for granted in your computations.
          
   
    Procedure 
      Random Test (m,a,c : integers;a_1,...,a_n  :increasing integers)
        x:=1
        random := 0
        for k:= 1 to n
         begin
           x:= a*x + c (mod m) {this is what we called x_k}
           i:=  Binary Search(x,a_1,...,a_n)
           if x=a_i   then random :=  random +1
         end
   
   The variable k runs from 1 to n. For each  value of k, there are
   log(n)+3 many steps between  begin  and  end because we assume the
   binary search algorithm takes log(n) steps.
   
   Adding this up we get  log(n) + log(n) + ... + log(n)  (n times)
   hence  O(n log(n) ).
   
   
       Alan Dow
       Wed Oct 16 10:23:19 EDT 1996





Alan Dow
Wed Oct 16 12:45:38 EDT 1996