I felt that the past couple weeks have been vastly different compared to the first eight or so weeks of the course. It seems that we have stepped into a more mathematical and theoretical component of computer science whereas the first couple weeks were about learning the technical aspects of programming like developing classes, using recursion and generally getting our programs to work by any means necessary, which felt more like a continuation of CSC108. I feel that the material that was explored in the final portion of this course is considerably more valuable than the technical programming skills that we were taught because making code efficient is more difficult (usually) than writing code that works but is inefficient for the most part.
An interesting concept that we learned this week was expressing the run time complexity (worst case in particular) of some sorting algorithms. In particular, we learned how to express the worst case run time of an algorithm by finding a tight bound for that function. By tight bound, we mean another function that grows like the worst case run time of our algorithm so that we can show how inefficient or efficient a particular algorithm is. When we find a tight bound for the run time of an algorithm, we say that it is a O(insert tight bound here) algorithm, or in words, the run time of that algorithm is in Big-Oh of (insert tight bound here). In intuitive terms, this means that the growth rate of the algorithm is like (insert tight bound here).
A sorting algorithm whose run time we analyzed is merge sort. This algorithm sorts a list by recursively splitting a list in half, sorting it, and then merging the two halves. This has a complexity of O(nlogn) because we can divide a list of length n log(n) times and then we must merge the sublists which takes n repetitions until we only have one final list. This means we have a complexity of O(nlogn) altogether for merge sort in the worst case (also in the average case). I found merge sort to be a rather unique sorting algorithm because its worst case run time, average case run time, and best case run time are all O(nlogn). I believe that the reason for this is the list will still be recursively split in half and then merged together which takes n repetitions even if the list is already sorted so the best case run time is relatively the same as the worst case run time.
I found quicksort to be an algorithm that was relatively easy to follow and so I enjoyed it. We pick a pivot value, and move everything less than the pivot before the pivot and everything greater than the pivot after the pivot. Now the pivot is in the right place. We now recursively call quicksort on the sublists to the left of and right of the pivot (much easier to understand than mergesort). The fact that quicksort can have a worst case run time of O(n^2) was kind of intimidating because it made me think of how real programmers have to account for such worst cases and it can often be very difficult. Normally, the run time of quicksort is (logn) which is very fast but choosing the pivot might be tricky. Thankfully, we are computer scientists so we can think of ways to effectively choose a pivot to try our best to avoid the worst case.
I enjoyed this portion of the course significantly more than the first portion because it required more thinking and analysis than just brainlessly trying to get a program to work. However, I did find it intimidating that in the future, I will have to worry about getting my program to run efficiently, something that I didn't really care for before. I also felt that we should've spent more time covering this topic because it is substantially more difficult because we didn't do much analysis of runtimes before and it was hard to grasp immediately. I find it frustrating that we rushed through one of the more complicated portions of the course and I also feel that we spent way too much time on recursion when we should have been learning more about optimizing our algorithms because it will be very important in the future.
