SLOG #9: Sorting and Efficiency

Sorting and Efficiency are very important concepts in computer science. It's quite normal in real life to sort a series of data for example, ranking students' grades. It's significant to use a quick and space-efficient way to sort data, especially in cases where the data size is huge.

The speed of sorting is based on the sequence of the data. We describe the speed in three cases: the best case, the average case, the worst case.

We use big-Oh to describe the speed of sorting. Running time is a description based on the input size n. When describing this algorithm, we ignore the constant c in running time so the algorithm is shown in O(g(n)) instead of c g(n). It's actually very smart to scale speed in this way. Since it is obvious n^2 is much larger than c n when n is huge (some constant c). We could easily compare distinct methods' speed in this way. For example we describe the speed of merge sort as O(n log n) and the speed of selection sort as O(n^2). Thus selection sort is slower than merge sort. Scaling of insertion algorithm, selection algorithm and bubble algorithm is all O(n^2) in average cases so we could tweak implementation of the same algorithm, combine these methods, and find the best way.

We are going to discuss four sorting algorithms in detail: selection sort, insertion sort, quick sort and merge sort.

Selection sort

Selecting sort selects the smallest element from the remaining n-i right-post position and swaps it into position. Its efficiency is O(n^2) in the best and the worst case. Actually the same number of steps is taken with the same size n. This way of sorting is the slowest one compared to other three ways of sorting. However it's quite natural in playing cards in real life.

Insertion sort

Insertion sort is similar to selection sort. It takes the next element (at position i) and insert it into its proper place in the left-most i +1 positions. Its efficiency is O(n^2) in the average and the worst case but O(n) in the best case where the list is generally sorted. Thus insertion sort is a little bit quicker than selection sort. However since their algorithms are the same in the average case and it's rare to sort a sorted list, its speed is still slow.

Quick sort

Quick sort is much better than selection sort and insertion sort in average cases. Quick sort works by somehow choosing a pivot and breaking a list into two sublists (everything smaller than the pivot, everything larger than the pivot). It continues to break down the list in this way until the list can't be broken down and brings all the sublists together. Its efficiency is O(n log n) in the average and best case however O(n^2) in the worst case. The worst case is we keep choosing the greatest or smallest item as the pivot and it has the same efficiency as selection algorithm in this case. However we hardly have the chance to keep choosing the greatest or smallest item as pivot. We could choose to find the pivot by finding the first, last and middle elements of the list and choose the median as the pivot to avoid this. In general, quick sort is still very efficient compared to selection sort and insertion sort.

Merge sort

Merge sort is similar but better than quick sort. Merge sort works by dividing the list in half until it can't be divided anymore and then mergesorting each of the two halves. The efficiency of merge sort is O(n log n). The same steps in any cases with the size n are taken. It takes log(n) steps to break the list into pieces and then mergesort all elements with log(n) steps and n comparisons in each step so its efficiency is O(n log n).

In the class, we also discuss a little bit about count sort and python built-in sort Timsort. Counting sort is very convenient to small integers with efficiency O(n) basically. Timsort is a combination of merge sort and insertion sort. In the last lab, we used test_sort to test various algorithms’ performance and found Timsort is the quickest.

Efficiency is very important in computer science especially when we need to process huge amounts of data. I really enjoy learning about these topics. Feel free to leave comments here.

SLOG #8: Big-oh, Better Sorts, Assignment 2

This week is quite busy. Assignment 2 is really challenging. The hints given by professor in the lecture are really helpful for us when solving assignment. Basically, this assignment is about recursion. We need to consider every base case carefully and connect them together. After we had an idea of how to divide the problem into several cases, writing the code became much easier.

Another thing we learned this week is sorting. Quick sort and merge sort were taught in class. Quick sort works by somehow choosing a pivot and breaking a list into two sublists (everything smaller than the pivot, everything larger the pivot). It continues to break down the list in this way until the list can't be broken down and brings all the sublists together. Its efficiency is O(n log n). Since it takes around log(n) steps to break down the list and each step has (n + constant) comparisons. However, in rare cases if we keep choosing the greatest or least element, the efficiency will be reduced to O(n^2). One way to avoid that is to find the first, last and middle elements of the list and choose the median as the pivot. Merge sort is kind of like quick sort however we need to add a help function for this sort. Merge works by dividing the list in half until it can't be divided any more, and then mergesorting each of the two halves. The efficiency of merge sort is stable compared to quick sort which is also O(n log n). Since we don't need to choose the pivot for merge sort, the efficiency of merge sort doesn't depend on the order of elements in the list but only the number of elements in the list.

I feel the algorithm is a little bit vague since we didn't do an accurate derivation however obviously the efficiency of merge sort and quick sort is much quicker than selection sort which is O(n^2). Thus, practically we use quick sort and merge sort to sort a large-size list.

I didn't consider efficiency in solving problems until this week's lecture. It's quite important to know something about efficiency.

SLOG #6 & 7: Linked Structures, BSTs, big-Oh

Last weekend I was so busy that I didn't have time to write a SLOG so this SLOG is a combination of what we learned in week 8 and 9.

For week 8, we learned something about linked lists. There are two different ways of thinking of linked list structures: 1. a list made up of an item and the remaining list; 2. an object with a value and a reference to other similar objects which needs to build up a wrapper class in order to keep track of the information about the entire list at front of it. We are assigned to think about how to build up a reverse_links. It took me much time to fully understand how it works. We need to use recursion to solve this problem without hesitation. However since the original version of the code posted on the course website is very comprehensive, I can't get its logical relationship right away. As building up other recursions, we firstly think about the simplest case where there is only one object without a reference. Then we think about how it works when the object has a reference which has no reference itself and introduce the method to other cases using recursion. It's quite important to figure out how general cases work in simple cases. In python __str__ methods are more informal than __repr__ methods. A helper function _str is built in order to make the __str__ method easier so we could avoid building a helper function with recursive structure in the definition of __str__.   

We also learned about the binary search tree in week 8 which was also covered in week 9. For BST, data in the left subtree is less than that in the root and in turn less than that in right subtree. Search becomes much more convenient if the data is inserted using this law. It's not easy to delete data from such a BST rooted at the node especially in the case that the node with data has two non-None children. The node needs to be replaced by the largest child in the left subtree and then delete that child. Unlike method insert in the single tree class, the recursive structures for method 'insert' should be built on the node instead of BST.

Algorithm for list searching whether a data is in a list is linear. However using binary search we could ignore (roughly) half of the list either left or right. The algorithm is log n performance for n nodes.

We also reviewed two stellar sorting algorithms we learned in CSC108:

1. Selection sort: select the smallest element from the remaining n-i right-most position and swap it into position i.

2. Insertion sort: take the next element (at position i) and insert it into its proper place in the left-most i +1 positions.

Running time is an algorithm over size n. We could ignore the constant c in algorithm as n goes large so the algorithm is shown in O(g(n)) instead of cg(n) (some constant c).

That's what we've learned over these two past weeks. Feel free to leave comments here.

SLOG #5: Recursion

This week is quite special. Firstly we had quite a hard lab. I didn't get the idea of it until now. Secondly we had a midterm term during lecture time on Wednesday so we didn't actually learn a lot this week. Thirdly the topic of this week's slog is assigned to be recursion. Since I have posted recursion a little bit in the past few weeks, this week's slog is kind of like a summary.

Recursion is the process of repeating items in a self-similar way according to definition from Wikipedia. Basically in python, it means keeping calling the function itself in its function body until it reaches the base case. So we definitely can't leave out the base case or it would keep calling itself without stopping which causes a runtime recursion depth error.

Though we know recursion is convenient. We could make our code much shorter and clearer to read compared to iteration sometimes. It's not always easy to write a recursion. Through these weeks of exercise, I think figuring out the base case and next-most complex case firstly will be helpful. We could plug some simple cases to test our code. For example, for assignment 1(Tower of Hanoi), we first figured out how 3 stacks work. We started from moving one cheese (base case) without needing to using recursion. Then we started to think about 2-cheese and 3-cheese case and get the idea we could move all but the bottom cheese to the intermediate stool, bottom cheese to the destination stool, and all but the bottom from intermediate to destination. The concept of moving 2 cheeses to their destinations could be generalized to n cheeses. This is how recursion works. Keeping calling itself until it reaches the base case: the number of cheese is 1.

As posted in SLOG 2, compared to iteration, recursion has drawbacks such that storing certain values on the stack for each function call which takes time and space. Since until now we didn't encounter really complex context, the advantage of recursion is very obvious. We could consider using recursion any time we need to repeat objects or functions in a similar way.

Finally, feel free to leave comments here.

SLOG #4: Trees

Last week, we didn't learn anything new. However it's still very helpful since we applied knowledge from before, especially recursion, to build trees. A tree is a good example of a recursive structure.

We firstly learned some terminologies about trees and found there are three different ways of traversing a tree: preorder, inorder and postorder. It's quite useful to learn how to write functions for these traversals. I found these functions are the same in base case. The only difference is the order of the functions in general case. The advantage of applying recursion is obvious here because it is easy to read what is going on in the function.

Code for general tree implementation is a little bit hard for me to write at the very beginning. After Professor Danny showed us the answer, I felt things become easier and I started to get used to the tree structure. Through practise, I feel it's efficient to think about several easy examples, write down the base case carefully firstly and then to introduce it to general case.

The midterm is coming next week. Good luck everyone :)

SLOG #3: Towers of Hanoi and Namespaces/Scopes

I spent most of time of this week working on the first assignment "Tower of Hanoi" which was really challenging. I was inspired by the hint given in class about how to move cheeses of three stools and finally figured out how to use the same recursive logic on four stools. This assignment definitely improves my programming ability and my understanding of recursion. I was quite excited about the animation of my solver when it automatically solved the puzzle using computer's amazing calculation speed.




I felt quite confused about the concept of namespaces and scopes learnt this week. I didn't know exactly how local scope and global scope work at the very beginning. By reading the scopes and namespaces from the python official website, I got Python searches for names in order from local scope, enclosing scope(nonlocal), global scope to built-in scope.  We could add nonlocal assignment to change scope_test's binding and global assignment to change the module_level binding. These assignments are quite useful when assigning values to variables.

Finally, I have a question:

Context A:

>>> x = 'outer'
>>> def func():
 print(x)
 x = 'inner'
 print(x)

>>> func()
Traceback (most recent call last):
  File "<pyshell#6>", line 1, in <module>
    func()
  File "<pyshell#5>", line 2, in func
    print(x)
UnboundLocalError: local variable 'x' referenced before assignment

context B:

>>> def func():
 print(x)

>>> func()
outer

This example is from: http://docs.python.org/2/faq/programming.html#why-am-i-getting-an-unboundlocalerror-when-the-variable-has-a-value

It’s really interesting to see I can’t reference x in the local slope that is assigned in the global scope before assigning it in the local scope (context A), however it works without assigning it in the local scope (context B).

Feel free to leave comments here. I hope to learn more from you.

SLOG #2: Recursion

This week we learned something about recursion which is really efficient for solving large-scale problems. Recursion means “defining something in terms of itself”. This approach breaks down a complex problem into small pieces which we could apply the same algorithm to with changing parameters until a termination condition is reached and combines the result.

Every recursive function is a combination of general case and base case. Base case is also called termination case. Every recursive function must have at least one base case otherwise it will keep calling itself. The general case is a recursive sub call which happens most of time. We should avoid leaving out the base case when writing a recursive function as well as circularity.

We could use both recursion and iteration to solve problems involving repetition. Compared to iteration, recursion is easier to read and requires fewer lines of code; however it is a little bit slower. This is because recursion calls itself many times and stores certain values on the stack for each function call, which takes time and stack space.

Finally, feel free to leave comments here J