Sorting and Efficiency

    The time complexity of a sorting algorithm is correlated to how many steps it has, and how much they are executed based on input. It's possible to find an equation from that information that will give you time depending on input size. If the algorithm is recursive, things get complicated and you have to also consider how many times it will end up calling itself. Once we have this information, it's useful to use things like Big O notation to figure out a limit for how much time the algorithm takes, where, if f(n) is your equation for time taken, f(n) = O(g(n)) if g(n) is some function that, when multiplied by some constant, is always greater than or equal to f(n) as n approaches infinity. For example, if f(n) = 3n^4 + n^2, then f(n) = O(n^4) since, there always exists some constant c where cn^4 >= f(n) for very large n. 

    This can be applied to the sorting algorithms we looked at in class to find out which ones are most efficient, and to figure out ways to improve them. I thought the most interesting contrast was between quick sort and merge sort. At first glance, it seems like they might take a similar amount of time, since they both split the input into two sides. Merge sort works by making a half and half split and then calling a helper function. Meanwhile, quick sort goes through each item individually, placing it behind the original first item if it is less than it, then splits that in half and calls itself recursively on each half. This causes quick sort to run much slower than merge sort since it won't always place items in the correct position before splitting the list in half, so it sometimes does more work than it has to. This is really clear if we look at its worse case scenario, which belongs to O(n^2) while merge sort's is only O(nlogn)

Recursion

    Recursion is when a function calls itself within its definition. This can be very useful in solving complex problems by breaking it up into smaller pieces. For example, if you wanted to count the non-list elements in a nested list, you could write a recursive function that first checks if what it's given is a list. If it isn't a list, the function will add 1 to its return value. If it is a list, the function will put each element of the list through itself again, and repeat the process just illustrated. This function could be written as:

    def non_list(lst):

        return sum([non_list(val) if isinstance(val, list) else 1 for val in lst])

(note: this function only works if the parameter lst is a list)

    The function works by using a list comprehension and repeatedly calling itself until the property of lst not being a list is met. Many recursive functions could also be written using while or for loops. In fact, using that method also uses less memory. However, recursive functions often offer a more elegant solution to the problem. They can also be written without using a list comprehension. For example, the above function could also be written as:

    def non_list(lst):

        nonlst = []

    def counter(lst2):

           if isinstance(lst2, list):

                 for a in lst2:

                     counter(a)

            else:

                 nonlst.append(1)

        counter(lst)

        return sum(nonlst)

    This is considerably bulkier and uses a nested function but works nonetheless. In general, a recursive algorithm should have a base case that it tries to get all of its parameters to approach (in this case the base case is having type(lst) != list) and to do this it keeps calling itself recursively. This works because the recursive function works backwards in a sense by reducing all of its elements to the most basic case and then combining all of the values once they're in that form to give the correct return value.

Week 5

    In labs this week, we had to use recursion on computational problems. At first, the problems were difficult (possibly due to me skipping class this week). Eventually the lab was solved, though our solutions were not the most efficient. Instead of confining all of our code to the return statement and using built in methods such as 'is' and 'isinstance', like in the examples done in class, we coded it the previous way and had to futz with it for quite a while before it started working. We couldn't figure out why the program wouldn't stop once it got the correct value, but would keep recurring and sometimes wouldn't return what we were looking for. After getting home from the lab I took a second look at the class slides and examples, and quickly figured out how to do it with only using code within the return statement (though getting used to the syntax did take a moment). Now, even though the program would keep recurring even after getting the correct value, all return values were stored and the max return value was the one printed. Since max(True, False) = True, putting the code within a max(...) statement would always return the correct statement, since just needed to know if at least one iteration of the function would return True. I'm glad I understand this better now, and will be trying to code everything in this more efficient way from now on.

Reflecting on Object Oriented Programming

    In class we have been working on object oriented programming. I remember when we started this at the end of csc108, I was confused by it (especially with why some methods had underscores surrounding them, what does it mean??) but now I feel I have a good grasp on the technique, and understand the purpose of the __init__ method (among others). Something that does still bother me that I noticed while doing last weeks Exercise is that, if you have a method, 'hop', within class 'Bunny', and you let a = Bunny(), and you call a.hop(), everything is fine. But, if you say something like, a.hop = 'hop', and then try to call a.hop() again, you get an error! It seems like this is because python now associates a.hop with the string 'hop', so when you call a.hop() again, it is substituting 'hop' in, so it thinks you're trying to call a string as a function. However, if you call Bunny.hop(a), it will still work. So, I guess I understand (vaguely) why this happens, but I still find it a bit irritating and inconsistent.
    Also, I don't understand the benefit of writing our function definitions as something like, "def hop(self: 'Bunny') -> None", especially since python red-underlines the "-> None" part. Why are we writing it like this? Me and python agree that it is silly, though I can see how it would be useful if you want to give a variable in the function a set value (such as "def hop(self: 'Bunny', jump = 'yes') ... print(jump) " would print 'yes' if a.hop() was called, or you could say a.hop('no') and it would print 'no'). Anyway, those are my thoughts for the week, so long!