Nov 3rd 2013

This week's material is an extension of the material from the previous week. Using the concept from the previous week, we have learned a new ADT: binary search tree. By implementing binary search tree ADT, searching through can be much more efficient. This is due to the fact that depending on the specific data value with respect to the root, certain parts of the tree can be ignored. While this seems to be rather trivial as a student, but its effectiveness can be certainly appreciated when it comes to large data sets such as trees that exist in operating systems.

One thing that I really enjoyed over the past week is the introduction of the big O notation. I have personally really enjoyed this material due to my Mathematics background and that it really gives me a sneak peak at the theoretical aspects of computer science. The big O notation is a concept that is widely applied throughout mathematics. In essence, it captures the limiting behaviour of a specific function.
Formally speaking: f (x) -> O ( g (x) )  as x -> infinity  <=> lim x->infinity sup|f(x)/g(x)| < infinity
where the sup notation denotes the least upper bound of a specific set. and | | denotes not necessarily the absolute value but the norm of R1. From this more concrete definition, we can have a better understanding of why T1(n)=(0.3365n2 + 0.17n + 0.32) s and T2(n)=(0.47n2 + 0.08n) s are both O ( n^2). By taking the limit of Ti(n)/n^2 as x -> infinity i = 1, 2 , by L'Hospital's Rule, T1(n)/n^2=0.3365 and T2(n) = 0.47. Since both of which are real numbers, we can say that n^2 describes the limiting behaviour of both functions within a certain constant and therefore both algorithms' efficiency are O(n^2).  
In terms of the assignment, I have encountered a challenge this week. The challenge is how to create a recursive data type from a know linear data type such as a string. The second assignment requires us to initialize the tree expression for a regular expression string. But the creation of a tree requires a data type that is recursive in nature. Therefore, the approach that I have decided to take is that first, recover the tree list representation of the regular expression string. secondly, use a recursive algorithm to link the data as nodes. As it turns out, by using a recursive algorithm to peel off the brackets in the string one by one, one can really recover the treelist representation of a regex. From there, it should be very straight forward to link the lists together using the exsting definitions of nodes provided by the course document.