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.