Analysis of Algorithms : An Active Learning Approach

1.3 MATHEMATICAL BACKGROUND 13

that for these five groups all probabilities would be 0.2. We could calculate the

average case by the above formula, or we could note that the following simplified

formula is equivalent in the case where all groups are equally probable:

(1.2)

1.2.2

1. Write an algorithm that finds the middle, or median, value of three distinct
   integers. The input for this algorithm falls into six groups; describe them.
   What is the best case for your algorithm? What is the worst case? What is
   the average case? (If the best and worst cases are the same, rewrite your
   algorithm with simple conditionals and without temporary variables so the
   best case is better than the worst case.)


2. Write an algorithm that determines if four integers are distinct. Depending
   on your viewpoint, the input for this algorithm can be divided into classes
   based on the structure of your algorithm or the structure of the problem.
   Describe how one of these two class divisions would be set up. Using your
   classes, what is the best case for your algorithm? What is the worst case?
   What is the average case? (If the best and worst cases are the same, rewrite
   your algorithm with simple conditionals and without temporary variables so
   the best case is better than the worst case.)


3. Write an algorithm that determines, given a list of numbers and the average
   or mean of those numbers, if there are more numbers above the average
   than below. Describe the groups that the input would fall into for this algo-
   rithm. What is the best case for your algorithm? What is the worst case?
   What is the average case? (If the best and worst cases are the same, rewrite
   your algorithm so it stops as soon as it knows the answer, making the best
   case better than the worst case.)

1.3 Mathematical Background

There are a few mathematical concepts that will be used through out this

book. The first of these are the floor and ceiling of a number. We say that

the floor of X (written X) is the largest integer that is less than or equal to

X. So, 2.5 would be 2 and 
7.3 would be 
8. We say that the ceiling

An() m----^1 ti

i= 1

m

= ∑

■1.2.2 EXERCISES