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