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.

Week 7: Recursion

    Recursion is a programming strategy, and a major topic in this course. It makes the functions of computer programs a ton more efficient, but it takes more sophisticated thinking to write. All recursion really is, is including a function call of itself within the body of a function. For example, having a line in the function f(x) that calls f(x-1). It sounds pretty simple, but there's a lot of guidelines to consider when making a recursive call or else you will lead to bugs and errors.

    First off, you must include a base case. Your function won't stop running if there isn't a set point to reach. Recursive functions are meant to break down a task into smaller versions of the same task, until it can't be broken down anymore. The point where the task can no longer be broken down is called the base case. I'll take an example of one we used in class, modified so the body isn't a single line, just to make it easier to read.

def preorder(tl: 'TreeList') -> list:
    """
    Return list of values in tl in preorder

    >>> preorder([5, [4, None, None], [3, [2, None, None], [1,                       None, None]]])
    [5, 4, 3, 2, 1]
    """
    if tl is None:
        return []
    else:
        return ([tl[0]] + preorder(tl[1]) + preorder(tl[2]))

In case you haven't noticed, this is the pre-order traversal I explained in my last post, now as a python function. In the end of that post, I explained that a tree can be represented as a list of [int, Tree or None, Tree or None] I also mentioned a simple recursive 3-step approach to doing all pre-order traversals. All three steps of that approach are expressed in the else statement above. The if statement is our base case. This is the non-recursive action that the program makes when the problem has been broken down as far as it should go. t1 is None translates to the root / child node not existing, therefore adding nothing to the resulting list that represents the pre-order traversal.

    Recursion can get much more complicated than this. To make good use of recursion, you need lots of practice with writing different function bodies to develop a good sense of what actions can work recursively, and what actions should be part of the base case. A more complicated example of recursion is in a function learned in class that writes the steps to solving the Towers of Hanoi game with 3 stools, in the least steps possible. That function involved breaking down the game into 3 smaller recursive steps:

1) Move all rings except bottom to intermediate stool.

2) Move bottom ring to destination stool.

3) Move all rings except bottom to destination stool.

When you begin step one, all three steps are used again just to complete step one. That means the second-to-bottom ring is used as the bottom ring when step 2 is called during the process of completing step 1. Also, that second-to-bottom ring will be taken to the overall intermediate stool. Every function call changes what the source, destination, and intermediate stools are, to make sure the function still works. When enough rings are involved in this game, the game can be broken down to the point where the (third, fourth, fifth, etc.)-to-bottom ring is used as the bottom ring. This is recursive to the point where there is only one ring above the "bottom" ring, and that ring is simply taken to whatever the current intermediate stool may be.

    In Assignment 1, I invented my own set of recursive steps for a function that completes the Towers of Hanoi game with 4 stools, using the same ideas. It was very efficient and it broke the game down into 5 smaller recursive steps:

1) Move all rings except the bottom two to i1 (since there are 4 stools, the two intermediates are labeled i1 and i2)

2) Move second-to-bottom ring to i2

3) Move bottom ring to destination

4) Move second-to-bottom ring to destination

5) Move all rings except the bottom two to destination

My function looks like this in python:

def fourD_m_c(n, source, inter1, inter2, dest):
    if n == 2:
        print("Move top cheese from {} to {}".format(source, inter1))
        print("Move top cheese from {} to {}".format(source, dest))
        print("Move top cheese from {} to {}".format(inter1, dest))
    elif n > 2:
        fourD_m_c(n - 2, source, inter2, dest, inter1) #all but bottom 2
        fourD_m_c(1, source, inter1, dest, inter2) #second to bottom
        fourD_m_c(1, source, inter1, inter2, dest) #bottom
        fourD_m_c(1, inter2, source, inter1, dest) #second to bottom
        fourD_m_c(n - 2, inter1, source, inter2, dest) #all but bottom 2
    else:
        print("Move top cheese from {} to {}".format(source, dest))

    The words ring and cheese can be used interchangeably. The five steps I explained before are expressed under the elif n > 2 statement. The else statement is the base case, and I still haven't at all explained the purpose of the body of code below the if n == 2 statement. This is sort of like a second base case and this was necessary because my 5 steps don't know how to handle the game when the bottom two rings are in fact all of the rings involved in the game. Therefore, the purpose of this body of code is to manually move those two rings when the situation arises. This body of code is only ever reached when the overall game involves an even number of rings. When the overall game involves an odd number of rings, the game is never broken down into smaller games that involve exactly 2 rings, so this body won't be needed or used.

    My function completed the 4-stool game in less steps than the function given in our lecture. I was proud of my function, but my assignment partner discovered an even more efficient function, and that function was submitted instead :<

Data Trees

    Data Trees are a type of structure to store information in, and we learned about these in class. You can view them visually like this:

    A tree is a series of nodes that have a very strict pattern structure. But first, here are some terms:
Parent: A node that points to another node, and  (Nodes 3, 5, 1, 9, and 7 above are parents.)
Siblings: Nodes with the same parent. (Nodes 5 and 1 are siblings.)
Root: A node with no parents. (Node 3 is a root.)
Leaf: A node with no children, and isn't actually considered a node. (3, 2, and 8 are leaves)
Internal node: A term that includes nodes and roots. Every part of a tree is either an internal node or a leaf.
Arity: A property of a tree that determines the maximum amount of children nodes in the tree may have. (The arity of the tree above is 2.)
Path: A path of nodes that are connected by the arrows (3, 1, 7, 2 is a path)
Tree Length: A property for a tree determined by the length of the longest path. (3, 1, 7, 2 is one of the longest paths in the tree, it's path length is 3 so the tree length is 3.)

Here are some rules:
- Every non-root node has exactly one parent.
- No cycles. A path on a tree cannot lead to an earlier node.

    Thanks to these rules, you can isolate an internal node and all of it's paths, and you have another tree that follows the same rules! This new tree is called a subtree. I wouldn't know for sure, but I think this is might be a very valuable trait for trees and this is why we learn about them.

    There are also different ways to traverse (read all of the internal nodes and leafs) a tree, including pre-order traversal, in-order traversal, and post-order traversal. They are all difficult to understand at first, so I started by studying the recursive-style definitions for each one that were given in the slides in class:

pre-order traversal: Visit root, then pre-order left subtree, then pre-order right subtree.
in-order traversal: Visit in-order left subtree, then root, then in-order right subtree.
post-order traversal: Visit post-order left subtree, then post-order right subtree, then root.

This is pre-order traversal. It goes 3, 5, 6, 9, 4, 1, 7, 2, 8. I'll remember it quickly by taking note of the following:

Pre-order traversal:
1) root
2) left (in pre-order)
3) right (in pre-order)

This is in-order traversal. It goes 6, 5, 4, 9, 3, 1, 2, 7, 8. Notice the unnecessary detours in the blue line after 9 and before 1. They are to illustrate that if there was a second child from 9 or 1, they would've been visited before the next one on the traversal.

In-order traversal:
1) left (in in-order)
2) root
3) right (in in-order)

This is post-order traversal. It goes 6, 4, 9, 5, 2, 8, 7, 1, 3. Notice the unnecessary detours in the purple line after 9 and before 1. They are to illustrate that if there was a second child from 9 or 1, they would've been visited before the next one on the traversal.

Post-order traversal:
1) left (in post-order)
2) right (in post-order)
3) root

You can also write recursive functions in python for all of these traversals when trees are defined as a list of [int, tree or none, tree or none]. the int in place 0 is the node, the tree in place 1 is the left child, and the tree in place 2 is the right child. If there is None instead of the tree, than there is no child.

how python searches for names

    Last week, I learned how python searches for names. Python programs call variable names all the time. Things can get confusing when the same name is used in different places of the same code to define different things. This is why python searches for names in a particular order:

-First, it searches for a local variable name (a variable usually defined within the same function as the call)
-Second, if there is no local variable name, it searches for a nonlocal variable (a variable defined not within the same function as the call, but instead defined in a larger function that includes the function with the call)
-Third, if there is no nonlocal variable name, it searches for a global variable (found on module level or under __main__)
-Finally, if there is no global variable name, it looks for any built-in python names

    I prepared an example of python code where this order comes into play:

vari = "spam0"

def my_scope_test():
    vari = "spam1"
    def inner_function1():
        global vari
        vari = "spam2"
        print("inner function1() searches for:", vari)
    
    inner_function1()
    def inner_function2():
        print("inner_function2() searches for:", vari)
        
    inner_function2()
    print("my_scope_test() searches for:  ", vari)

my_scope_test()
print("the module level searches for: ", vari)


When this code runs: here is what is printed:

inner function1() searches for: spam2
inner_function2() searches for: spam1
my_scope_test() searches for:   spam1
the module level searches for:  spam2

The variable named "vari" is defined three times: First at the module level, second within a function, and third within an inner function, but with a global assignment. (That makes the definition as if it were made in the module level, and how it would be defined without the global assignment) In the same order, these definitions at different points in the code are considered global, local/nonlocal, and global/local. The variations depend on which stage in the code execution these variables are called. I will now walk you through python's thought process for each name search:

inner_function1() needs to find vari to use for it's print statement.
Step 1: local variable name? Yes!
So it uses the variable definition within inner_function1() for the print statement.

inner_function2() needs to find vari to use for it's print statement.
Step 1: local variable name? No
Step 2: nonlocal variable name? Yes!
So it uses the variable definition within the overlapping function my_scope_test() for the print statement.

my_scope_test() needs to find vari to use for it's print statement.
Step 1: local variable name? Yes!
So it uses the variable definition within my_scope_test() for the print statement.

the module level needs to find vari to use for it's print statement.
Step 1: local variable name? Yes!
The module level's local variable names are the global variable names. The global definition for vari has been written twice, so it uses the latest definition, which occured when inner_function1() ran.

    Later in this same lecture when I learned all of this, it was demonstrated that this kind of logic also occurs when working with classes and methods, instead of what we just did with functions. Python looks for methods in the class before looking for methods in the superclass. This order of searching for methods in class and superclasses is called inhertance, which is very similar to the all the name searching I just wrote about.
    That's everything I know about name searching, I might make another post about Assignment 1 after it's finished and after the due date has passed.

exercise 2 finished + what I learned + things

    Exercise 2, at least to me, was about practicing making our own error messages. It was very straightforward, but before starting with this exercise, I needed some help from a friend to teach me some new python commands and concepts that I didn't learn in CSC108 (or in class either, because I wasn't paying close enough attention):

-Every error message you get in python comes from a built-in class called 'Exception'.

This is important for making your own customized error messages, because in order for those customized messages to work like any other error message, you must make a new subclass of Exception. 

-The command 'raise'.

raise is needed for when you want to call a class. If I wanted to call a subclass Customized_error that I made to display my customized error message, I would write the following line in my code:

raise Customized_error("customized error message")

-The commands 'try' and 'except'.

'try' is used for when you want to run a function to see if an error is caused, but not return what the function is supposed to return. 'except' is to be written after try, then followed by the name of an error class or subclass. If that error class or subclass is reached during the call of the function, the line acts very similar to an if statement that returns True, and the program then decides to run the code that is written within the indent of this 'except' line.

    This was basically everything I needed to learn in order to finish the exercise. Other than that, my new time slot on Monday-Wednesday mornings is working out much nicer for me, but I've lately been giving more attention to my other courses. This will probably change I hope. Yes.