Week 10: More Big-Oh and Better Sorts

This week, we focused on more big-oh's and a bunch of new sorts including quick, merge, count, and python's own hybrid timsort. One of the sorts that stand out the most to me is quick sort. When I was younger, everybody says that quick sort is everyone's favourite sort but that was pretty much the only thing I know back then. Now, it is amazing to be able to analyse WHY it is everybody's favourite. The biggest difference between quick sorts and all the other sorts is that it chooses a pivot and begins to partition. Generally, it performs better than most sorts (eg. insertion sort with O(n^2)) because it does not rely on swaps and redundant calls. Thus, making quick sort as optimized as possible. Merge sort is pretty awesome too as it splits up elements and joining them together in pairs, quadruples, and so on. It seems like a pretty slow process but surprisingly, it results in O(nlg n).

Professor Heap showed us that we could compare different types of sorts by calculating the duration of each execution. I found it absolutely amazing because nothing beats being able to see the results before your own eyes. The cool thing is that it is not limited to just sorting algorithms but to any programs.

Week 9: Performance and Big-Oh

In this week's lectures, we focused on performance of algorithms and the famous (or notorious) Big-Oh notation. Being able to see the efficiency difference between the algorithms we often deal with daily really does help bring my thoughts together. I have been programming for quite a long time now and I have never given a real thought to what goes on behind the program and what makes it more efficient than the other ones. In terms of Big-Oh, O(1), O(n), O(2^n) and such are very straight forward but I find O(lg n) to be one of the most interesting algorithm behaviour. I never understood the definition of logarithm in math class until now. Take binary search as an example, the worst case performance is O(lg n) because it keeps dividing a list in half until the search is either found or not. If there are 8 elements in the list, the worst case would take 3 steps to find an element that exists. 

Being able to see the a diverse amount of  algorithm behaviours certainly bring my awareness up whenever I am programming. I am now super conscious of my codes and try to keep it as clean as possible without losing too much on overhead.

The most challenging part this week is not so much about the algorithm behaviour, but having to understanding different kind of sortings because I am not too familiar with them. For instance, I have heard of insertion and bubble sort before but I never tried to program it myself so it takes me a bit of time trying to figure out where the codes are heading.

Week 8: Linked Lists

We focused on a data structure called linked list this week. It is very queue to a stack except each object inside the data structure holds the reference to the next object. However, it is comparatively much more superior to a queue in terms of efficiency because insertion of new elements mean only having to deal one reference (as opposed to moving items back and forth in a queue).

The lab was very challenging this week because we had to literally code to find the length of the linked list and how to insert a new element to a desired position without raising any errors. I realized I over think many parts of the code and it definitely consumed a lot of time (tried to use recursion every where I could). Sometimes, it is better to think from a more simpler perspective and it could turn out to be a lot more.  

Week 7: Recursion

Recursion is the technique of being clean and smooth by dividing a big problem into similar sub problems and solving it as it is. The basic idea behind recursion is to solve those sub problems since they are more easily solved and thus, put them altogether as the final solution. One thing I have learned is that anything you can do with recursion could also be done using iterative loops. Obviously, the complexity of it comes down to specific context. For instance, it is possible to use pure loops for solving the tower of hanoi, however, it is so much more efficient and clear to use recursion because tower of hanoi could be split into smaller yet similar structure of problems. Many would ask: when should you use recursion? Personally, I think one should use recursion when the problem presents itself as a composition of similar small problems. The key to choosing between iterative loops and recursion is whichever one is more easier to use for the specific context. There is no need to be fancy and use recursion in every single problem. One thing to note about recursion is that it could lead to a significant amount of overhead which could slow down the program's overall efficiency. The best way to find out whether iterative loops or recursion is more efficient is to have two version of the codes and compare them.

Week 6: Binary Trees

This week, we learned something called trees and it is something completely new to me. However, I didn't find the concept of trees difficult at all, rather, it was pretty straight forward. I find trees exceptionally cool because unlike the other linear data structures we have learned so far in this course, trees work very differently. With that being said, they certainly have different ways to traverse this data structure which makes it very interesting and intriguing.

As I have stated earlier in the blog, I am not very strong at visualizing recursion off the top of my head. Fortunately, I remembered to draw out the recursions when I was tracing the implementation of trees and it definitely helped me understand it a lot better. This week's learning isn't too bad compared to previous weeks.

Looking back at all the concepts we have learned, I just realized we are focused primarily on data structures. I guess knowing these must be very important either for upper computer science courses or our future job placements (both could work as well).

Week 5: Namespace, Scopes, Unit Testing, Tower of Hanoi

This week, we focused on namespace, scopes, unit testing, and the notorious algorithm of "Tower of Hanoi". All in all, I did not have a problem with namespace, scopes, and unit testing as they are mostly very straight to the point. However, the recursions behind the Tower of Hanoi prove to be highly challenging. Tracing the first few steps is relatively easy but afterwards, the numbers just decide to explode all over the place. With the confirmation of the first few traces, I have to use what Professor Heap like to call ,"intuition", to believe that the recursion works. In terms of recursion, being able to believe it works really assist me into thinking ahead in any kind of programming questions.

With that being said, majority of the time spent this week was dedicated to finding the solution to Tower of Ann Hoy that uses four stools. Indeed, it was devastatingly hard because recursion prove to be so abstract inside my brain. Luckily, the handout made it easier by reminding us to split the algorithm in three parts, where first and last basically uses the same concept for 4 stools and the second is a complete copycat of the codes of three stools. I realized when it comes to recursion problems, my thinking becomes optimized when I use pencil and paper. The human brain is simply not a stack so we could only remember so much before we forget the rest. I traced the most simple number of cheeses I could think of and found a very common trait between the algorithm of four and three stools. Although my current codes are not optimal, I am really proud that I toughed it out and found an alternate solution.

Week 4: Learning Recursion

This week, we focused heavily on the use and effectiveness on recursion. I certainly have heard of this technique in solving problems before but never really wrapped my head around it until now (although I would say that I am still pretty bad at it). Recursion is definitely very powerful technique if used correctly at the right situations but honestly, simple iterations should be used whenever possible (not over thinking a problem). I was realizing this because as we learned in the first few weeks of class, every single time a method is called, it is put onto a stack and as a result, takes up more memory. In the case of constant recursive calls, it makes a lot of sense that it would create an immense amount of overhead to execute its codes. It would be sensible to avoid recursion as much as possible.

However, I was looking ahead into the course and realize that recursion sometimes prove to be the best thing there is. For instance, traversing a complex data structure like a tree-list requires the need to recursively search up nested-lists. Obviously, anything that could be done recursively could be done using iterations. Unfortunately, it would take an excess amount of confusing loops in order to achieve traversing on data structures.

I struggle a lot with recursion because I tend to think about a problem as a whole as opposed to trying to think of it small (how a problem could be broken down into smaller yet similar problems). The more practice I do, the better I feel I am getting. Hopefully, the practice I have done is enough for me to handle the recursions used for the upcoming weeks where we will learn about link lists, tree lists, binary tree lists etc.