Chapter 2 Review Answers


  • 12 last occurrence of smallest and big-O
    What's our plan? One might be to use a variable x to keep track of the min so far in the sequence. Let i run from 1 to n and compare x to the i-th of the sequence. If i=1 or if a_i < x then start a subloop which will search for the last occurrence of x. This is clearly, worst case, i goes completely from 1 to n and for each i, the subloop goes from i+1 to n, totalling SUM( n-i : i=1...n) = n(n+1)/2 steps, i.e. big-O(n^2).

    What if instead we simply first find the min (takes n steps) and then go back and search for last occurence, this will just be 2n steps (worst case).

    Procedure LastMin([a_1,..., a_n] : List)
       x :=a_1
       i :=1
       while i < n
        begin
         i := i+1
         if a_i < x then x := a_i
        end  { note i is n when this ends}
       while x > a_i
         i := i-1   { I decide to go backwards}
       output i {this should be it}
    

    After writing this algorithm I realized the best would be to just search for the minimum from the last element to the first and, in place of x, just keep a record, say j, for the current location of the minimum (first occurence from the right). One pass through the list yields the answer.


  • 17is f onto and big-O
    We have a function f from some finite set, why not {1,2,...,n}, to another set, why not, {1,2,...,m}.
    We of course have to let a counter j run from 1 to m and check to see if j is equal to f(i) for some i. To check that we have to let i run from 1 to n and check if f(i) = j for each i. Seems like O(n^2) to me. Actually it looks more like m*n steps? Ah but if m> n we don't have to check! (Why?)

    f gets coded as a list of pairs [ [1,f(1)], [2,f(2)], ..., [n, f(n)] ].

    Procedure ONTO?(n,m: integers;  list of pairs)
      A := 1  { as soon as A becomes 0 it is not onto }
      j := 1
      if n< m then A:=0   { don't waste time }
       while ( A=1 and j< m )    {test each j}
        begin
          i := 1
          while i  < n
            begin
            if  (i-th pair is [i,j] ) then i = n+2 { Silly trick }
            i := i+1
            end
        if i = n then  A:=0  {j not in image}
        end
      Output A
    

    21 ternary search (determine divide and conquer)
    (Answer is book is infinite loop, see why you need program verifications?) Plan for [a_1 < a_2 < ... < a_n] is to see if value x lies among a_1 upto (roughly) a_(n/3), or among a_(n/3 +1) up to a_(2n/3), or in the final third. Whichever is the case, essentially recursively call the algorithm to search the subinterval. l will denote index of left end of interval to search and r will be the index of right end.

    Procedure Ternary( [a_1, ..., a_n]: sorted list; x: number)
      l:=1, r:=n
      while l < r
        begin
         k := floor(r+l /3)  { note k is equal l + floor(r-l /3) }
         if x > a_k
           then   { x is not in first third }
            begin
            k' := floor(2(r+l) /3)  { and k' is  l + 2* floor(r-l /3)
            if x > a_k' then l:= k' +1  { since x not in first 2 thirds }
              else   { x not in first or last third }
               begin
               l := k+1
               r := k'
               end
           else r := k   { first third is only possibility }
        end  { when this is done l = r and x = a_r or not in list }
      if x = a_r then  A := 1
        else  A := 0
      output A
    
    If f(n) is number of steps for searching length n, then if C is the actually number of lines of code, then f(n) is something like (in fact a little less than) f(n/3) + C. Although this is not technically a recursive algorithm it is clear that f(n) is larger than f(n/3)+C (and not significantly smaller than this). Therefore f is O(log(n)). We could put the log to be base 3 but this is the same big-O behaviour.

    25 first x_j s.t. exists i< j which equals it.

    procedure DownList( [x_1, ..., x_n ] : list )
      A := 0 { memory for hit }
      j := n { start at top and work down }
      while j > 0
        begin
        i := j - 1
        while (x_i <> x_j  and i>0)
            i := i-1
        if i> 0 then
                     begin
                     A := j
                     j := 0  { to stop }
                     end
        end
      output A  { 0 for no such j }
    


    Euclid's complexity Write an algorithm for the division algorithm and determine number of steps (in terms of inputs). Then find a divide and conquer algorithm to compute gcd(a b). Compute it's complexity using 5.3 where you could set f(n) to be the maximum number of steps needed to compute gcd(a b) for any a, b at most n. You should be able to get f(n)=f(n/2) + g(n) (with g(n) not too big) by going two steps at a time.

    Procedure Rem(a,b) { input a > b, output r< b s.t. a = qb + r }
       r := a - b * floor(a/b)
       output r { but what if floor is not built in? }
      r := a  { if no floor function }
      while r> 0  { we will go one too many}
        r := r - b
      r := r + b  { put it back}
      output r  { this took ceiling(a/b)  steps of course }
    
    Procedure GCD(a,b)  { will use gcd(a,b) = gcd(r_0,r_1) }
     r_0 := Rem(a,b)
     if r_0 = 0
       then output b
     else
       begin
       r_1 := Rem(b,r_0)
       if r_1 = 0 then output r_0
         else GCD(r_0,r_1)
       end
    
    Let f(n) denote the maximum number of steps it would take to run GCD(a,b) for any pair b< a such that b < n+1. We claim that this satisfies a divide and conquer recurrence relation of the form f(n) = f(n/2) + C for some constant C about 4 (unless floor is not built in for Rem). To see this we need to see that if b< a and b< n+1, then r_1< r_0 and r_1 < n/2 +1. It is clear by looking at the code for Rem(a,b) that r < b, hence r_1 = Rem(b,r_0) is less than r_0. Similarly, r_0 < b. But now we have that b = q * r_0 + r_1 for some q (again by the coding of Rem), and r_1< r_0 < b, hence q> 0. This means that r_1 < b/2 since otherwise 1 * r_0 + r_1 would be bigger than b.


  • 2.3 P124: 16 6, 28, 2^(p-1) (2^p-1) is perfect if 2^p-1 is prime
    Obviously you can just check that, e.g. 28 = 1 + 2 + 4 + 7 + 14 = sum of its divisors other than itself. Notice that 28 = 2^(3-1) * ( 2^3 -1) = 4 * 7. 1,2, and 4 are the divisors of 4, and 1, 7 are the divisors of 7, hence the divisors of 28 consist of a divisor of 4 times a divisor of 7. So the sum of these is just (1+2+4)*1 + (1+2+4)*7 = (2^3 - 1) * 1 + (2^3 - 1) * 7 = (2^3 - 1) * (1+ (2^3 -1)) = (2^3 -1) * 2^3.


  • 25 P149: 4 937 is 13^-1 (2436)
    Well, just multiply and check (mod 2436) I guess. (937)(13) = 9370+ 2811 = 12181. Five times 2436 looks like it should be pretty close (of course we expect something like m * 2436 + 1 to equal 12181). Indeed, 5 * 2436 = 12180.

    8 144^-1 (233)
    Of course we could work out gcd(144,233), since we then know we can get 144x + 233 y = 1 for some x,y. Then x (or its equivalent value mod 233 is 144 inverse).
    Here's another way. 144 is a product of a bunch of 2's and 3's (since it is 12*12). 2^(-1) is obvious because 233 is odd (whenever I say inverse in this question, I'll mean mod 233). Also 233 mod 3 is 2 hence some mulitple of 3 is just one more than 233, hence also 3^(-1) is easy to find mod 233. Indeed, clearly 117 is 2^(-1) and 234/3 = 78 is 3^(-1). Therefore 6^(-1) = 2^(-1) * 3^(-1) = 117 * 78 (mod 233) = 9126 (mod 233) = 39*233 + 39 (mod 233) = 39. This means, that 12^(-1) = 2^(-1) * 6^(-1) = 117 * 39 = 4563 (mod 233) = 136. Finally 144^(-1) = 136 * 136 (mod 233) 79 * 233 + 89 (mod 233) = 89.

    Naturally we can just check this 144 * 89 = 12816 and 233 * 55 = 12815, hence 89 is the inverse of 144.

    10 a^-1 (mod m) exists means gcd(a,m)=1
    Naturally this can be viewed as one of the facts we are to know. More generally, we "know" that if there are x,y such that a*x + b*y = d, then gcd(a,b) divides d. The connection then is that if a has an inverse, call it x, then ax = 1 (mod m) which means there is some y, such that ax = 1 + my, i.e. ax - my =1. So by the remark above, gcd(a,m) must divide 1.

    We can do without the remark as follows. ax - my =1 and let d = gcd(a,m). d divides a and m, means that d divides ax - my. But this means that d divides 1 because that is what ax - my equals.


    24 a<28 is rep by (mod 4, mod 7) (0,0), (1,0), (1,1), (2,1), (2,2), (0,3), (2,0), (3,5), (3,6)
    This idea comes from the Chinese remainder theorem. You should know this much of it. 4 and 7 are relatively prime, hence for any pair ( x (mod 4), y (mod 7) ) there is a unique number A between 0 and 27 (4*7 - 1) which satisfies both these, i.e. A mod 4 = x mod 4 and A mod 7 = y mod 4 (usually x is between 0 and 4 and y between 0 and 7 so we don't have to write x mod 4, just x). This implies that for each of the above pairs there is some number A which is coded by the pair (the converse, i.e. each A has a code, is trivial). By the way, you can use the Pigeon hole principle to prove the Chinese remainder theorem is to prove that if A and B are distinct numbers between 0 and 28, then either A mod 4 <> B mod 4, or A mod 7 <> B mod 7 (Can you prove this?). Because then the mapping which sends A to ( A mod 4, B mod 7) is 1-1 and thus, by counting, onto.

    It's easy! Consider A-B. If A mod 4 = B mod 4, then A-B mod 4 =0. Similarly if A mod 7 = B mod 7, then A-B mod 7 = 0. But then, 4 divides A-B and 7 divides A-B. 4 and 7 are relatively prime, hence 4*7 divides A-B. But A and B are both between 0 and 28 hence A-B is less than 28 in absolute value, but if 28 divides it, it must be 0.

    Back to the codes: For brevity let us answer in the form A is coded by (x,y).
    0 is coded by (0,0).
    What about (1,0)? A mod 7 = 0 means A = 7*k for some k. Then 7k = 1 mod 4. This has a solution because gcd(7,4)=1. We will likely be doing this again, so let's compute 7^(-1) mod 4 ( 7 = 3 mod 4, and 3^(-1) = 3 (3*3=9=1 mod 4). Also 4^(-1) mod 7 = 2).
    So k = 7^(-1) * 1 = 3. Answer A=21 is coded by (1,0).
    (1,1): A=4k+1 since A=1(mod 4). So 4k+1 = 1 (mod 7). Thus 4k = 0 (mod 7). k=0 works. Indeed, why didn't you see that A=1 works?
    (2,1): A=4k+2, set 4k+2 = 1 (mod 7), implies 4k = 6 (mod 7). 4^(-1) = 2 remember, hence k = 2*6 = 5 (mod 7). A = 22.
    I'll just do one more: (3,6): A=4k+3 (giving A mod 4 = 3), hence 4k+3 = 6 (mod 7), or 4k = 3(mod 7). Multiply both sides by 2: k = 6 (mod 7). Hence A=27.


  • Review P164: 10 how to find lin comb of a,b to equal d and do so for d=gcd(84,119)

    How to do it is to use the Euclidean algorithm (and keep track of the steps) to find the gcd. Each step of the Euclidean algorithm is of the form r_(n-2) = q_(n-1)*r_(n-1) + r_n. So the final step of the Euclidean algorithm gives us that d = r_(m-1) - q_m * r_m for some integer m. Then we just recursively substitute, on the RHS, [r_(n-2) - q_(n-1)*r_(n-1)] in for r_n and then simplify until we get to the stage where only r_0 and r_1 are left in the expression.

    119 = 84 + 35
     84 = 2*35 + 14
     35 = 2*14 + 7
     14 = 2*7 (hence gcd = 8 and the previous step was the last one).
    
    Recursively reverse:

    7 = 35 - 2*14 = 35 - 2*[84 - 2*35] = 3*35 - 2*84
    7 = 3*[119 - 84] - 2*84 = 3*119 - 5*84.