Week 11: Sorting and Efficiency

    Even in 108, we were advised to think about efficiency in our functions, and we learned about some sorting algorithms. We looked at for-loops, and for-loops within for-loops that caused the program to make linear and quadratic amounts of steps, respectively. In 148, we were given a more expansive hierarchy of function efficiency, determined by running time analysis for an input of size n. Here it is:

constant:                  c (a number in the range of positive rational numbers)
logarithmic:              clogn                       eg, binary search
linear:                      cn                            eg, linear search
quadratic, cubic, etc:  cn^2, cn^3, ...
exponential:              c2^n                        eg, tower of hanoi
horrible:                   cn^n or cn!

    In the same lecture, we were refreshed on big-oh notation from 165. To understand big-oh, you need to first understand worst case scenarios and break-points. big-oh always considers the worst case scenario (the longest possible time it will take to complete the function) of a function of a given running time analysis. For example, O(n) means the worst case scenario for a function of running time analysis n

    When comparing big-ohs to other big-ohs, you need to consider a break-point. A break point is a certain size of input where one function is no longer taking more time at it's worst case scenario than the other function. Also, if one function always has a longer running time analysis than the other, then the certain break-point is considered to be 0. For example,

O(n) is a subset of O(n^2)

Means that at a certain break-point, the worst case scenario for a function of running time analysis of n^2 is worse than that of one of running time analysis of n for all sizes n that are larger or equal to the break-point. I know it's a wordy definition, but after a couple of visualizations, it's not a difficult concept to understand.

    Running time analysis is always the focal point when creating an efficient sorting algorithm. In 108, we already learned about some less-than-stellar sorting algorithms, mainly bubble sort, selection sort, and insertion sort. Now, we're learning about quick sort, merge sort, count sort, and tim-sort (tim-sort is python's built-in sort function).

    Quick sort is the first of these sorting algorithms we learned. It works like this:
    1) Choose a pivot (preferably at random)
    2) Check every element besides the pivot. If the element is less than the pivot, it goes into list L1
        If the element is more than or equal to the pivot, it goes into list L2.
    3) return L1 sorted by quick_sort, concatenated with the pivot, concatenated with L2 sorted by                 quick_sort.
A pivot is chosen randomly to help ensure the largest or smallest element doesn't get chosen. That way, there is less chance of going recursively into only one list that simply excludes our pivot. That would make the function much less efficient.
    When running through these steps, it's important to remember that a list of 1 or 0 is considered sorted. That is the base case for this sorting algorithm, and for the following one.

    Merge sort is the second of these sorting algorithms we learned. It works like this:
    1) Cut the list roughly in half.
    2) merge_sort each half.
    3) merge those halves together.
Two functions are happening here: merge_sort and merge. merge is important because it's often needed to make sure that the list that combines the two sorted lists [0, 2] and [1] is also sorted, as list [0, 1, 2] instead of [0, 2, 1]. merge_sort basically breaks down the list into many halves-of-halves-etc. until it's entirely lists of length 0 or 1, and then they are all merged together properly with merge.
    Thanks to the clever use of recursion, these two sorting algorithms have a logarithmic running time analysis, meanwhile sorting algorithms learned in 108 had a quadratic running time analysis. That's an incredible difference in sorting efficiency!

Never use mutable objects for default parameters

    I learned something very curious in a lecture recently. This:

def f(n: int, L: list=[]) -> list:
    L.append(n)
    return L

will produce the following in the shell:

>>> f(7)
[7]
>>> f(17)
[7, 17]

In the second command, what the coder would probably expect is[17] to be returned, not [7, 17]. That's because there includes the default parameter L which should create an empty list to append to, right?
    The only important thing that Danny wanted us to learn is to NEVER USE MUTABLE OBJECTS FOR DEFAULT PARAMETERS. He then explained the reason is because L is stored as an object within f.__defaults__, and it is used at every function call. I'm still confused by this. If a default parameter is stored and used at each function call, why doesn't this happen with non-mutable objects like ints and strings? What is it about mutable objects that allow this weird behavior?
    I made a second example of this function and showed it to Danny. Here it is:

def g(n:int, r:int=0) -> int:
    r += n
    return r

I asked Danny to explain a critical difference between functions f and g that change the behavior of the two functions. If I remember correctly, he stressed that r += n is a reassignment to an object while L.append(n) is a modification. I think all that means is that reassignments change the value that r points to, while a modification changes the properties of L. Despite thinking this way, I still don't see why a mutable object would be treated any differently when it comes to behavior around default parameters. That's as far as I managed to dig, but I can't spend too much time thinking about this.

My understanding of BSTs + things

    I already explained Trees. Binary Search Trees (BSTs) are just like Trees, except there is one more rule applied when appending nodes to the Tree:

When appending nodes to the tree, if the value of the node is (less/more) than the value of the root, then append the node to the (left/right) subtree. If the (left/right) subtree doesn't exist, then the node in question becomes the root of a new (left/right) subtree.

    This rule makes BSTs much nicer to work with then regular trees. Since BSTs have this rule when they're being created, they have properties that can make your methods and functions much more effecient. For example, they allow your searches to become binary searches, since the values in in-order traversal is now in perfect ascending order.

    This is pretty much everything I know about BSTs, but I know that there is more to them than that. All of the BSTs that we've worked with in class and in labs are designed in a different way. They seem to use two different classes: The BST class, and the BST Node class. I never took the time to figure out exactly what each class is supposed to do and what properties they're supposed to hold. Because of this, I suffered during lab 8 when we had to design functions that required full understanding of these 2 classes.

    It's my SLOG and I'll cry if I want to. Besides my trouble with BSTs, I've been experiencing woes in a few other parts of this course so far. I got 0 on the last question in the first term test, and I lost my test once it was returned to me. Since I can't compare the correct answer to my answer, that's enough reasoning for the emotional part of my brain to decide not to look up how to properly answer the question. I submitted e3 early and the autograder returned 3 failures and 1 success. The autograder says things about AssertionError. What is that? I finished 3 of the 4 required functions for A2PII. The 3 ones I finished work perfectly to me, but are pretty messy. I drove myself crazy yesterday trying to map out on paper how to properly write the body for all_regex_permutations(s). 

    I should see if spending time at the CS help center or getting another peer tutor like last semester would help.