Week 9 of CSC148: BSTs, Runtime, Efficiency, and Exercise 3

So it seems this was the final week on tree data types as we transitioned from binary search trees into runtime and efficiency of algorithms, and ultimately the idea of big-oh, which I'll save for another week once we've done more work on it. Binary search trees, although a new concept, was more of a modification on something that I understood well at this point, and if anything, was a simplification of these concepts. The idea is that for every parent and its children, the left sub-tree must contain a smaller value than the integer value of the parent while the right sub-tree had to a have larger value. This is an expansion of something that was taught in CSC108, and actually made the concept a lot clearer for me. I believe the main thing to take a way from this ADT is that every time the algorithm is run, the size of the pool of possible values is cut in half. Contrast this to a regular Tree ADT, one where there is an integer at every node without the restriction on the left and right children. In this case, the algorithm must search the entire tree in the worst case, a linear runtime. And as we learnt, linear runtime is not a runtime you want to be dealing with! 

As for E3, I had a little bit of difficulty with the functions we had to write but in the end I was very happy we were tested on this material. Being forced to grind out some work on recursion really helped me get to a point where I now feel very comfortable with recursion. I finished the exercise fairly quickly with some clunky code but decided to use recursion to its full potential and I ended up with some clean code I was very proud of. A big part of this was remembering a little aid I had read somewhere for writing recursive functions, I believe it was in the readings for the intro week on recursion. The trick is to start writing a function for every possible size of the input. So, start with the base case, of course. Then go on to writing a function that deals with the case where there are two of whatever you're dealing with, and so on. Hope that tip helps anyone that may be reading!

Now on to the second part of assignment 2...