Hw08: cardinality; big-Oh; mod

Before you tackle the homework, remind yourself of our general hw policies. Tweaks/clarifications shown in purple.

1. (3pts) p.236, #32a,c,d. (which sets countable) [4ed: p.79, #32a,c,d.]
2. (4pts) p.236, #36. (union of countable sets.) [4ed: p.80, #36.]
3. (2pts) In the definition of big-Oh, give particular values of c,n₀ (Rosen: "C,k") which witness:
   1. 17log(n)+19 is O(log n);
   2. n²log(n) is O(n³);
   3. n³+2 is O(n¹⁷).
4. (2pts) p.142, #8. (polynomial bounds) [4ed: p.90 #8.]
5. (3pts) p.142, #12. (x² vs x log(x)) [4ed: p.90 #12.]
6. (2pts) p.143, #20a. (simplify big-Oh. Recall your answer to the third problem, above.) [4ed: p.91 #20a.]

7. (4pts) You have accepted a job at the startup KaZoo, whose rad new product lets you both text-message and instant-message buddies with whom you file-share, all the while searching for extra-terrestial life

   Their current version works, but unfortunately is too slow: because of all the network traffic it generates, the program becomes bogged down after only 100 buddies. (It is the amount of network traffic that dominates the running time -- the local processing time is negligible.) "Unacceptable!" your boss cries. "We need to support at least 5000 buddies!"

   Indeed, you work day and night, and a week later report to your overjoyed boss, that you have cut the amount of network traffic generated by a factor of 64. (Or equivalently -- network/compression technology improves 64x.) Your boss is overjoyed, and marketing promptly announces "Now, supports 64 times as many buddies!"

   How many buddies can a user now have, before the system bogs down, if the n buddies induces f(n) traffic, for the following functions f.

   1. f(n) = n
   2. f(n) = n^2
   3. f(n) = n^3
   4. f(n) = 2^n
   What do you say to your (intelligent) boss, to explain in lay terms why a 64-fold speed improvement may not mean a 64-fold number-of-users improvement?

   Hint: rather than a function runtime-KaZoo(), consider the function nettraffic-KaZoo() [you may give it a shorter name]. The particular number nettraffic-KaZoo(100) is a constant benchmark you'll compare your new version against.

8. (2pts) p. 152, #12a,b. (Some best-case performances.) [4ed: p.112, #12a,b]
9. (2pts) p. 166, #4. (| transitive) [4ed: p.126, #4.]
10. (1pt) p. 167, #16. (relative primes of 12.) [4ed: p.126, #14.]
11. (1pt) p. 167, #38. (congruences to 4, mod 12.) [4ed: p.126, #30.]
12. (3pts) p.168, #42. (a ≡ b, &c equiv d; => a-c ≡ b-d.) [4ed: p.126, #34.]
    [To think about: What if m=1?]

13. (3pts) Write a function to encode messages by the shift-cipher, as described in Rosen.

    ;; shift: string/lowercase, number --> string/lowercase
    ;; (Where "string/lowercase" means "{a,...,z}*".)
    ;; Encode lower-case strings by the shift cipher, as sketched in Rosen.
    ;; Output not specified, for other inputs, e.g. upper case, spaces, punctuation.
    ;;
    (define (shift msg offset) ...)
    
    ;Examples:
    (shift "pizza"  1) = "qjaab"
    (shift "bialy" -2) = "zgyjw"
    (shift "pez"   52) = "pez"
    (shift (shift "indecipherable" 17) -17) = "indecipherable"
    

    You may use any language, though your solution should be well-written. (The solution set's version is 8 lines, plus comments and test cases).

    You may use the provided teachpack, (w/ has some scheme-specific notes at the end). Note that in ASCII, unlike Rosen, the numeric value corresponding to the character #\a isn't 0, but some positive integer constant. (As always in your programs, don't use magic numbers.)

14. (1pt) For the preceding program, write a first-order logic formula expressing the general concept hinted at in the final test-case.
15. (2pts) p.168, #56. (ISBN check-sum) [4ed: p.127, #48.]
16. (2pts) What is 123¹⁰⁰¹ mod 101?
    Presumably you'll double-check your answer with mathematica or drscheme ("expt").
    (This is p. 180, #20, except you may find it more intuitive to proceed top-down, rather than the book's bottom-up approach: 123¹⁰⁰¹ ≡ 123*(123²)⁵⁰⁰ ≡ ... (mod 101). Don't show your work, but do work this out yourself, as per the class's hw honor policy.)