CSC 148 SLOG for Week 8

         This week we learned about binary tree lists that are arranged in the order of the left subtree being smaller than the root and the right subtree being larger than the root. We looked at how the insert, find, delete and find max methods work using recursion, and in the exercise we are supposed to implement a contains and a max node method using iteration following a model of the insert method in iteration. I find material we learned in class this week pretty easy since we've already learned binary tree extensively. We also learned about searching and sorting efficiency, which I still feel a little unclear about. I learned about big-O notation and efficiency in high school but we didn't go into too much detail of it, so I read the lecture slides carefully and listened carefully in class and now I think I have a good understanding about the notation. I think it is a bit similar to limits, which I learned in calculus. When n get very large, the efficiency approaches n or n^2 or log(n) or nlog(n) which when I drew a graph of the efficiency versus n of the first few points seem pretty reasonable to assume if n approaches infinity. This concept once again confirms the fact that math and computer science are very related and I could use some math concepts such as graphing to help me solve hardships in computer science. The exercise this week was enough since I only needed to follow the model of insert to implement the methods contains and max node. I spent a long time on the lab this week but it was solely because I misunderstood the question. After rereading it I just thought for a while and knew how to do it. I finished the assignment this week and find this assignment just as interesting as the last assignment. Even though this one is not as complicated and long as the last one, it is pretty challenging to understand the concept of regular expression and comparing it with string. Unlike the professor, I actually found the first part quite easy since I only needed to turn a string into a tree. I used the method of checking the number of parenthesis and working my way from the top down, finding the symbol for the root every time and recursively initialize regextrees as the left and right children. However I did encounter a lot of trouble on the second part since I was unsure whether I should check from the top down or the bottom up. The major source of difficulty was that I didn't know where to partition the string to check for for example the left child of a dot root. In the end I used a for loop to check for every single partition and every single number of elements. Then everything flowed smoothly and I implemented the bar, which is very similar to the dot and the star.

         I agree with amber from http://amberlikescode.blogspot.ca/ in that binary search trees and binary trees are super useful and even though they are not built-in data types they become natural after some practice. My roommate told me that microsoft actually asked him about binary trees during an interview.