Week11: Sorting and Efficiency

This week we learned some sorting methods. It is important to understand how the sorting algorithm processes and also to examine their efficiency. Having a timesaving and efficient implementation is significantly important for computer science. As the workload(size) is often large, so what we concern about is how it scales, and how the algorithm will behave(processing time) when the input size really large.

We use asymptotic analysis to describe limiting behavior. When an implementation of an algorithm(size n) runs cg(n) steps(c is a positive real number) we express the algorithm by big-O i.e. O(g(n)). Big-oh is also upper bounded, which means the algorithm has a limit on how it behaves(its growth rate). For example, O(n) is linear and it will never exceed cn. Also, when the size n get very large, the difference of time complexity approaches infinity. Therefore, the efficiency of algorithms really matters.

constant: O(1)

logarithmic: O(log n)
linear: O(n)
quadratic: O(n2 )
cubic: O(n3 )
exponential: O(2n)
horrible: O(nn) or O(n!)

We will examine some common sorting algorithms, and compare their time complexity.  First of all, the bubble sort is very inefficient, because items are exchanged before reaching their final position. For a size n list, in the first pass, there is n - 1 comparisons; the second pass has n - 2 comparisons. There are n-1 passes, and its time complexity would be n-1 + n-2 + ... + 1 = n(n - 1)/2, and therefore it runs in time O(n^2). Secondly, for the insertion sort, it always have a sorted list from the first item to where we currently implement with, and the next item is inserted in the sorted list by comparing it with previous element. The time complexity is O(n^2) as well. Thirdly, the algorithm for selection sort is 1) find the minimum element though the list; 2) exchange only once, to its proper position; 3) find the minimum element in the remaining unsorted list; 4) and so on. Its time complexity is still O(n^2) but it is slight more efficient. These are sorting methods we have learned in CSC108. They all require O(n^2) running time.

We learned some new methods of sorting: merge sort, quick sort, and they are more efficient.

def merge(L1, L2):
    """return merge of L1 and L2

    >>> merge([1, 3, 5], [2, 4, 6])
    [1, 2, 3, 4, 5, 6]
    >>> merge([1, 2, 3], [0, 4, 5])
    [0, 1, 2, 3, 4, 5]
    >>> merge([0], [1, 2, 3, 4])
    [0, 1, 2, 3, 4]
    """
    L = []
    i1, i2 = 0, 0
#    every slice is a (linear) copy!
#    while L1[i1:] and L2[i2:]:
    while i1 < len(L1) and i2 < len(L2):
        if L1[i1] < L2[i2]:
            L.append(L1[i1])
            i1 += 1
        else:
            L.append(L2[i2])
            i2 += 1
    return L + L1[i1:] + L2[i2:]

def merge_sort(L):
    """Produce copy of L in non-decreasing order

    >>> merge_sort([1, 5, 3, 4, 2])
    [1, 2, 3, 4, 5]
    >>> L = list(range(20))
    >>> shuffle(L)
    >>> merge_sort(L) == list(range(20))
    True
    """
    if len(L) < 2 :
        return L[:]
    else :
        return merge(merge_sort(L[:len(L)//2]), merge_sort(L[len(L)//2:]))

As we can see in the code, merge_sort is a wrapper, and calls its helper function merge. What merge does is returning a sorted list which comes from two sorted list. In merge_sort, the process is: 1) it divides list into halves until the length of sublist is less than 2(recursively: merge_sort); 2) merge the halves (recursively: merge); 3) return the merged list. Noticed that we split the list by O(n) times, and each time cost O(log n) steps. Therefore, merge sort runs in time O(n log n). Next, we will see how quick sort runs.

def quick(L: list) -> list:
    """Produce a sorted version of L

    >>> quick([2, 1, 3])
    [1, 2, 3]
    """
    if len(L) < 2:
        return L[:]
    else:
        # i = randint(0, len(L) - 1)
        i = 0
        return (quick([x for x in L if x < L[i]]) +
                [L[i]] +
                quick([x for x in (L[0:i] + L[i+1:]) if x >= L[i]]))

Quick sort is another efficient sorting method. It is implemented by 1) choose a pivot element; 2) split the list to two parts, one is all less than the pivot(left), the other is all greater than the pivot(right); 3) quick sort the left and right (recursively: quick). Finally all elements in the list are sorted. For its time complexity, the times we find the pivot is O(n), and if the pivot appear about the middle of the list, we can split the list in half, thus the number of steps for each time is O(log n). Therefore, its average time complexity is O(n log n). Nevertheless, in the worst case, when the pivot is the largest or the smallest element, the list divides into a list of 0 elements and a list of n-1 elements, then we will have n-1 + n-2 +... + 1 running time, thus its time complexity is O(n^2).

Furthermore, there is a more efficient sorting method, which is python's built-in sort (timsort). Its time complexity is O(n). It seems like it combines many sort methods and is implemented depend on the list's size, randomness, run length, etc. Timsort is amazing and abstract for me. Above all, sorting is very important and basic, and is frequently used in computer science, and we should really focused on its efficiency, as "Time lost is never found again - Benjamin Franklin".

Thanks for reading!!

Revision:
Thank for Weidong An's correction, I made a mistake on second last paragraph. 
Timsort's time complexity in the worst case and average case is O(n log n), and only in the best case is O(n).

Week10: Abstract Data Type

The thing I found hard is abstract data type, and also the ADT stack. However, I noticed I have not throughly talked about it yet. Thus, I decide to do some review on it.

First of all, we need to understand what is ADT. ADT is an abstract data type, it is defined by a set of operations(what it does), but without saying how they are implemented. Thus it seems abstract, and makes us wonder, if it cannot be implemented, then why it is useful. The fact is we can but we sometimes do not need to come up with methods and give specific implementation of the method at the same time. If the procedure is separated, then the task is simpler and clearer. Also, some well-known ADT can be used frequently by many people, and similarly, an algorithm can be used in many implementations. Next, there are two unfamiliar words distinguish the "idea of operations" and "implementations of operation". The first one is called the provider, the second one is called the implementor. The division of the work accelerates our process in programming. Another word is "interface", which means a set of operations that define an ADT.

One ADT we have talked for a lot of times is Stack. It consists of four operations: 1) __init__; 2) push; 3) pop; 4) is_empty. The implementation of them is called veneer, because it is very easy and using existing methods. One more thing to indicate, stack has LIFO("Last In, First Out") structure.

Here is how stack is implemented.

class Stack: def __init__(self): self.items = [] def push(self, item): self.items.append(item) def pop(self): return self.items.pop() def is_empty(self): return (self.items == [])

(Source: http://openbookproject.net/thinkcs/python/english3e/stacks.html)

Thanks for reading!!

Week9: Binary Search Tree

Hi! We learned more about Binary Search Tree this week. It is a sorted binary tree, and it is consisting of BSTNode. We also reviewed some sorting functions we have learned in CSC108 i.e. selection sort, insertion sort and bubble sort, and we examined their running time. They are relatively long.

First of all, we have a delete method for BST class and its helper function _delete. The most difficult part for me is to understand what we should do after we find the node we want to delete, when the node has two children. Usually we expect something like it is replaced by either node.left or node.right, and everything just move one step forward and the size decreases by one. Stack and some LinkedList work at that way. However, as we all noticed, the structure of the binary search tree will crash when it has more than two children. Also, we need to ensure node.left is smaller than the node and the node is smaller than node.right. Hence, we find the node with the largest value in node.left and it satisfies the properties of BST.  Moreover, I am thinking about whether we can replace the node by the smallest node in node.right; that seems work too.

As for the running time analysis, BST is sorted, therefore if we want to search a certain data, we can always decide to search either left subtree(smaller than data) or right subtree(larger than data), and the other is ignored. Thus if it is a well-balanced tree with size n, the expected running time will be O(lg(n)) which is the average running time. This is because what we are doing for searching is divide n in half until the exact value is reached, so the number of times is log2 n (2^x = n => x = log2 n ). However, in the worst case i.e. there is only left children or right children, the running time is O(n).

I need to keep working on searching and sorting. There are a lot of ways to do and we shall compare their efficiency in terms of its size n, and its running time when n is significantly large(as n approaches infinity). Thanks for reading and it will be great to receive your comments:)

Week8: Linked List

This week we are introduced to LinkedList, and again it is new and abstract. It has recursive structure. There are two ways to interpret it:

1. The list that made by two parts (1) the value or item; (2) the remaining list or rest;
2. A node or object that has a reference and a value. The reference and value are nodes as well.

In order to understand these concepts better, first we need to know what wrapper and helper are and how they work. Wrappers and helpers increase the clarity of our code, and also they are easier to come up with. For example I wrote a function that will capitalize the word:

def capitalized(word: str) -> str:
      return word.upper()

However, I want to add an explanation in front of my capitalized word. Instead of modifying my original function, I can write a wrapper function:

def capitalized_word(word: str) -> str:
      w = capitalized(word)
      return 'The word I capitalized: ' + w

Inside the wrapper function capitalized_word, capitalized is called directly as a helper function. This is a simple example, and we can just combine these two functions. However, if the case become complex, such as the LinkedList and LListNode, wrappers and helpers become necessary. LinkedList(the wrapper class) is considered as a collection of LListNode(the helper class), therefore it can be decomposed in some sense, and invokes the method of LListNode directly.

Next, we are going to examine methods applied in LinkedList. There are three methods taught in lecture: insert, delete_front, and reverse. Notice that LinkedList is first-in, first-out, therefore, we add object in front of LinkedList. The idea here is create a LListNode that has its next node refers to the LinkedList. When we delete an object, we delete the front LListNode. We implement it by replacing the front node with its next node. Moreover, reversing LinkedList is a bit more complex, so the helper function does the work of reversing LListNode, and the front node is replaced with the reversed LListNode. In addition, the pair of BST(wrapper class) and BTNode(helper class) are similar to LinkedList and LListNode. BST seems more effective in the aspect of storing values. Its nodes are ordered like nodes within a Tree.

Thus, getting familiar with properties and methods of Linked List is not enough for doing well on the course. I really need to practice on more codes and get a deeper understanding on what else it can do. Hope it works~

Finally, thanks for reading my slog and welcome the discussion:)

Week7: Recursion

    We have talked about Recursion through past weeks. This is a main new thing in CSC148 and it has brought lots of difficulties to me. It is not hard to understand; we can trace it through the general cases who ends by a base case, and then we can add them up to see the result.  However, a complex recursive function is hard to come up with.

    A function calls itself recursively is a recursive function. "Recursive" is totally different from "circular" which brought infinite loops. Therefore, I usually start with a simple base case who can stop the recursive function by returning something. Next, I write general cases by calling the function itself; at that time, we can either return final result or accumulate each one. The cases are separated by if statements as the whole function is operated once again, whereas in CSC108, we use while loop to stop repetition as codes run inside the function. Moreover, we always need to check the correctness and even the error of our recursive functions through paper and pencils because we are thinking them based on our understanding on what should our function do in various examples. It is acceptable for me to construct a basic structure of a recursive function at the beginning, and then revise to make it closer and closer to the correct answer. The reason of doing this is it is much easier to trace a recursive function to find out what I have missed than to think about some codes recursively which might start or end at nowhere.

    Recursive functions simplify our codes regards to its efficiency(a function can be used for as many times as you want). We would write recursive function when we can find some patterns from short examples to longer examples. In fact it turns out to be operating same things over and over until the base case is touched, such as it becomes empty. Also, they are good at showing the idea of how the function would run based on the previous step. Therefore, the recursive function only need relatively short codes within a function. Thus, practicing more on recursion is necessary for me as it is hard and important which requires thinking deeply, and I believe it would helps programming a lot!

Week6: Trees

    This week we are introduced to Trees. They have unique properties so that they can build expressions and even make wise "animal tree".

     The tree is similar to linked lists. Start with terminologies, it consists of nodes(the top one is root). The paths between parent and children are called edges; the length of edges is the number of edges. Height is the maximum path length from the leaf(the node that has no children) to root. Likewise, the level of the tree is all the nodes that have same distance to root. The last fancy word is arty or branching factor, which means the maximum children within any node. 

 
    There are basically three ways of traversal for tree expression. They are pre-order(prefix) traversal, in-order(infix) traversal and post-order(postfix) traversal. As we want to print the contents of a tree in specific order, we need to write up functions. For a binary tree, the followings are the examples of the three different orders.

def print_tree(tree):
    if tree is None: return
    print(tree.cargo, end=" ") #cargo is the value
    print_tree(tree.left)
    print_tree(tree.right)

def print_tree_postorder(tree):
    if tree is None: return
    print_tree_postorder(tree.left)
    print_tree_postorder(tree.right)
    print(tree.cargo, end=" ")

def print_tree_inorder(tree):
    if tree is None: return
    print_tree_inorder(tree.left)
    print(tree.cargo, end=" ")
    print_tree_inorder(tree.right)

    The key for pre-order traversal is always print root(cargo) of a TreeList at first and then go into the left subtree which is a recursive call, and print its cargo and the left subtree of it until the tree is None, it exit and return to previous call to execute "print_tree(tree.right)" which is another similar recursive call. In a general view, it will print the root, the entire left subtree and the entire right subtree. For post-order traversal, it print from the left subtree to right subtree, and finally root. Obviously, the in-order traversal prints in an order of left subtree, root and right subtree. These different traversal make Tree neat, functional and well-organized.

    On the other hand, we are learning how to build an expression tree. By giving with a list of string which a mathematical operation expression, we rearranged them in an ordered way according to different priorities of operations. It is important to consider multiplying, addiction, and even parentheses. Another thing to remind, to avoid python quit unexpectedly, we would better write exceptions to raise error.

    Last but not least, the animal tree is something that I found like an interesting and cute game. After the training by ourselves, it learns new knowledge. I would like to put the long code below for appreciation.

def yes(ques):
    ans = input(ques).lower()
    return ans[0] == "y"

def animal():
    # Start with a singleton
    root = Tree("bird")

    # Loop until the user quits
    while True:
        print()
        if not yes("Are you thinking of an animal? "): break

        # Walk the tree
        tree = root
        while tree.left is not None:
            prompt = tree.cargo + "? "
            if yes(prompt):
                tree = tree.right
            else:
                tree = tree.left

        # Make a guess
        guess = tree.cargo
        prompt = "Is it a " + guess + "? "
        if yes(prompt):
            print("I rule!")
            continue

        # Get new information
        prompt  = "What is the animal's name? "
        animal  = input(prompt)
        prompt  = "What question would distinguish a {0} from a {1}? "
        question = input(prompt.format(animal, guess))

        # Add new information to the tree
        tree.cargo = question
        prompt = "If the animal were {0} the answer would be? "
        if yes(prompt.format(animal)):
            tree.left = Tree(guess)
            tree.right = Tree(animal)
        else:
            tree.left = Tree(animal)
            tree.right = Tree(guess)

(from: http://openbookproject.net/thinkcs/python/english3e/trees.html)

    The part I found difficult to understand is that only the leaf refers to an animal, and the other nodes actually contain questions. The function has multiple levels for completion which eventually creates someone we can communicate with.

    Keep working and hope everything runs smoothly(especially my code)!!

Week5: Tower of Hanoi, Scopes and Namespaces

    Start working with Assignment 1, it actually requires lots of thinking and efforts. The main purpose of this assignment is about moving cheeses on stools and also to find the minimum steps. Furthermore, it is involved in recursion and I think that is the most difficult part.   

    The code below reveals how to move cheeses on three stools:

def move_cheeses(n: int, source: int, intermediate: int,
                 destination: int) -> None:
    """Print moves to get n cheeses from source to destination, possibly using intermediate"""
    if n > 1:
        move_cheeses(n - 1, source, destination, intermediate)
        move_cheeses(1, source, intermediate, destination)
        move_cheeses(n -1, intermediate, source, destination)
    else: # just one cheese --- no recursion required!
        print("Move top cheese from {} to {}".format(source, destination))

    As we have practiced so far, it has a base case which print "move top cheese from source to destination", and after tracing the general case, the function ultimately will print every steps it used of moving cheeses from the first stool to the last stool. What the general case does is moving all but the bottom cheese from the source(1st) stool to the intermediate(2ed) stool and having destination(3rd) stool as intermediate stool; it is recursive. Next, move the bottom cheese from the source(1st) stool to the destination(3rd) stool; it is not recursive as n is not greater than 1. Lastly, move all the cheese on the intermediate stool to the destination, using the source(1st) stool as intermediate stool; it is recursive. 

    In our assignment, we need to move between four stools. This would greatly reduced the move steps because not like moving between three stools we have one intermediate stool now we have two. Therefore, to find how many cheeses will be moved in the first place in order to get minimum number of moves became a big challenge. Works on them really help me get better understanding on programming.

    Other things I found hard to understand are scopes and namespaces. They are new and abstract concept for me. According to the notes online, a namespace is "mapping from names to objects", such as built-in names, global names and local names, and each of them are created at different stages and have different lifetimes. Another important fact to notice is the local namespace is created when the function is called, and "forgotten" when the function exits. The orders in python are innermost scope (local), enclosing scopes (nonlocal), global, and built-in names. 

     The example below is about how global and nonlocal methods work and the clearer sight of namespaces and scopes. When we first assign spam = "test spam", it is local in scope_test(); "spam = "local spam"" is inside do_local(), therefore after the function is called, the value is forgotten, spam still refers to "test spam". After we nonlocal spam in the do_nonlocal(), we assign new value to spam, "spam = "nonlocal spam"" and it is still true in scope_test(). Moreover, global spam make "spam = "global spam"" true in global name spam. However, we still print local spam inside scope_test(). Finally, when we exit the scope_test(), the global name spam refers to "global spam".

def scope_test():
    def do_local():
        spam = "local spam"
    def do_nonlocal():
        nonlocal spam
        spam = "nonlocal spam"
    def do_global():
        global spam
        spam = "global spam"
    spam = "test spam"
    do_local()
    print("After local assignment:", spam)
    do_nonlocal()
    print("After nonlocal assignment:", spam)
    do_global()
    print("After global assignment:", spam)

scope_test()
print("In global scope:", spam)

The output of the example:

After local assignment: test spam
After nonlocal assignment: nonlocal spam
After global assignment: nonlocal spam
In global scope: global spam

(from: http://docs.python.org/3.3/tutorial/classes.html#python-scopes-and-namespaces)

Thanks for reading!