Hw10: Counting I

Due 04.Apr.13 (Tue) 17:00.

Before you tackle the homework, remind yourself of our general hw policies.

Reading: Rosen 4.1-4.4.

1. (3pts) Consider strings of length ≤ n over the alphabet Σ = {a,…,z}. What fraction of these strings are length exactly n? Give your answer as a constant plus a big-Oh error term that goes to zero (e.g., "1/2 + O(1/log(n))".) [For post-2004:] Show your work.
2. (2pts) Section 4.1, #32 (p.311). (4ed: p. 243 #32) (|Z/n -> Z/2|)
   To yourself: Compare to a set's indicator function.
3. (2pts) Section 4.1, #54 (p.312). 4ed: p.244 #52 (|{n-var boolean functions}|)
4. (2pts) Section 4.2, #10 (p.319). 4ed: p.249 #10 (integer midpoint)
5. (3pts) Section 4.3, #18 (p.325). 4ed: does not exist (flipping outcomes).
6. (3pts) Section 4.3, #22a,c,f (p.325). 4ed: does not exist (alphabet soup).
7. (4pts) Section 4.3, #26 (p.325). 4ed: ??? (softball).
8. (4pts) Counting passwords.
   We will consider a few various passwords schemes. Let a "common word" be an English word 6-8 letters, found in a reasonable dictionary. As an estimate, we'll guess that there are 12,000 common words¹. Here are some password schemes that we'll compare:
   1. Common words.
   2. A hyphenated pair². of common words e.g. "frolic-meridian".
   3. A common word, with but with one letter's capitalization changed, and then one digit inserted somewhere. Assume that there are the same number of 6-letter, 7-letter, and 8-letter common words.
   4. For comparison: all possible strings of length 6-8, of 80 possible characters (which is roughly the number of letters, digits, and common punctuation).
   Supppose you're trying to find somebody's password by brute-force checking all possible combinations, and that you can check 10⁹10³ passwords/sec. For each of the above schemes, how long is needed to try all possibilities? Give your answer to two significant figures³, using the most appropriate unit from {seconds, minutes, hours, days, years}. Full credit for answers within 2% of the exact answer, as we're already making quite a few assumptions anyway.
9. (2pts) Section 4.4, # 4 (p.333). 4ed: p.259 #36 (coeff of x⁵y⁸ in (x+y)¹³)
10. (2pts) Section 4.4, #18 (p.333). 4ed: does not exist ([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.
11. (3pts) Explain the Flash Mind Reader (Flash plug-in required).
    Your explanation shouldn't contain unsubstantiated claims about properties of sums of a numeral's digits; if you want to argue about such numerals, name the parts and show the property holds.

12. (0pts) For fun/thought, not to turn in.
    Visit tinyurl.com or snurl.com. If there are 10¹⁰ static web pages, and every single one of them were registered on such a site, what how long would be the longest small URL be? Does one of these sites do a better job than the other? Which do you prefer?

    This of course leads to question our assumptions: Is 10¹⁰ a reasonable upper estimate? How about dynamic URLs -- that is, ones which have a hashed form of the query encoded in them, and the server decodes the question to serve up a specific answer (e.g. mapquest). Can you reasonably bound the possible number of mapquest answers? How about, the number of dynamic URLs that may have been issued in the history of the web?

Not that this is an issue we've explored at all in this class. so that bounds could be propogated through to include in the answer.) (A more rigourous treatment would give error bounds to all inputs, so that bounds could be propogated through to include in the answer.) (back)

Information --- Staff --- Homework --- Reading/Lecture note --- Newsgroup --- Feedback