Sorting algorithms and efficiency

  This is our last slog entry and we are assigned to the topic of sorting algorithms and its efficiency. In our lecture, we were taught about 3 main sorts and they are the quick sort, merge sort and selection sort. I remember that lecture was particularly special, recalling that our professor Danny brought a stack of coffee cups and demonstrated the quick sort, merge sort and selection sort ideas. It was really interesting and the ideas behind were clearly demonstrated.
  In terms of efficiency, quick sort is the fastest, and merge sort the second and finally selection sort is the worst. I found selection sort to be the sort that can be understand the easiest, it is to selection the smallest or largest one and put it into a new list, and then compare each and once again move it into the new created list and until the original list becomes empty. However, its procedure is way too slow and typically, our professor don't really recommend us using it.
  Quick sort is to randomly pick a value (we call it pivot) from the list and take rest of the other values and compare them against with the pivot. Values that are greater than the pivot are put on the left and values that are less than the pivot are put on the right. Then we recursively sort the left and right (we call it divide and conquer). The idea of divide and conquer are used by merge sort as well.
  Finally, the merge sort is that we pick a middle value, and divide lists into two equal length sublist and then to compare the first index of the left sublist with the first index of right sublist. If first index of left sublist is smaller than the first index of right sublist, then we move that value to a new list, if it isn't, then we move on to comparing the first index of left sublist with the first index of right sublist, and the smaller one is then append into the new list and this process goes on until we get a sorted new list.

About tracing and more

In this week's lecture, we talked about tracing and memory model. Professor Danny guide us through some of the recursion example using the python visualizer which I belief some of us have used in csc108 before. Python namespaces and scopes are also covered, the invention of python namespace and scope can lower the chances of confusion and also ensure when running a program, Python is calling the right function and using the right parameter. An example of local scope, non local scope and global scope was used to demonstrate the idea. However, it is quite confusing as I was not able to get the idea of the global scope. I don't understand why did the global scope called gave a spam non local spam. I did not have enough time to stay after class ended to ask Professor Danny because I have another class right after the 9am lecture. As soon as I went home, I review Professor Danny's annotated notes that was posted on the csc148 webpage and read the attached python notes that he put about 9.2. Python Scopes and Namespaces. This notes gave a detail breakdown of each component and I found this a big help. I understand a lot bettr now.  It is almost the end of the term, I feel like I've learned a lot in the term and is becoming more familiar with the Python language. I am looking forward to our last few lecture and hope everything can come into a good conclusion.

hiding attribute, equality

  In this week's lecture, we mostly covered the topic of hiding attribute, equality and reduce. Hiding attribute is somewhat similiar to a private attribute, however, there is a slight difference. It uses ._ instead of _ in the initializer. Changing an attribute of the parent, can causes change in the children's attribute as well. Also, we talked briefly about the equality, which is a build in function of python called __eq__. The equality function compares two node and see if they are equivalent, and noted that the function checks whether they are equivalent or not, instead of to check whether they are the same. It is interesting because even thought two nodes might be equivalent but it doesn't mean that they are the same. If we uses the id() to check, we can see that the two nodes have different identities. After that, we uses the build in python function property and we also create a get, set function, in this lecture we didn't create a delect function, therefore we have the delect fuction replaced with a None. If a node wasn't set in a function, which means it isn't an acceptable input of the parameter, in this case we raise an exception.

about test2

  The csc148 test2 is coming up on wednesday. I am really nervous about this test because I still feel like I am not so ready for the test. I am particularly weak at the recursion topic and about the structure about the binary search tree. I re-read all the course requirement reading and re-do the exercises that were assigned to us after test2. Hopefully, I will be able to manage to do okay on the test2. I will come back and conclude some of the hardship that I encounter during test 2 and share on this blog after I finished writing the test.

A thin slice of selection sort and quick sort

  We spent half of the lecture time on the topic Big O, and after that we moved on to the topic sorting. Sorting is quite interesting to me as it allows us to produce another list with certain order or command. I've learned a little bit of sorting methods in csc108, however, I was really unclear about its idea that time. But in today's lecture, Prof danny brought in a stack of coffee cups and did an interesting demonstration of the selection sort and quick sort with these "tools". I found the idea of selection sort and quick sort salient now. Which selection sort mainly focus on swaps of 2 item and start from beginning, while quick sort saves more time by just randomly extracting one out and do comparison. Both of these sorts gives a rearranged list of the original list. However, the idea of them wasn't fully covered yet because we ran out of time at 10am. Therefore, I believe the idea of sorting will be discussed in a more detail sense in the upcoming lecture.

introduction to Big O complexity and Regular expression

  We are introduced with the new idea of big O complexity (big Oh) and Regular expression (Regex) last week. The big O complexity gives an overview of the runtime complexity which I think they makes a lot sense in terms of the arithmetic proof. From what I've learned so far about regular expression, is that it is a bunch of characters that can include numbers, letters or operators, that forms a search pattern. The starnode, barnode and dotnode are some of the subnodes in a binary search tree. However, I am still confused with Regular expression thus I spent quite a lot of time on my assignment 2. I am not exactly sure if regular expression will appear on our future test, or exam as we weren't taught a lot of this topic, but I am sure that I will look more deeply in it.

More about recursion and tree traversal

  The idea of recursion still somehow confuses me many of the times, I get the idea that recursion is like looping on itself but when it comes down to the thinking of base case, it still gives me a hard time. However, Recursion is really convenient that it allows me to write a relatively short code body and it is really smart. List comprehension is another hardship for me, as the ordering of the "for", "if", "else" placements are somehow confusing, different ordering of them gives different operation. They are somehow that are worth a lot of caution. It is also something smart as it provides a shorter code body as well. I've been stuck on the tree traversal for a short while, I didn't understand the last exercise's task. I ended up spending a couple hours going through lecture notes and some additional tree traversal notes. I figured out the use of preorder and inorder list thus causing everything to make sense. Tree traversal gives me a general idea that when executing a body, we want to use the shortest process and quickest time.