Analysis of Algorithms : An Active Learning Approach

18 ANALYSIS BASICS

(1.20)

(1.21)

When we are trying to simplify a summation equation, we can apply Equa-

tions 1.8 through 1.12 to break down the equation into simpler parts and then

apply the rest to get an equation without summations.

1.3.5

1. Typical calculators have the ability to calculate natural logs (to the base e)
   and logs base 10. How would you use a calculator with just these capabili-
   ties to calculate log 27 59?


2. Assume that we have a fair five-sided die with the numbers 1 through 5 on
   its sides. What is the probability that each of the numbers 1 through 5 will
   be rolled? If we roll two of these dice, what is the range of possible totals of
   the values showing on the two dice? What is the chance that each of these
   totals will be rolled?


3. Assume we have a fair eight-sided die with the numbers 1, 2, 3, 3, 4, 5, 5, 5
   on its sides. What is the probability that each of the numbers 1 through 5
   will be rolled? If we roll two of these dice, what is the range of possible
   totals of the values showing on the two dice? What is the chance that each
   of the numbers in this range will be rolled?


4. You are given four dice that have numbers on their faces according to the
   following lists:
   d 1 : 1, 2, 3, 9, 10, 11
   d 2 : 0, 1, 7, 8, 8, 9
   d 3 : 5, 5, 6, 6, 7, 7
   d 4 : 3, 4, 4, 5, 11, 12
   For each pair of dice, compute the probability that the first die will have a
   higher value showing than the second will, and vice versa. You can easily
   show your results in a 4  4 matrix where the row represents one die and

1

i=1--i

N

∑ = lnN

lgi

i=1

N

∑ ≈N lg N–1.5

■1.3.5 EXERCISES