ITEC 122 2007fall ibarland

home—info—lectures—hws—exams

hw11
counting, concluded
reading about grammars

1. 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.

   1. How many different characters does the site choose from, when generating shortened-URLs? (More than 26, as a-z are all used, as well as ...?) If you need to generate one or two short-URLs, go ahead.
   2. How many possible shortened-URLs have length exactly¹ 6?
   3. How many possible shortened-URLs have length 6 or less?

   4. 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.)

   5. 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 320 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?

2. p.344, #30a-e (5ed, p.310 #28a-e): alphabet soup
3. p. 361 #18 (5ed, p.324 #18): flipping eight coins
4. p. 369 #9 variant (5ed, p.333 #9, variant)
   1. What is the coefficient of x¹⁰¹y⁹⁹ in the expansion of (x+y)²⁰⁰?
   2. What is the coefficient of u¹⁰¹v⁹⁹ in the expansion of (3u-2v)²⁰⁰?
5. p.398, #4 (5ed p.360, #4) Remember: divide the number of "desired" outcomes by the number of possible outcomes.
   (We presume that each day is equally likely, out of the 366 possibilities).
6. p.398, #6 (5ed p.360, #6) When counting desired outcomes, be sure not to accidentally count the ace of hearts twice!
7. p.398, #8 (5ed p.361, #8)
8. Reading:
   • (5ed §11.1) Languages and Grammars
9. (5ed p.749, #4ab).
   As mentioned in the reading, “S→AB” means “you can replace the substring "S" with the substring "AB"”; the question asks you to keep making substitutions until you only have lower-case letters (“terminals”).

home—info—lectures—hws—exams

©2007, Ian Barland, Radford University Last modified 2007.Nov.27 (Tue)

Please mail any suggestions (incl. typos, broken links) to iba�rlandrad�ford.edu