WEEK 11 SLOG

Sorting and Efficiency

Last week, we covered several sorting method and their running time(in bigO notation). In 108, we learnt three kinds of sorting algorithms. They are bubble sort, insertion sort and selection sort. All three cases take n^2 time in the worst case. Selection sort need to go over the list in every outer while loop, which makes it have the same running time regardless of best or worst case. Insertion sort has a linear running time when sorting a sorted list since the insertion part need to compare the element with the elements before this index until it finds the right position. We did not cover Bubble Sort in 148, so I just ignore this algorithm.

In 148, we have some "smart" sorting algorithms. The first one I want to talk about is mergesort. We proved the correctness and running time of mergesort in CSC240. By strong induction, we have the algorithm that returns the sorted list for each half of the list and then merge it, which should return a sorted list. And the running time mostly depends on the recursive calls not the merge function, which results in the nlogn running time for best or worst case.

Another sort we are required to know is quick sort, which is quite different from the merge sort but both of them use recursive method. The basic idea of quick sort is to choose a pivot randomly. Then we find all elements which are smaller than the pivot and plug into recursion as list1. Similarly, we find all elements which are greater than the pivot and plug into recursion as list2. Finally, we use list1 + [pivot] + list2 to get a sorted list.

The worst case for quick sort is that it chooses the leftmost element as pivot in every recursive call.If we let T(n) denotes the running time of it. T(n) = O(n) + T(n-1) and we can solve T(n) is O(n^2), which is the same as insertion sort and selection sort. However, in my opinion, we can ignore the worst case for quick sort since it rarely happens. The average case of quick sort takes nlogn time, which is the same as mergesort. We can get this result by solving T(n) = O(n) + 2T(n-1).

When reading my classmate's slog, I found lots of useful information. For example, in Alice's blog (http://lbg940131.blogspot.ca/). She claims that the point of O notation is we need to choose a tight upper bound. Like O(nlogn) is better than 0(n^2) although O(nlogn) is contained in O(n^2). Another classmate gave some helpful reading material about sorting which I found it quite interesting. (http://weidong148.blogspot.ca/)

Week 10 Slog

Hi, everyone!

The second term test is approaching, which makes me quite nervous, given that I had bad performance in some exercises in recent labs. Basically, we have been dealing with recursive method in the last few weeks. Since week 7, we are required to apply recursive method in Linkedlist, Binary Search Tree, and Linked Binary Tree. In my opinion, the linked binary tree is the most challenging one. At the beginning, I tried to get a one dimension list from a given binary tree and the use the list to produce, but Ta said that was not the point of this exercise. When the solution to the lab released, I realized that we were supposed to use tuple to combine binary tree with linked list, which was a little bit similar to what we had done in exercise 3.

In lab 8, we were dealing with recursive method in Binary Search Tree. We were required to implement a recursive method to count the number of  items in BST which are smaller than the given one. I remembered we were trapped after figuring out the base case. When the solution was released, we know the main point of this method is to use the property of BST. If the root is less than item, then we should count the root + left tree and do left tree + right tree in the other case. And the hard part of this lab is to understand the difference between 3 kinds of method, which has different base cases and result in huge difference.

Wish everyone good luck in the test!!

Week9 Slog

Hi, everyone!

In this week lectures, we covered the binary tree and an introduction for time complexity.

I think exercise 3 and lab were both big challenges for me. First about the E3, it really took me a long time to figure it out. And I don't think I can work it out alone without some outside help. Part A is fine and not so hard, but part b is, eh..quite a challenge. It would not be overstated that it should be the most difficult recursive function I've ever written. I was struggle how to store the height of the node along with the sum until my friend suggested to use tuple, which I would never come up by myself.

Lab was difficult mostly because we were asked to write recursive method. And it is new for us to write a helper function inside a class method. By I am still wondering the necessity to have a helper function inside.

Week 8 Slog

Hi,everyone!

After doing so much recursive exercise, I think I am supposed to have a better understanding of recursive function. But in this week's lab's lab, my partner and me were still struggle for how to build a recursive.

We just covered how to prove the correctness of a recursive algorithm in our CSC 240 class. Basically, every correct recursive algorithm can be proved by strong induction. I think considering the base case is extremely essential for writing a recursive function. Also, we can use strong induction to help us to write it.

Taking an example we used in CSC 240, let's say, we want to write a recursive algorithm that Sort a list. By strong induction, we have the algorithm does what we want for len=1,2,3,4,5...n-1. Now if we want sort a list with length n, then we can just divide the list into 2 parts and do the recursion. Then, by MergeSort, we put 2 parts together and it is still correct which follows by strong induction.

Week 7 Slog

Hi, everyone!

The topic of this week is recursion. We have been dealing with recursion from the beginning of the semester. I think we can always see recursion in the lecture, lab and test. I have to admit that it is not an easy topic for me even it is not the first for me to approach recursion. It dates back the time when I was learning c++ and we spent lots of time on this topic. I can still remember the typical examples for recursion in C++ are factorial and Fibonacci Sequence.

The examples we have in recursion are quite comprehensive. At the beginning, we use nested list as our recursive examples. Then, we have turtle recursion and something called permutation, which costed me tons of time to understand what is going on. Additionally, we use recursion in our assignment and lab. I can clearly remember how we implement recursion in Hanoi Problem. Finally, we use recursion in Tree class and basically every method in Tree class requires recursion, which is quite challenging for us to write the code on our own.

I think the most efficient way grasp recursion to track some special examples and run the code in Python Visualizer. By doing this, you can really understand what is going on inside recursion. For example, if we write a recursive function to compute n!, then we have to go straight to 1!=1 and go back to n!. The prof mentioned the there's difference between human doing recursion and Python. I think if we are asked to compute 5!, then know the answer of 4! and then directly use it to compute 5!=4! * 5. Python does not know the answer of 4!, but it knows 1! and that is enough. It will go along back until reaching 5!.

When writing recursive function, I think what professor concluded about on recursion was very helpful. Basically, recursion involves a base (in order to stop the recursion)and a recursive formula. That is a good guide for me to write recursion function.

Finally, there's a recursive exercise in lab. We are required to reverse a string without using any built-in function. And following solution is really smart and reveals the elegance.  

def reverse(s):    
     if s == "":         
        return s     
    else:         
        return reverse(s[1:]) + s[0]

Week 6 SLOG

Hi, everyone!

We had two lectures about how to represent binary trees in Python. Since I am taking csc240 now and we just covered this topic, it should not too challenging to me. I think the nicest about binary trees is that it is a great example for doing recursion since a parent tree can have two children and then keep continuing. If we know something about its subtrees, let's say leaves, then we know the number of leaves of the whole binary trees.

The prof covered three examples of how to order binary trees (preorder, inorder postorder). All of three functions involve recursion, and I find it really helpful to run the recursive functions in Python visualizer. It can help you understand recursion better.

Also, the prof talked about Tree class, the most interesting of this class is basically all of its method involve recursion. So when the prof wrote the method, I experienced a hard to follow him. But I did review all the methods at home and had a better picture of this class. Besides, I learnt some new build-in function of Python. For example, any function can return True if one of the element in for loop is true. And filter function is a good idea to combine another function result and a for loop to produce a list.

Anyway, term test is coming and next week is reading week. Hope it would not be an actual 'reading' week.

Week5 SLOG

It is week 5 now. The most important topic this week, I think, is recursion according to the A1 and lab. But we are required to talk about recursion on week7. So, I want to write something specific about A1.

I suppose most people have started A1. Frankly speaking, the assignment in csc148 is really quite different from that in 108. A1 is way more complicated and requires much more work. It involves class, recursion and basically everything we have learnt in 108. So, it is a decent opportunity for us to test whether we can apply what we have learnt for programming in Python. Besides, we can review some new concepts just learnt, like recursion in this assignment, which it is hard to finish but excited to think how to write it.

I think the most tricky part in this assignment is the Tour part. At the beginning, we could not figure out a clue. I think the most difficult part here is we were not sure how many extra functions we were supposed to write. Actually, we came across the some problem when doing step 2. Sometimes it is hard to start because you are uncertain whether your thought in mind is correct. And a good start or more precisely, a good try could be a half success.

Luckily, prof gave us a clue about three stools version during lecture. It inspired us that 4 stools version was basically the same recursion with a slight change. The recursion of 4 stools should be formed by 3 parts, one of which should be 3 stools recursion and the other two should be moving n-i cheeses. So we need to write a 3 stools recursion which was covered in lecture as a helper function.

We have not finished A1 yet, but I believe we will finish all the steps soon and I am sure I will learn many new things from my partners.

Well, the midterm is approaching and it seems we lack enough past tests. There is only past test on the main page.