Analysis of Algorithms : An Active Learning Approach

10 ANALYSIS BASICS

both their data and software. In this case, developing small programs that store

data compactly is not only important, it is critical.

1.1.3

1. Write an algorithm in pseudocode to count the number of capital letters in
   a file of text. How many comparisons does it do? What is the fewest num-
   ber of increments it might do? What is the largest number? (Use N for the
   number of characters in the file when writing your answer.)


2. There is a set of numbers stored in a file, but we don’t know how many it
   contains. Write an algorithm in pseudocode to calculate the average of the
   numbers stored in this file. What type of operations does your algorithm
   do? How many of each of these operations does your algorithm do?


3. Write an algorithm, without using compound conditional expressions, that
   takes in three integers and determines if they are all distinct. On average,
   how many comparisons does your algorithm do? Remember to examine all
   input classes.


4. Write an algorithm that takes in three distinct integers and determines the
   largest of the three. What are the possible input classes that would have to
   be considered when analyzing this algorithm? Which one causes your algo-
   rithm to do the most comparisons? Which one causes the least? (If there is
   no difference between the most and least, rewrite the algorithm with simple
   conditionals and without using temporary variables so that the best case gets
   done faster than the worst case.)


5. Write an algorithm to find the second largest element in a list of N values.
   How many comparisons does your algorithm do in the worst case? (Later,
   we will see an algorithm that will do this with about N comparisons.)

1.2 What to Count and Consider

Deciding what to count involves two steps. The first is choosing the significant

operation or operations, and the second is deciding which of those operations

are integral to the algorithm and which are overhead or bookkeeping.

There are two classes of operations that are typically chosen for the signifi-

cant operation: comparison or arithmetic. The comparison operators are all

considered equivalent and are counted in algorithms such as searching and

■1.1.3 EXERCISES