Extra Credit Hw

Due 04.May.05 (Wed) 17:00.

We will award up to 15pts of extra credit on the following problems. Note: These problems are to be completed by yourself, not with a partner. Turn in your problems as ordered in the list below (and include the problem# from here as well as from 5ed), thanks. Otherwise, the usual hw policies apply

On these problems more than ever, we will be looking (and grading) for a high level of understanding, clarity, and conciseness. In general, extra-credit problems are harder work for fewer points (but cover interesting, more in-depth material). Note that some of the problems require reading sections of the book we didn't cover in lecture (Huffman codes, posets ("partially-ordered sets")).

1. (5   pts) Write a real-life program for encrypting and decrypting RSA messages, given the (public and) private key. (The messages can be arbitrarily long.) As always, programs should include test cases (both trivial and realistic), be clearly commented, etc. Your program should be robust -- code you can actually incorporate in future programs. ¹ You may use any general-purpose programming language, but not pre-written RSA or {\em modular-}arithmetic library functions, beyond remainder, quotient, and divides?. You'll want to use bignums of course -- either built-in or from a library.
2. (10pts) The previous problem is nice, but doesn't include the generation of public/private key pairs, which is critical.
   1. Write a prime-tester. (Look up "Miller's test" in Rosen.)
   2. Using this, write a function to generate RSA public/private keys.
   Again, we're looking for robust, reusable code.
3. (1.5pts) p. 51 #6c-f (fo→english, enroll) [4ed: p.33, #8]
4. (1.5pts) p. 52 #10e-j. (fo→english, fool) [4ed: p.34, #12]
5. (1.5pts) p. 54 #28a-j. (quantifier statements over R) [4ed: does not exist?]
6. (3   pts) p.272 #42 (w^i reversal) [4ed: p.210 #34]
7. (1   pt  ) Which is stronger statement: saying that three sets are mutually disjoint (their intersection is empty), or that they are pairwise disjoint? Give a group of sets which are one but not the other.
8. (1   pt  ) Prove that if f is O(g), then f+g is O(g), for f,g in R→R.
9. (1.5pts) p.658, #24 (Huffman code) [4ed: does not exist?]
10. (2.5pts) p.658 #26. (Huffman code w/ tie-breaking) [4ed: does not exist?]
11. (2   pts) p.507 #28b (Warshall's alg) What is the loop invariant, for Warshall's algorithm?

12. (2   pts) Look up on the web, Warshall's algorithm generalized to compute not just the transitive closure of a graph, but the shortest path between any two pairs of vertices.

    What is the loop invariant, for this variant of Warshall's? Do p.507 #28b with some made-up initial distances, and the modified algorithm.

13. (1.5pts) p.528 #6 (poset dual) [4ed: p.428 #6]
14. (1   pt  ) p.528 #10 (cross-product) [4ed: p.428 #10]
15. (2   pts) p.528 #22 (covering) [4ed: p.428 #20]
16. (1.5pts) p.529 #28 (bounds in a poset) [4ed: p.429 #26]
17. (1   pt  ) p.529 #30 (bounded posets) [4ed: p.429 #28]
18. (1.5pts) p.529 #36a (unique bounds) [4ed: p.429 #34a]
19. (1   pt  ) p.529 #38 (lattices?) [4ed: p.429 #36]
20. (1   pt  ) p.565 #36. (isomorphic graphs?) [4ed: p.465 #36]
21. (1   pt  ) p.565 #42. (isomorphic graphs?) [4ed: p.465 #42]
22. (1   pt  ) p.565 #44. (isomorphic graphs?) [4ed: p.466 #44]
23. (1   pt  ) p.566 #60. (def'n directed isomorphic) [4ed: p.466 #60]
24. (4   pts) p.393 #34b-f (avg-case complexity of quicksort; requires doing #20) [4ed: does-not-exist?]
25. 1. (1pt) Write a program which shuffles an array into a random permutation. (Your favorite language will have a primitive for generating random numbers.)
    2. (1pt) Formulate a logic statement S₁, that your function's returned array contains the same elements as the original input array. You may presume that the input array contained no duplicates.
    3. (3pts) Formulate a logic statement S₂ expressing a property about the randomness of your shuffled array. Does S₂ capture the entire idea of a randomized array? If not, give an example of an algorithm which satisfies S = S₁^S₂, but is not what most people would consider a good shuffling algorithm.
    4. (5pts) Prove that your program's return value really does satisfy S, (presuming random really does return a uniformly random result.)
26. (up to 5pts, for a very clear, comprehensive answer)

    When looking at divide-and-conquer algorithms, our sub-problems were often of the size ceiling(n/b) or floor(n/b). However, in our analysis (Th'ms 1,2 of 6.3) we presumed the recursive calls were of size exactly (n/b).

    Does this matter, for the final big-Oh results? Argue why or why not, proving your statements.

27. (3   pts) Show that N is isomorphic to N×N by giving an explicit, closed-form bijection ("closed form" meaning no loops, sums, or recursion in the expression). Argue that your function indeed a bijection.

¹ if you ever (say) publish a shareware program where buyers receive a key upon payment, to unlock/register their copy of software. [an error occurred while processing this directive] [an error occurred while processing this directive]