18
for class on Thursday April 9, 1998
Please read Sections 7.7 and 7.8 of the Schneider and Gersting text, and be prepared to discuss the following:
1. Once again, more on sorting. Try to wrap your head around this idea: a sort procedure might call itself on some smaller portion or portions of the array to be sorted. ``But but but'' (I hear you cry) ``...how can that work? Isn't that a circular definition?'' Well here's one way to do this: you can sort an array by first sorting the left half, then the right half, and then merging the two sorted halves. Of course if the array has size 1 you're already done and can return. The tricky part is this: when you go to sort the left half, you use this very same procedure, and sort the left half's own left half and right half and merge those. The underlying idea here is a powerful (and sometimes difficult) tool known as recursion.
2. The text discusses debugging as part of the software life cycle. Consider the difference between trying to demonstrate that there are no bugs in a certain program, and trying to show that there are some. Which would you rather do, if you were on the debugging team for say Netscape version 29 ?