CSC152 2006S, Class 50: About Exam 2 Admin: * Toys from this past weekend. * Questions on Exam 3? * replacmeent? to replace, in an interesting way * I don't understand the last case in problem 3 (finding an element with i smaller elements) * Pivot splits into three parts: smaller, of size s pivot larger, of size h * Cases s = i - pivot is the element we want s > i - the element we want must be in smaller, recurse on smaller s < i - the element we want must be in larger, recurse on larger * Reading this afternoon (maybe) Overview: * Problem 1: Graphs. * Problem 2: Random Linear Structures. * Problem 3: Dynamic Arrays. * Problem 4: Heapsort. Graphing Functions In the abstract * Column = (x / maxX) * width * Row = (y / maxY) * height Problem, x, maxX, width are all integers Solutions? * Cast to reals for computation, cast back to integer * Change the order of operation (x * width) / maxX * Stored maxX / width (as a real) in a field, scaleX compute x / scaleX Morals: * Worry about integer vs. double * Think about relationships * Use subclassing when possible Problem 2: Random Linear Structures. * Initial idea: Shove new values at the end of the vector To remove a random thing, pick a random number and remove the thing at that index * But: * Need O(1) get * Don't remove the random element, swap the last element to its location and then remove the last element * Similar to an idea from Heaps * Want peek to return the same value as get * Precompute the random number * Update add to put in a random location and move the random thing to the end; get removes the end * Moral: Reversing strategy sometimes helps * Problem 3: Dynamic Arrays * When someone asks for an index beyond the currently-legal ones, build a bigger underlying array (and copy over the values) * Question: How much bigger should the new array be? * Exactly the requested size * If we do something like for (int i = 0; i < N; i++) { mystuff.set(i, new Integer(i)); } * We get O(n^2) * Better strategy: Change how we expand * Don't expand by a constant amount * Instead: DOUBLE the size * Problem 4: Heapsort. if (this.order.compare(this.contents.get(__),this.contents.get(__)) __ 0) To make more readable, write this.compare(___,___) Cases for swap down * No children: Stop, Done * No right child: Check the left child If the left child is smaller swap recurse * Two children Find the smaller child Compare to child If child is smaller swap recurse