Problems for Session A3: Analyzing Algorithms

Problem A3-A: Plotting exponentiation

Determine the wall-clock time it takes to compute 1.3^N recursively for every n between 0 and 100. (Note that you'll need to be careful to measure only the time of execution.) Plot the points. Is the curve smooth? If not, suggest why not.

Problem A3-B: Comparing exponentiation

Determine the wall-clock time it takes to compute 1.001¹⁰²⁴ recursively. Determine the wall-clock time it takes to compute 1.001⁵¹¹ iteratively. Which is quicker? Why?

Problem A3-C: Plotting exponentiation, revisited

Determine the number of steps used to compute 1.3^N recursively for every N between 0 and 100. Plot the points. Is the curve smooth? If not, suggest why not.

Problem A3-D: Comparing exponentiation, revisited

Determine the number of steps it takes to compute 1.001¹⁰²⁴ recursively. Determine the number of steps it takes to compute 1.001⁵¹¹. Explain the difference.

Problem A3-E: Sorting

Note that we can use our modified kSmallest algorithm to sort arrays (i.e., put all of the elements in order). How? If there are n elements in the array, we ask to find the n smallest elements. Since the algorithm puts the n smallest elements in order, it has sorted the whole array.

Use this observation to add a sort method to IntSeq (and to StringSeq, if you developed it).

Problem A3-F: Sorting, revisited

Find a textbook or Web page that discusses sorting and determine the name of the sorting algorithm we developed in problem A3-E.