Sorting and Efficiency

Algorithm runtimes are important for large-scale inputs--the larger the input, the bigger the difference between an iteration of a logarithmic algorithm and an exponential algorithm.

Sorting, in programming, is taking a collection of objects and putting them in the order  needed by the function (ascending, descending, etc.).  In particular with Large N inputs, the initial order in which the objects are given will determine how fast (or slow) the algorithm runs.  For most types of algorithms, if the collection is already sorted, it will run faster (less assignment steps); if it is random, it will run slightly longer with the probability that some  things will be in order; if it is reversed, it will run the slowest because it has to re-assign every element of the list.

Here's a synopsis of some of the run times in Big-Oh Notation:

O(1) = constant
examples: a method that's algorithm is independent from the length of the input
why:  the method will always execute a certain number of steps that doesn't involve running the entire list, and thereby doesn't depend on the size of the input to determine its runtime

O(log n) = logarithmic
examples: a binary search three
why: the length of the input will be repeatedly cut in half when the algorithm runs, thus cutting the runtime of each subsequent section down by 50%

O(n) = linear
examples: searching through a list
why: running from one end of the list to the other (in a worst case scenario) searching for something will mean that the loop in the algorithm will iterate n times--where n is the length of the input

O(n^2) = quadratic
examples: comparing elements in a list
why: two loops will have to be written in the algorithm; one will run like the linear version (checking every element of the list), while the inner loop will compare the element from the first loop and compare it to every other element in the list--thus, for every n times the out loops is performed in a worst case, it is run n times with the inner loop.

These deal with the idea of efficiency because you want to create the fastest run time possible as a programmer, while executing exactly what your program is designed to do.  With the different types of Sorting Methods (Bubble, Selection, Insertion, etc.) it is easy to see, just by looking at the code, that there are less and more efficient ways to sort a collection of objects.

For example, Bubble, Selection and Insertion sort all have a "worst case" runtime of O(n^2) because in the worst case scenario, they will have to compare every element in the list with every other element in the list, reassigning everything.

Alternatively, something like Merge Sort has a faster "worst case" runtime of O(n log n), because it breaks the length of the input (n) into smaller subsections and re-orders those, sort of gluing the whole things back together, instead of checking one item across the length of the list.

As was tested in the lab, there are hybrid methods that combine certain techniques to create even faster run times, and with inputs of Large N, the reduction in Big-Oh upper bounds for the runtime will make a significant difference.

Binary Tree to Linked List

This week's lab assignment proved to be quite tricky (my partner and I worked our way through various problems, but never got it working quite perfectly).  While Binary Trees and Linked Lists are similar in function (a root element with up to two children, extending into as many levels as is necessary), it was trickier than anticipated to convert a Binary Tree into a Linked List in the "inorder" traversal.

Our problem was that the recursive algorithm that we wrote worked for a "Standard" sub-tree (one parent, two children), but didn't know what to do with asymmetrical sub-trees and just sort of skipped elements from them.  I'll go back and work through that one to make sure I know how to figure it out.

Our "helper" functions would be called when the "children" were reached (one left helper and one right), and the main return statement would place the sub-tree in the proper Linked List format.  This is why it skipped the elements that weren't symmetrical; if you pass one run of the algorithm where the elements don't match, it's going to try and figure out a way to keep going based on the "if/else" statements you've created.

It's always helpful to know why a program doesn't work the way you want it to.  By identifying the problems, one can create new methods (no pun intended) to either replace or assist the elements that don't work.

Regex vs. Binary Trees

The trickiest difference between Regex Trees and Binary Trees is the Star node, which can only ever take one child.  It means creating a program that can differentiate between one or two children (no blanket recursion).

The Binary Tree will start at a root, and while there may only exist one child per node, there will be a placeholder of a Nonetype that the methods can iterate over or search for to interpret or dissect the Tree itself.  As noted last week, a Binary Tree can be traversed and its order understood and reconstructed if necessary.

The Regex Tree also starts at a root, but the rules for how the Tree can extrapolate are different.  There needs to be a more specific parsing algorithm for each level of leaves, which gets more complex the more nested the level is.  As mentioned in the beginning, the Star Node is the catch in parsing a tree--since Dot and Bar Nodes act much the same way.  In order to make sure an instance is valid, the Star Node must have one child (any other node, which can then continue to branch out).  This means that there is only ever one linear connection through the Star Node.

As an example:

STAR

|

STAR
|

LEAF

 

This creates a single track linear trajectory to the only Leaf from the Root (the first Star Node).

 

As a counterexample, using other types of nodes:

 

DOT

/        \

LEAF       STAR

                |

                LEAF

 

 

BAR

/       \

STAR    DOT

    |         /     \

      L      L      L

 

In order for a program to traverse the tree, it needs to be aware of what node it is looking for, and that will tell the program what to expect as a sub-level (Leaf = no children, Star = one child, Bar or Dot = two children).  This has to be kept in mind as being different from Binary Trees (or Linked Lists) where there will always be a symmetrical search (even if one element is None).

Trees and Linked Lists

Trees and Linked Lists are useful for creating intertwined data structures.  Creating a map of connected elements is both efficient and complicated.  It’s efficient in design, but it requires a very firm understanding in both the elementary ideas of the language (and its functions) as well as the end goal you are trying to achieve.

Trees contain varying type instances as “nodes” or “leaves” in the larger system.  Stemming from a root (so far, a specific integer), each node can contain a certain number of other trees, or None types.  The Trees are often represented as a Linked List (where any subservient Tree is a list inside of the dominant list—which can extend infinite times if need be).  This allows the programmer and the user to find specific information via indexing.

Trees (specifically binary trees) can be analyzed by which route the program takes to read the nodes in the tree (traversals): Pre-Order, In-Order, and Post-Order.

The Pre-Order traversal starts at the root, then travels to the left subtree, and works through the various levels from left to right.

As an example:

ROOT

/    \

A            B

/    \        /    \

C       D    E       F

The Pre-Order Traversal will start at the root (ROOT), then move to the first left node (A), then move to the left subtree (C), and since there is another child, continue to that one (D).  At this point, the left subtree is covered, so it will move to the right subtree (B) and follow the same pattern (adding E and then F).  Altogether, this would layout the Pre-Order Traversal as: [ROOT, A, C, D, B, E, F]

Using the same example, the In-Order Traversal will start at the deepest level on the left side (C), move to its parent (A), and since there is another child on that level continue there (D).  since that subtree is done, it will move up again on the left side, which takes it too the root (ROOT).  Now that the left subtree is done, it will continue to the deepest level on the right subtree, but staying on the left side (E), then it will follow the same pattern as the left side (adding B and then F).  Altogether, this would layout the In-Order Traversal as: [C, A, D, ROOT, E, B, F].

Between the two of these traversals, a unique tree can be constructed and visualized (which results in the Post-Order Traversal—which starts at the deepest level and scrolls the tree left to right for each subtree, resulting in [C, D, A, E, F, B, ROOT].

Recursion

A recursive method is very simply defined as a method that calls itself.  It can be called as assigned to a variable within the function, or as a part of the return statement.
 
Recursive methods are designed to sift through every nested layer of data, gather all the elements, and collect or return the information you're looking for.
For example:  if you wanted to return a list (in any nested structure) with 2 added to every number listed anywhere, you could write a return statement like:
def add2(lst: list) -> None:
... (shortened just for explanation)   
      return ([add2(x) if isinstance(x, list) else x + 2 for x in lst])
 
A sample input of:
a = [1, 2, [3], [4, [5, 6]]]
 
Would return:
[3, 4, [5], [6, [7, 8]]]
when add2(a) is called in the shell.
 
This is a very basic example to show how the recursive function access each element of the inputted parameter.

These functions can return a single quantity as compared to other elements in a nested list, can add up or multiply all the elements in the nested list, can extract/modify/delete any or all elements in the various levels of recursion in the given parameter so that the end result is achieved by only calling the function once.