This week, I'm revisiting an old SLOG and analyzing how I've changed over the course. I am choosing to revisit my third SLOG, which was about recursion. During the time of that SLOG, I was very confused about recursion and I found it very difficult to understand. Now that we are in the final weeks of CSC148, I have had more practice with recursion both conceptually and when programming. I'm even using it in my current program in Assignment 3!
I now understand recursion as a very vital asset in terms of programming. It can make searches, creation, and the like so much more easier when you can recurs over the entire function. While it is sometimes very frustrating to implement in a program, it makes complex problems seem like a thing of the past.
This week in class, we learned about the run times of programming and what we can do to increase or decrease run time. This was also like an introduction to CSC165, which is a computer science course on mostly the "science" part of CS. For example, the run time of a search, say n in L, is dependent on the length of the list. This means the run time has a direct relationship to the length of the list.
We also learned that there is a formula for the maximum number of nodes in a binary tree, (2^n) - 1. Not only that, but the maximum number of leaves the last row of a tree can have, 2 ^ (n - 1). When talking about the height of the tree, we know that n ≤ (2^h) - 1, or log(n + 1) ≤ h.
We can also look at run times in sorting algorithms. Back to CSC108! We discovered that bubble, selection, and insert sort all have a run time proportional to the list by n^2. This means that the run time is quadratic. This makes the algorithm very slow, so we created a new sort, quick sort, which has a run time of log(n), proportional to the list. This makes the sort speed super fast!
This whole logarithm thing still confuses me, so I'm hoping if and when I take CSC165 that I will understand the logic behind all of the run times and I will better learn how to do the science behind the programming.
very impressive slog, but I can see that you did not consistently write your entry every week, seeing how 3 weeks course material review is packed into one slog entry. Anyway great job!
ReplyDeleteI agree with you on the fact that this whole run time and big-Oh thing is still very confusing! I too did not take CSC165 before and had trouble understanding the topics we learnt at the end of class. Also, thanks for reminding me about the formulas for the maximum number of nodes in tree, had completely forgotten about that!
ReplyDelete