ITEC 122 2008fall ibarland

home—info—lectures—exams—archive

hw11
counting; cardinality

1. (6pts) p.344 #14 (5ed p.310 #14) variant:
   How many bit strings are there of length n or less which both start and end with a "1"?
   (Hint: Your answer should include an if or case statement, to handle the base case(s) correctly.)
2. p.353 #4 (5ed p.319 #4) A bowl contains ten red balls and ten blue balls. A woman selects balls at random without looking at them.
   1. (2pts) How many balls must she select to be sure of having at least three balls of the same color?
   2. (1pt) How many balls must she select to be sure of having at least three blue balls?

3. 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. (1pt) 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. (1pt) How many possible shortened-URLs have length exactly¹ 6?
   3. (2pts) How many possible shortened-URLs have length 6 or less?

   4. (2pts) 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. (2pts) 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?

4. p.344, #30a-e (5ed, p.310 #28a-e): alphabet soup
5. (8pts 4pts ) p. 361 #18 (5ed, p.324 #18): flipping eight coins

home—info—lectures—exams—archive

©2008, Ian Barland, Radford University Last modified 2008.Dec.18 (Thu)

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