Extra Credit Hw

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

We will award up to 15pts of extra credit on the following problems.
(If you turn in more than 15pts worth, we'll grade the first 15pts we feel like and stop.)
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 the book), 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. Your program must work efficiently on keys of 50-100 digits, and arbitrarily long messages. 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 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. 52 #10e-j. (fo→english, fool)
4. (1.5pts) p. 54 #28a-j. (quantifier statements over ℜ)
5. (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.
6. (1   pt  ) Prove that if f is O(g), then f+g is O(g), for f,g in ℜ→ℜ.
7. (1.5pts) p.658, #24 (Huffman code)
8. (2.5pts) p.658 #26. (Huffman code w/ tie-breaking)
9. (2   pts) p.507 #28b (Warshall's alg) What is the loop invariant, for Warshall's algorithm?

10. (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.

11. (1.5pts) p.528 #6 (poset dual)
12. (1   pt  ) p.528 #10 (cross-product)
13. (2   pts) p.528 #22 (covering)
14. (1.5pts) p.529 #28 (bounds in a poset)
15. (1   pt  ) p.529 #30 (bounded posets)
16. (1.5pts) p.529 #36a (unique bounds)
17. (1   pt  ) p.529 #38 (lattices?)
18. (1   pt  ) p.565 #36. (isomorphic graphs?)
19. (1   pt  ) p.565 #42. (isomorphic graphs?)
20. (1   pt  ) p.565 #44. (isomorphic graphs?)
21. (1   pt  ) p.566 #60. (def'n directed isomorphic)
22. (4   pts) p.393 #34b-f (avg-case complexity of quicksort; requires doing #20)
23. (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.

24. A two-dimensional array A is symmetric if A[i][j] = A[j][i] for all valid indices i,j. You can see that an implementation of a symmetric-array class, rather than allocate N² locations, could instead allocate only N(N+1)/2 locations (about half), and have its own lookup method.

    One way to do this would be to use the first index as an vector-of-vectors, where the ``inner'' vectors range in size from 1 to n. (``vector'' meaning a one-dimensional array.) However, this means an array lookup takes two memory references (one for each vector). Depending on cache sizes and how the array is used, this could cause an excessive amount of cache misses.

    A more memory-stingy approach would be to internally have just a single vector, and to translate the user's i,j requests to a single index into the interal vector. This requires some index arithmetic, but fewer memory addresses.

    This problem generalizes beyond two dimensions: an m-dimensional array A (size N^m) is symmetric if, for lists of m indices idxs1 and idxs2, A[idxs1] = A[idxs2] whenever idxs1 is a permutation of idxs2. (You can think of sorting the list of indexes before doing the lookup.)

    1. (0pts) Look up triangular numbers, pyramidal numbers, and Pascal's triangle.
    2. (1pt ) How many data can be stored in an n-dimensional symmetric array?
    3. (2pts) Implement two-dimensional symmetric arrays, using the single-internal-vector approach.
    4. (3pts) For comparison, implement the vector-of-vectors strategy. Run a sufficiently wide range experiments, to compare the running time of these two approaches for various sizes.
    5. (4pts, but only after doing the next part) For comparison, implement n-dimensional symmetric arrays with a vectors-of-vectors-of-…-of-vectors approach. Run a sufficiently wide range experiments, to compare the running time of these two approaches for various sizes. Discuss locality of memory, and the pros/cons of using hash tables instead of .
    6. (5pts) Implement n-dimensional symmetric arrays, using a single-internal-vector approach.
       (Nice, but not necessary: can you find an indexing scheme which doesn't need to know the size of the n-dimensional array?)
25. (1-12pts) How many different non-equivalent states are there in the game Air, Land, Sea? Discuss, including implications for data definitions. (How does this relate to eq? (or ==) vs equal? (or .equals(•))? Full points requires significant work/thought; you'll probably want to start with a precise definition of ``equivalent states''.
26. (2pts) Section   6.3 #28 (p.434). (hi-lo with one lie)

27. (1.5pts) First, look at some sites like tinyurl.com or snurl.com which take long URLs and create new short names for them. You might wonder how quickly such sites will run out of short names.

    If there are 10¹⁰ static web pages, and every single one of them were registered on such a site, how long would be the longest small URL be? (Just count the encoded part of the name, without the initial ``http://www.snurl.com/'' prefix.)

    We might then start to wonder, is 10¹⁰ a reasonable upper estimate on the number of web pages? After all, one of the best use of these sites is for abbreviating dynamic URLs which contain (long) queries embedded inside them (e.g. mapquest URLs). So we'll ask the same question, but now suppose that 10¹⁰ people each generate one dynamic request per second, for 10¹⁰sec (about 325 years — e.g. since William of Orange took the English throne in 1688). How long will the longest short-URLs be now?

    To think about to yourself:
    Does one of these sites do a better job than the other? Which do you prefer?

28. (1.5pts) Section 4.2, #10 (p.319). (integer midpoint)
29. (1pt) Section 4.3, #16 (p.325). (odd-sized subsets).
30. (1pt) Section   4.3, #22a,c,f (p.325). (alphabet soup).
31. (1pt) Section   4.4, #18 (p.333). ([11]_b⁴)
    That is, Take the number which is written as "11" in base b. What is that number to the 4th power? (Express your answer as a numeral written base b.)
    The mention of Pascal's triangle may or may not actually help you, but it's worth reading the blurb in the book relating the triangle to combinations.
32. (2pt) Section   6.6 #  6 (p.464). (squarefree)

¹ 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]