# Class 50: Discussion of Exam 2

Back to Faster Sorts. On to Graphs.

Held: Tuesday, May 2, 2006

Summary: Today we discuss important issues from exam 2.

Related Pages:

Notes:

• I took my kids to Chuck E. Cheese this weekend. I brought you back silly presents.
• Are there new questions on exam 3?

Overview:

• Problem 1: Graphs.
• Problem 2: Random Linear Structures.
• Problem 3: Dynamic Arrays.
• Problem 4: Heapsort.

## Problem 1: Graphing Functions

• My experience was that it was easier to implemented `ScaledGraph` if you subclassed `Graph`.
• A common strategy was to have a scale factor, which is the ratio of the width to the maximum X.
• A few of you made "interesting" decisions about storing the scale factor.
• If you made the scale factor the ratio of the maximum X to the width, you had to divide by the scale factor to convert an x to a column. Division is more expensive than multiplication.
• I made the decision to store the width and the maximum X, which is also less efficient.
• If you didn't cast the width and the maximum X to doubles before division, you often got a bad scale factor (such as 0).
• Few of us did well with graphs in which maxX was less than width. (In fact, such graphs probably need support for real functions, rather than integer functions.)

## Problem 2: Random Linear Structures

• Most of you decided upon a simple initial strategy: Have `get` select a random element.
• The problem then became how to remove that element. The built-in `remove` operation is O(n).
• The solution? Move the last element in the vector to the place you're about to remove.
• How did you make `peek` match the next call to `get`.
• Most commonly, but computing the random location in advance.
• Less commonly, by making the `add` method randomize, and always returning the last value.

## Problem 3: Dynamic Arrays

• Too many of you relied too closely on random documentation you found on the Web. In particular, you were tempted to use `System.arrayCopy`, but weren't sure what parameters to give it.
• Why did the "expand to exactly minimum size" strategy make things slow?
• Because each time we add something to the stack, we need to expand it.
• If each expansion is O(n) and we do O(n) expansions, we do O(n2) steps.
• Some of you failed to gather supporting empirical data because you only tested small values of n. One of the issues in asymptotic analysis is that you often only see the pattern for larger values.
• See AnalyzeStack.java for analysis.
• What is the solution?
• The simple solution is to simply ensure a size for the stack when you start.
• But stacks are supposed to be dynamic.
• The better solution is to expand the underlying array by more than a little. In particular, if you double the size each time it needs to expand, it expands rarely. (In fact, to expand to size of n, you only need log2(n) expansions, for a total cost of less than 2*n.)

## Problem 4: Heapsort

• See sample code.

Back to Faster Sorts. On to Graphs.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Tue May 9 08:31:56 2006.
The source to the document was last modified on Thu Jan 12 14:58:07 2006.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2006S/Outlines/outline.50.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu