Sorting and Efficiency:

       One of the most important aspects of programming is efficiency. Efficiency of a program is how fast it can compute, given a large set of data, as compared to another program with a different algorithm. We briefly covered this topic in CSC108, where we learned about efficiency using the sorting mechanisms: bubble sort, selection sort, and insertion sort. The efficiency of these sorting mechanisms (bubble sort, selection sort, and insertion sort) was compared using their big oh definitions, where all three of them were denoted by O(n²). The big oh for these algorithms denotes what happens as the data inputted gets larger but they can be compared as still have advantages and disadvantages when given smaller input size. For example, bubble sort compares two numbers and swaps them if the second number is smaller and continues to take the larger of the two compared throughout the list while comparing with the consecutive number until it places largest number to the back of the list. When it starts back again it makes one less comparison each time. Whereas, in insertion sort it picks the smallest item and places it to the front of the list repeatedly, building a sorted sublist. When comparing bubble sort and insertion sort, insertion sort is slightly better because of the fewer swaps it makes even though the big oh denotes for these two functions is the same.

       
       Recently, we were introduced to three more sorting algorithms, which are merge sort, quick sort and count sort. Since CSC148 hammered recursion into our brains, these sorting techniques also dealt with recursive techniques to provide greater efficiency.

       One of the new techniques we learned is merge sort, where a list is divided into two halves and each piece is “merge-sorted” and this process continues till each list contains only one element. When a list has one or zero elements it is already sorted. These pieces are then merged back together. Since I can’t display the technique using cards as done in class, the following diagram from one of the readings is gives great visualization for understanding the merge sort technique:

© Copyright 2013 Brad Miller, David Ranum

Retrieved from: http://interactivepython.org/courselib/static/pythonds/SortSearch/sorting.html

      The use of recursion in merge sort allows its efficiency to be O(nlogn). Although I wish I had understood why its efficiency is so before writing TT2, there’s no harm explaining it now since I actually understand it. The logn part of big oh comes from the division of the list in halves, which makes sense because as the rate of increase in x values in a logarithmic function increases, the rate of increase in y values decrease. Thus, the number of divisions of the list also decreases as the list is parsed in smaller sublists. The n part of the big oh comes from the merging of each number. In other words, the function merge is called n times because the division of the sublists leads to n lists (as each sublists contains 1 element). Merge sort, in comparison to the sorting techniques learned in CSC108, is much more efficient because O(nlogn) > O(n²).

      The second sorting technique we learned is called Quick sort. Quick sort works by picking a split point, called pivot. Then it makes sublists of items that are smaller than the pivot and larger than the pivot, and recursively solves these sublists till each sublist has less than 2 elements. Just like merge sort, a list is sorted when it contains only one element in it, which is essentially the base case. Below is a diagram that provides a clear example of quick sort:

Retrieved from: http://kehs.ksd.org/Classes/Compsci/Java/WebLessons/ICT%20Version%201.5/WebLessons/APCSL26/APCSL26-1-3.html

Unfortunately, the worst case scenario in quick sort is denoted by O(n²) which is accounted by the choice of pivot which can be the two ends of the list each time, causing n divisions and the processing of each item’s placement in the final sorted list. However, when the pivot is always the middle element the runtime analysis can be O(nlogn), similar to merge sort.

      Lastly, we also looked at count sort in class, which Danny had made up in just a few minutes before class (Wow!). The following is the code for count sort, presented by Danny, since there aren’t any visuals online:

def count_sort(L):
    """silly functional sort.  See radix sort for something serious"""
    count_list = [0, ] * len(L)
    for i in L:
        count_list[i] += 1
     L1 = [] # blank slate!
    for i in range(len(count_list)):
        for j in range(count_list[i]):
            L1.append(i)
    return L1

     
      Although count sort doesn't use recursion, the way that it works is by making an initial list of zeroes, where there are as many zeroes as the number of elements in the list plus 1 extra zero. Then, the original list is iterated over to mutate the index correlating with each item’s value with 1 in the place of zero in the list of zeroes. Lastly, a new list is created to append the values of the index containing 1. Here is an example of a list that goes through count_sort:        count_sort([3,1,2]) à count_list = [0, 0, 0,0]

                                                                      à count_list = [0, 1, 1, 1]

                                                                      à L1 = [1, 2, 3]

#this final list contains the indices of value 1 in count_list

       As evident, this sorting technique would fail if a value of the list was greater than the value of the total length because its corresponding index in count_list will not be incremented by 1, thus leaving its value out. Nevertheless, this sorting mechanism is denoted by O(n) because the actual list is iterated over only once.

       So, these sorting algorithms provide us with a tool for comparing the runtime analysis!

What is Big Oh?

The term big oh is a commonly used when discussing the runtime of a function. For example, if I have a function that takes 10 steps when given an input size of 10, 20 steps for an input size of 20, and so on; then, when given a large arbitrary input size of n, it would take n steps. This function would be denoted as O(n) because the function grows linearly. Therefore, big oh is denotes the runtime of a function. However, the runtime can be different for different inputs. In CSC108, we learned about bubble sort. Here is a code for bubble sort we used in CSC108:

def bubble_sort(L):

    """ Sort the items of L from smallest to largest.  """

    end = len(L) - 1

    while end != 0:

       for i in range(end):

            if L[i] > L[i + 1]:

                L[i], L[i + 1] = L[i + 1], L[i]

        end = end - 1

The algorithm of bubble sort is based on a simple technique, where two consecutive numbers are compared with each other and swapped iff the second number is smaller than the first. This is done for each number in the list, indicating that the runtime of an unsorted list would be O(n²). However, the runtime can be totally different if the list was already sorted (the runtime would be O(1)), which would be the best case scenario. Often the best case scenario doesn’t tell us much, so we look at the worst case scenario, which is when the list is reversed sorted in the bubble sort example. The O(n²) is the worst case runtime for bubble sort, which is useful to know to get an idea about the function’s efficiency (the topic of my next assigned slog post).

Binary Search Tree Example

To continue with the use of the properties of Binary Search Trees. The best example would be a lab exercise that was initially quite challenging but finally clarified many misconceptions about BSTs and left me with in-depth understanding (or at least, that's how I feel)!

For lab 8, we had to write a method called count_less, where given a BST the function returns a sum of all the numbers less than the value at the root. We had to write this method using three different class implementations but the one I present here is the one I struggled with the most.

def count_less(self: '_BSTNode', item: object) -> int:
        """
        Return the number of items in the BST rooted at this node that are
        strictly less than item.
        """
        if self.item:
            if self.left is None and self.right is None:
                if self.item < item:
                    return 1
                else:
                    return 0
            elif self.left is None:
                if self.item < item:
                    return 1
                else:
                    return self.right.count_less(item)
            elif self.right is None:          
                if self.item < item:
                    return self.left.count_less(item) + 1
                else:
                    return self.left.count_less(item)
            else:
                if self.item < item:
                    return self.left.count_less(item) + 1
                else:
                    return self.left.count_less(item) + self.right.count_less(item)
        else:
            return 0

Yes, I know that that my code is really long because of repetition but I am presenting this version instead of a compact one for the sake of clarity as I describe how the property of BST is used when coding this method.

First of, assuming that the class BSTNode is implemented properly, we check if the root of the tree has a value and if it does then we check if it has no children, only left child, only right child or both children. The case where we have no children, the implementation is straight forward. Also, for the case where we have no left child, we are bound to check the right child given the value of the item is more than the value of the root, and vice versa for the case where we have no right child. However, it is interesting to take a look at the else clause because this is where we see the implementation of a BST property. In the else clause, given the value of the item is less than the value of the root, we only do recursion on the left subtree because that is the only place where there could be more values that are less than the value of the item to suffice the purpose of this function.

Binary Search Trees

My last post was definitely not about Binary Search Trees. It was about Binary Trees in general (although I managed to mistakenly write Binary Search Trees). So, I will now explain how a binary search tree is different from a normal binary tree. A normal binary tree is a tree where the root can have two children, left child and right child, just like the example presented in the previous post. There are no restrictions as to what the left and the right child could be. However, in Binary Search Trees (BST), the left child’s value must be smaller than the root while the right child’s value must be greater than the root. Considering that the left and the right child themselves are BST, they would follow the same rule, i.e. their left child’s value must be smaller than itself while the right child’s value must be greater than itself.

Here is an example of a Binary Search Tree:

In this example, we see that 4 is less than 5, hence it is the node of the left subtree; while 7 is greater than 5, hence it is the node of the right subtree. This pattern follows for the left and right subtrees themselves.
It is a common misconception to think that the left subtree of the right child can be smaller than the node. This is because when we add 4 for instance, it *first* checks if 4 is less than the value at the root or not, which it is. Then, *second* it goes and compares 4 to the value of the root of the left subtree. Thus, a value less than the root can never be found in the right subtree. This property often used when searching for a specific number as it number's value and the root's value can be compared to narrow the search, thus doing less work (one of the primary goals of computer scientists)!

Binary Trees and Linked Lists

A binary search tree is essentially a list with a value, representing the node or the parent, which points to its left child and right child. The left child and the right child could be a value or a tree itself, which could have another tree within itself, and so on. It differentiates for an actual tree as its branches grow downwards and it can only have 2 branches since it is binary. When a branch does not further lead to other branches, it ends by pointing to None type objects. An example would be:

T = [5, [4, [3, None, None], [1, None, None]], [2, None, None]] 

A linked list, on the other hand, is basically the same kind of structure as at binary tree but the only difference is that it has only one child. It is also made of a list, which only points to one child instead of a left child and right child. Consequently, the visual representation of the following linked list example is:

L = [5, [4, [3, None]]     

Reflecting on A1 and TT1: List Comprehensions and Recursion Conclusion

After A1, I thought I understood recursion very well. A1 really drilled the tracing technique for recursion into my head. I bet I traced the three stool method and four stool method millions of times! I even found a pattern to the optimal value of i, though it wasn't helpful for any coding. A1 was quite challenging not just because there were harder concepts to be coded, like recursion, but also because figuring out the details about TOAHModel and Tour was tricky. In essence, it was like “fill in the blanks” questions except with huge blanks to be filled in, which made it challenging. Yet, I got through it with proper implementations. However, now that I look back, I realized that I did not use list comprehensions. However, studying for term test 1 helped me practice coding with list comprehensions as well. Moreover, I also realized that I didn’t fully grasp recursion as I thought I did. For example: my first attempt to Winter 2013 test question # 4 was the following:

def rec_len(L):
"""(nested list) -> int
Return the total number of non-list elements within nested list L.
For example, rec_len([1, 'two', [[], [[3]]]]) == 3.
"""
    count = 0
    for item in L:
        if isinstance(item, list):
            rec_len(item)
            count += 1
    return count

Of course, the above solution wouldn't work because the accumulator is overridden every time the function is recursively called. To use this accumulator idea, the variable would have to be a global one. This is where I finally figured the value of list comprehension. My final solution to the above problem was:

    return sum([rec_len(elem) if isinstance(elem,list) else 1 for elem in L])

This list comprehension is accumulating a list to be summed up in the end to find the total number of non-list items, fulfilling the need of an accumulator.

Now that I've practiced this idea and got through the test, I realize the list comprehension is a valuable tool for dealing with recursive functions.

Intro to Recursion

Recursion is one of the hardest concepts I learned so far in Computer Science. It was not hard understanding the concept itself; rather, it was hard accepting its validity when applied to computer programming. In the recursion reading, it was first described in terms of drawing fractals (for visualization), in which a hill-looking bump was drawn from a straight line. This pattern continues to grow for every straight line created by the new edge formed by the hill-looking bump. Therefore, the pattern applies the same strategy of forming the hill-looking bumps for every (new) straight edge as it used when it first started with a straight line. The first fractal from a straight line is called the base case.

    In computer science, the same idea of fractals occurs when a larger problem is broken into smaller tasks, when solving these smaller tasks use the same strategy as solving the larger tasks. The smaller tasks are carried out to complete the larger task till the base case is reached, which is the initial strategy used to solve the problem. In fact, the idea of recursion fits in well with mathematical induction. In CSC165, we had written proofs to prove a certain mathematical statement using induction, where a base case proved the statement using an example and then the statement was proved using arbitrary values, n and n+1. The use of two consecutive arbitrary values’ proof signifies the key feature about recursion, which is that the strategy used to solve the larger problem, is the same as the strategy used solve the smaller tasks needed to solve the problem.

    Although I understand recursion better now and I am able to apply it to mathematical induction, I hope that after finishing the assignment 1 and some other practices, I can understand it’s applicability in different data structures.