Sorting and Efficiency

The day before the test I read this table for preparation:

(http://bigocheatsheet.com/)
What we've always been focusing on is the worst case performance of an algorithm. By intuition, the "worst case" a sorting algorithm could have should be when the given list is in descending order (i.e. sorted and reversed, as described in the lab this week). In the worst case, merge sort performs well, while bubble, insertion and selection we learned from CSC108 has less efficient algorithms.

How efficiently a function works is determined by the way it does the work and how long the computer actually takes to finish each step. Even a small variance in the code may have a big influence on the overall efficiency. For example, if you have a while loop, and have some value like L[i:] as the condition, the function would have to take the piece L[i:] each time when the loop is executed. If there could be an alternative version of this while loop which uses the single index i as the variant to be examined as the condition, it would make this part of the code much more efficient.

Personally I like selection sort, though it is not an efficient one. No matter how the list is arranged (random, sorted, or sorted and reversed), in each step of iteration it looks at every element in the list and find the smallest one, then switch it with the first element in the unsorted part. Even when the rest of the list is already sorted, there is no way the function could know it. That's why it has the same big O for its worst case and best case. This sorting algorithm works in a way closest to how a human's brain processes list while manually sorting a list.

Another algorithm which has the same efficiency working in its best case and worst case is merge sort. When given a list, the function breaks it into two parts, repeat these steps until there are only two elements in a group so that this group can be merged together in order. Then it merges each group of two lists, until there is one final ordered list left. Even if it is originally given a completely sorted list, it will still do these steps since it does not know the list given is already its correct order.

Merge sort is more efficient than selection sort just like binary search is more efficient than linear search. By dividing the list in halves it can actually save lots of calculation.

Bubble sort and insertion sort are, though doing bad in the worst cases, doing better than merge sort in the best cases, when the given list is already sorted. The point is that these two algorithms do examine whether each number is in their correct position, and if so they just go through the entire list and then end without doing anything else. In this way they win the race when the list given is already sorted.

In most cases, however, the list given to sort is a random list, so that the average and worst-case run-time is more important when we discuss the efficiency. So from the list above, we consider merge sort and radix sort as efficient algorithms.

The Lab wasn't Going Great...

I could not figure out how to write the first function during the lab. The TA said that we should construct a helper function which finds the first LLNode and the last.
I suppose that it should work as taking in the left branch of the node and finding the first node of the in-order traversal and the last node. The reason for that is what we do is that we take the root node of the tree, represent it as an LLNode, append the traversal of the right branch to it, and append itself to the end of the traversal of its left branch. The last step is the most complicated step since we do not know to which LLNode we should append the root LLNode to, unless we can get access to the last node of the left branch.

Then the entire code should be like:
make an LLNode with the root value given as its item
use the helper to find the first node and last node of the left branch
make this root LLNode the link of the last node of left branch, and make the first node of traversal of the right node the link of itself

Then the rest of the work can be done by recursion.

Revision:
After the term test I found that I should have worked harder to understand this lab task better, because it seems that we needed a similar helper for the function we're writing on the test... But I had no idea on how exactly the helper should look like... My regrets:( and especially for that unlike my buddies I do need the 60% course grade in order to get into the program since I'm in PMS... I did assume that the test would not be "as hard as the lab is" so I did not really pay too much effort on it.

Binary Search

A binary search tree is a convenient way to find objects. It has a big-omicron of log2(n), which makes the program more efficient dealing with larger sets of data.

By learning this I had finally realized why a traversal which takes the left branch of a node first, then the symbol of the node it self, then finally the right branch is called an "in-order" traversal... If it were a binary search tree, then its in-order traversal will be just a list of the numbers sorted in ascending order.

Though more efficient in looking for data, the coding part is much more complicated than a linear search method. For different types of input we actually have to use a lot of "if" statements to deal with them separately. Good news is that once I understand what the code should be able to do, the coding part is not that challenging. A problem I always have is understanding the task a function should do in order to reach the goal. When I'm dealing with some seemingly complex tasks I have to keep calm and go through the requirements to be met... ask for help... and finish the coding part quickly. Perhaps I just need to do more practices.

Linked Lists

Once (when I was preparing for the term test) I had a feeling that almost all that we've learned during the previous weeks were examples of recursion: working on nested lists, recursive trees, python turtle, etc.

Linked lists, to no one's surprise, is another example of recursive processing, which as its own limitations and advantages. For example, in order to return the item at a given index in a linked list, we have to iterate over the list before this index so that we can find the item. We should first check if the index i is 0, an if not, we use a new index i-1 on the "rest of the list". As the index becomes zero, we return the first item in the current linked list being processed. It works in a recursive way, which seems to be less efficient than finding an item at the same index in a normal python list.

However, linked lists do have some advantages over normal lists. For example, when we're taking out an object from a queue (in which data are stored in a first-in-last-out form), when we take out the item at index 0 from the normal list, items in the rest of the list have to be shifted leftwards. In a linked list, when an item is deleted it is almost as simple as when an independent object is deleted. The rest of the list remains unchanged, which makes it more efficient than moving out the item from a normal list.

So as we're programming we should think of how we can improve by using different ways to store the data.

Recursion - Tracing and understanding

Recursion is just calling the function itself inside the function body, in order to do repetitive computations, in a way kind of like looping.

At first it did not make any sense to me, since the function seems to be put into use before it is completely defined, i.e. you are already calling the function before you even finish the last line of the code.

However, by manually tracing the recursive process I could finally understand that recursive functions do make sense.

I'll use my favorite example to explain it.

(My version of) Python Turtle code present in class:

import turtle

import copy

COLORS = ('red', 'green', 'blue', 'yellow', 'orange')

def tree_burst(level, base, turtle):

    """Draw a symmetrical ternary tree of height level with initial edges

    of length base.

    """

    if not level: # Pythonese for level == 0

        #turtle.forward(base)

        pass

    else:

        turtle_list = []

        for h in range(5):

            turtle_list.append(turtle.clone())

            turtle_list[h].color(COLORS[h])

            turtle_list[h].setheading(72 * h)

            turtle_list[h].forward(base)

            tree_burst(level - 1, base / 2, turtle_list[h])

if __name__ == '__main__':

    T = turtle.Turtle()

    T.color('red')

    T.speed('slow')

#    T.hideturtle()

    tree_burst(3, 128, T)\

As mentioned in my previous blog, the resulting image is like:

When the main program is run, parameter "level" taken by the function is not 0 (yet). So it enters the 'else' part. While entering the for loop, a clone is created, a color is selected, and the direction is set. The turtle moves after all these preparations. After a line is drawn, the function prompts that it should repeat the calculation with (level - 1, base / 2, turtle_list[h]).

Then the function is run from the beginning, and the process is repeated until "level" reaches 0.

This period of recursion comes to an end. But wait, we haven't completed the for loop, yet. The program shouldn't stop. Since it has already taken 0 as the value of h, the function should then take 1 and repeat everything it has done.

What bothered me was that a recursive function seemed to be "called before completely defined". It was just a misunderstanding of the concept: the function is already well-defined when we run the program. It executes through the lines, knowing nothing about what is coming after the line currently being executed. Once it sees itself in its own body, it just go back to the first line with the new parameters given and continue executing, until it finds some way to escape, in this case, when level reaches 0. So an essential part for a recursive function, as far as I'm concerned, is the code which allows it to escape from the circle.

In this Python Turtle example, we actually see how a recursive function interacts with the for loop inside. I would say that a recursion and a loop are practically the same thing. They both deal with the same code executed over different parameters given each time. The only difference is that a loop is more explicit: we can easily find out when it will stop with (almost) no calculations. Recursion is thus just a fancier loop.

Maximizing efficiency

In the lab last week we solved problems related to loops and comprehensions. Converting a comprehension to a loop expression is not difficult, but during the conversion we have to think as a programmer, which is, to maximize the efficiency of the program.

We certainly have a number of ways to solve the same task. An example is the "stack" and "queue" problem we met in a previous lab. If the data is stored in a "first in, last out" method, while taking out (or storing)each object, all items in the list have to be shifted once to one side. If the "first in ,first out" method is used, then when taking out one object, the others just remain in their original position, thus it requires less computation.

While using a loop or a recursion, we shall reduce the number of iterations. For example:

lst = []
for i in range(1, 4):
   for j in range(1, 4):
      if (i * j) not in lst:
         lst.append(i * j)

return lst

To get the same result we can also have:

lst = []
for i in range(1, 4):
   for j in range(i, 4):
      lst.append(i * j)

return lst

They return the same result [1, 2, 3, 4, 6, 9], but the latter code takes less number of iterations, thus the latter one is more efficient.

Comment on 3-stool Hanoi/Working on A1...

The method to solve the three-stool Hanoi problems taught in class was different from what I had in mind. I know that the process works as a recursion, but what I have in mind is that, when manually solving this game we are actually repeating the moves we make. For example, if we want to move 6 pieces from the first stool to the last, we have to repeat twice the actions taken moving 4 pieces in order. So our process in mind is something like this:

prepare to move 1 - move 1
prepare to move 2 - move 1, move 2
prepare to move 3 - move 1, move 2, move 3
...

But the program just didn't work that way. Instead, it is thinking "backwards", figuring out what the last step should be, and deducing backwards. It is actually accurate since when we are deciding to which stool we move the first(smallest) piece, we do consider where we want the last piece to be placed.

The GUI graphics don't look good enough for me. Though we were asked not to make any changes to GUIViewer and GUIController, I made some changes to the width of cheeses and color arrangement.

I hope we can really get onto learning tkinter soon, so that we can make actual games in the future.