Efficiency and Sorting

    For the past few weeks, we have been ignoring recursion(Yay!) and focusing on something that really peaks my interest, sorting lists, and the efficiency of these functions and of many more beyond that. The types of sorting algorithms studied in detail include: Selection Sort, Bubble Sort, Quick Sort, Insertion Sort and Merge Sort. In addition, we learned briefly about the extremely efficient default sort on python, Timsort. Finally, the way efficieny was measured for these algorithms is by Big-Oh analysis. The rules of this type of analysis state that when declaring the efficiency of a function, you must first find the general equation of how many steps are run then simplify it to the highest power and that is your Big-Oh. Selection sort, Bubble sort, and Insertion sort are all methods we had learned in CSC 108, and all have the same Big-Oh of O(n^2). These are the 'simpler' sorting algorithms and use loops to sort through the entire list, which is why they have that efficiency. While their exact equations are not n^2 (they could be something like 5n^2 + n + 27), we round to the highest power because of the fact that at some point, the constants, and even the value of any powers lower than the highest in the equation would become meaningless at very high list sizes. Merge sort, Quick sort, and Timsort however, have a O(n log n). This is because they seem to divide the list up into smaller lists, and divide and sort those. While this sounds scary, it turns out it is much more efficient that the previous three sorting algorithms mentioned.  While O(n^2) might seem inefficient compared to these superior algorithms, it is still in the acceptable range of programs. Programs that run on O(n!), or even O(n^n), are the point where efficiency is compromised, and is deemed unacceptable. 

And on the ninth week of CSC 148 my professor gave to me...

    A week of Big Oh's, efficiency, and sorting algorithms. And a little bit of BST review, but since I talked about that last week, I'm just going to briefly go over it here. A BST is essentially a tree, but organized. The left subtree will always have values less than that of the root, while the right subtree will have values greater than it. Now on to more important things.

    I don't know if this says something about my personality but I love learning about efficiency. Just anything about it, whether it's about why my program being inefficient or about the mathematics of efficiency or just simply how lazy computer scientists are when it comes to accuracy with efficiency. I've always thought that as you go on in CS, you will inevitably start making less and less efficient functions simply because problems will contain more and more unknowns and will be impossible to do efficiently. I was both pleasantly surprised as well as horrified to learn that this was not the case. Factorial and N^N functions are deemed improper in every level of computer science, but occasionally a necessity, depending on the function.

    In addition, while learned in more detail in CSC 165, Big Oh notation seems to fit perfectly into the dogma of of a CS student; being lazy and efficient. You always round down to the lowest Big Oh that fits your function, you always remove the coefficient and put it as a breakpoint instead. At first I thought it was silly to purposefully simply a function to its basest form, but as the examples in class get more and more complicated, I could see why this is a huge time saver (you can find out the efficiency of the function at literally once glance), and why it is used today.

Searching for Linked Lists in Sets of Two

    Okay, I know I didn't put up my blog post about trees this week like I promised, but I'll put it up eventually. In the mean time, we'll talk about Linked Lists!

    A linked list is essentially a tree, but where every single node has only one value, and a pointer pointing to the next node (Also known as the rest of the linked list). Just like recursion, and trees, and all of computer science in general, it was really hard to get my mind around this concept at first. But as time went on, and I read and reprogrammed the code over and over again, it suddenly started making sense. Although this might not make perfect sense, the idea that linked lists are just lists, but instead of being inside of a single list, it is 'wrapped' inside of a wrapper, where it points to other linked lists just didn't make sense to me. But when I started to get the hang of the prepend and decapitate functions of linked lists, it started to become clear

    Now one thing that I'm still having a little issue with is a binary search tree. The concept of binary search is pretty simple; you start off with a term, and to the left are terms that are smaller in value, while to the right are terms that are greater. This gives a much faster search time for finding an object because instead of potentially having to search and entire tree, you can literally ignore half of it depending on if the value you are looking for is greater than or less than the initial value. I don't exactly know what I find confusing about these trees since I have a grasp of what they're supposed to do, but whenever I try to think about them, I can't help but feel as if I'm missing something.

A Recursive Post About Recursion

    In addition, the idea of recursion, while not fully understood, has become a lot clearer to me since I first learned it. The idea that, while defining a function that you can call the function perplexed me. How is something like that possible? Wouldn't that be like just calling the function infinity times? It turns out most of my confusion was that... Wait a minute. Does this sound familiar to you as well? That's probably because it is! Welcome to my recursive post about recursion! The first time I did this was a long time ago, in a galaxy far, far away. And since that time, I have learned so much more about recursion. From the myriad of functions we've programmed together, to classes we've created, all based on recursion, there's one thing I've learned; recursion isn't that complicated.

    It turns out that the thing about recursion that confused me the most was the fact that it was written in list comprehension form. As I have mentioned in previous blog posts, I took CSC108 a LONG time ago(about 1 year to be precise) and didn't learn a thing about list comprehensions. What makes it worse is that I missed the entire first week of class because I was stuck in an airport because of storms happening in Canada, so I am still not sure if we learned it then. However, during a lab, the topic of list comprehensions came up, and low and behold, recursion seems to make sense to me now!

    Recursion itself isn't particularly useful. It's just iterating over a function to keep it going without having to embed a bunch of loops around it. It's two things that I think make recursion useful; the built-in python function, whether it be append, or sum, or max, and the condition that the recursion is occurring against. The reason I neglected to mention a base case is because it's not what makes a recursive function useful; it's what makes a recursive function function (recursively). The built-in function is what provides some sort of work done to the function, whether it sorts things from nested lists, or it just creates a new list of things in a different order, this is what lets your function do what it needs to. The recursive condition, on the other hand, is what lets the know where to go, and prevent it from being an infinite loop. Whether it is a for loop, iterating over the items in a list, or a while loop, letting the function occur over a range of numbers, this is easily the most important part of a recursive function, excluding the recursive function itself. By splitting the function into parts, and understanding each portion, it made it much easier for me to understand.

    However, while I understand how a recursive function works, it still confuses me in its uses. For example, things such as linked lists and trees, which are essentially whole classes based on recursion, aren't clear to me. I understand how the code works, that isn't the problem, I just don't understand where and why I would use them. Why is it better than a nested list? Why do we have a specific instance of a tree, and call it a different thing, even though it is just a tree? It's questions like these that keep me up at night (not really though). Well, that's all I have to say about recursion. See you next week!

P.S. I know I haven't done a blog entry for week 6 yet... mostly because I completely forgot about it. I promise it'll be up by this Tuesday!