Since we learnt about tree object, the recursive feature of it made me increasingly curious about what else we could develop from this object. During Week 9 we mainly learnt about the Binary Tree Node and how to construct a Binary Search Tree(BST). A Binary Search Tree is basically a recursive node-based binary tree object with three special features: First, the left subtree of a node contains only nodes with keys less than the node's key; second, the right subtree of a node contains only nodes with keys bigger than the node's key; and third, there is no duplicate nodes.
There're several very representing methods of a BST, including insert, find, delete, and height. Learning about how to write those methods in class really inspired me a lot. Basically we need to right a helper function for almost all of those methods, which is quite challenging but helpful to me because I haven't had many chances practicing writing helper functions. Since all the functions and method are recursive, I achieved a more thorough understanding of recursive functions.
What's more, Week 9's lab is also both very challenging and inspiring. Together with my partner, we drew many pictures of what the function is going to do before starting to write the code. TA also helped us a lot on understanding the purpose of each function and how we could avoid unnecessary extra work.
During this week which is Week 10, I feel excited about learning about two more sorting method other than the three basic ones I learnt in last semester's 108 course. They are very efficient compared to the ones we have learnt and also make a lot of sense to me because I have had a decent understanding of recursive functions.
The first one is called Quick Sort which sounds good :) Basically it picks the very first value as a pivot value from a list of values and split the whole list in to three parts- the left half which contains values smaller than the pivot value, the pivot value, and the right half which contains values greater than the pivot value. After doing this step recursively, we can finally get the result which is a sorted list. However, this can be very time-consuming if the list given is already sorted. After quite an amount of discussion, we come up with an idea that we should randomly pick the pivot value instead of using the first value of the list as a pivot value. In this way the possibility of accidentally picking the smallest value as our pivot value decreased to a large extend.
The second sorting method I learnt is Merge sort which behaves even better than Quick sort. Briefly speaking, it divides the whole list into approximately equally half and compare the two smallest values from both sublists and send the smaller one to the merge list. By doing this recursively, we can get the resulting sorted list very fast.
By doing lab 10 this last week, I can see more directly from the graph me and my partner made out of each sorting algrithm. Appearantly the built-in sort method does the best job among all. The three sort methods we learnt from cs108 course has a running time of about n^2 while the other three methods we encountered this semester only require log(n) with base 2.
Looking forward to next week's class and hoping I can do well on the second test!
2014年3月19日星期三
2014年3月2日星期日
CSC148 SLOG - Recursive object Tree and LinkedList (week 6- 7)
Recursive objects are amazing. The key thing to understand when writing recursive function is figuring out what the base case is. After figuring out what basically we want the function to do, the rest part is to repeatedly call the function itself until reach the base case.
Just like the turtle we learnt about last week during lecture, the very representative object called Tree during week 6's lecture inspired me a lot. I discovered that the intellectual merit of recursive functions is that it allows us to write the code in a optimized and efficient way when encountering difficult situations.
What's more, the most fascinating thing about recursive functions is tracing through them. For instance, by learning about the three traversals of a Tree object- preorder, inorder, and postorder, I saw that tracing through recursive functions can be sort of tedious, however, eventually I can reach the base case and solve for the correct answer.
Similarly, the lectures on LinkedList object during week 7 are also very informative. Conceptually, there's a sequence of nodes within a linked list, each with a head and a reference to the rest, which is also a linked list. As shown below, a linked list is basically a nested list with references.
When initializing the object, we used the default value None for both the head and rest. And surprisingly, prepending a new head to a linked list is not that simple as I thought, there're three procedures:
1. Start the rest of the list with the current attributes by shallow copying them
2. Change the current head to the one passed in
3. Change the current rest to the copy.
Just like the turtle we learnt about last week during lecture, the very representative object called Tree during week 6's lecture inspired me a lot. I discovered that the intellectual merit of recursive functions is that it allows us to write the code in a optimized and efficient way when encountering difficult situations.
What's more, the most fascinating thing about recursive functions is tracing through them. For instance, by learning about the three traversals of a Tree object- preorder, inorder, and postorder, I saw that tracing through recursive functions can be sort of tedious, however, eventually I can reach the base case and solve for the correct answer.
Similarly, the lectures on LinkedList object during week 7 are also very informative. Conceptually, there's a sequence of nodes within a linked list, each with a head and a reference to the rest, which is also a linked list. As shown below, a linked list is basically a nested list with references.
1. Start the rest of the list with the current attributes by shallow copying them
2. Change the current head to the one passed in
3. Change the current rest to the copy.
Writing the __contains__ builtin function also helps me understand the structure of a LinkedList object.
2014年2月6日星期四
Recursion (week 4- 5)
A recursive function is a function that its implementation references itself. I have been increasingly interested in recursive functions since I was introduced to the concept in the first lecture of this course. In plain English, a function can refer to its own header in the body so that it can execute itself over and over again and produce the result we want more efficiently.
During week 4, I learnt more about recursive functions. Specifically, I learnt about nested list and how to solve for the depth of a nested list. We started by defining the nesting-depth of L as 1 plus the maximum nesting depth of L's elements if L is a list, otherwise 0. Then I learnt that the code we write is almost exactly the same as the definition, that is, return (1 + max([nested_depth(x) for x in L] + [0]) if isinstance(L, list) else 0). we add [0] into L because we need to treat the depth as 0 in case we go through an empty list.
At first I was a little confused about what's going on because I don't quite understand why and how we can put a function header in its body to execute the code. However, by discussing with the person next to me during class and also by finishing up Assignment 1, I walked myself through both the definition and application of recursive functions. What's more, figuring out how to complement the codes in the Tour.py file in Assignment 1 gives me a more thorough understanding of recursive functions.
What I found most interesting about week 4's lectures was the turtle functions and how amazingly the "turtle" object can draw those pictures. As a very classic recursive object, turtle also refer to itself in the function body. the picture it drew impressed me a lot. The basic rule of how the turtle object works is like the growth of tree twigs, which is a lot like the picture below:
During the lab of week 5, I applied my knowledge gained previously and actually sat down and wrote some recursive functions together with my partner. We figured out that a recursive function will not stop running until the condition in the 'else' part is met. This concept makes my understanding of recursion even more clear.
Recursive functions are amazing and hopefully I'll learn more about them in the next few weeks.
SEE YOU NEXT WEEK! :)
During week 4, I learnt more about recursive functions. Specifically, I learnt about nested list and how to solve for the depth of a nested list. We started by defining the nesting-depth of L as 1 plus the maximum nesting depth of L's elements if L is a list, otherwise 0. Then I learnt that the code we write is almost exactly the same as the definition, that is, return (1 + max([nested_depth(x) for x in L] + [0]) if isinstance(L, list) else 0). we add [0] into L because we need to treat the depth as 0 in case we go through an empty list.
At first I was a little confused about what's going on because I don't quite understand why and how we can put a function header in its body to execute the code. However, by discussing with the person next to me during class and also by finishing up Assignment 1, I walked myself through both the definition and application of recursive functions. What's more, figuring out how to complement the codes in the Tour.py file in Assignment 1 gives me a more thorough understanding of recursive functions.
What I found most interesting about week 4's lectures was the turtle functions and how amazingly the "turtle" object can draw those pictures. As a very classic recursive object, turtle also refer to itself in the function body. the picture it drew impressed me a lot. The basic rule of how the turtle object works is like the growth of tree twigs, which is a lot like the picture below:
Recursive functions are amazing and hopefully I'll learn more about them in the next few weeks.
SEE YOU NEXT WEEK! :)
2014年1月19日星期日
CSC148 SLOG - Object-oriented Programming (week 1- 3)
According to Wikipedia, Object-oriented programming (OOP) is a programming paradigm that represents concepts as "objects" that have data fields (attributes that describe the object) and associated procedures known as methods.
Basicly I learnt about how to build a Class object properly and how to use some specific methods and modification tools to make my class object more consistent during the past three weeks. Though creating a class object was from csc108 mainly, I enhanced my skills of creating Class objects during my 148 classes.
I find it very useful and more efficient to write the type contract in the function header. For instance: "def __init__(self: 'Point', coord: [float, ]) -> None: " I was not very comfortable about writing this way at first, but after I practiced over and over again, I realized it is truely a better way to construct the code which saves both space and time.
Exercise 1 and the lab exercise also helped me a lot to improve my way of thinking like a computer scientist. During the lab exercise, I was at first confused about what indeed should I do to arrange the information i got and apply them properly in my code-writing process. I then discussed with my partner and figured out that the first step is to name the class and two crucial methods in a precise and brief way. Then we struggled between whether to make the file we got a list or to make it a dictionary. We figured out it is better to make it a dictionary where keys are the number of occurrence of the words in text and values are the words that occurred that many times. It made everything easier to proceed the first main method which is to get the top n word occurred in the file. With my partner, I learnt how to think independently like a computer scientist and think ahead to make things flow more efficiently.
During the lectures of week 2 I learnt about some ADT types - lists, stacks, dictionaries. Also I gained some knowledge about some comprehensions like [expression for x in items] where x is a variable and items can be a list, dict, set, tuple, etc. 'Ternary if' is also very useful in coding. It appears in form of "expression1 if condition else expression2". It does save a lot more space than writing in old 'if' structure and is easier to understand.
During week 3 I gained some knowledge about how to extend the features of Stack, a class object we created before, by writing a subclass of the existing class. We can name the subclass the way how we want it to function. Then we add conditions to the methods inherited from the original class to create the new methods for our subclass. More excitingly, I learnt that we can even create our own Exception Type. For instance, the PopEmptyException that is raised when try to pop an empty Stack.
I'm so glad that I learnt those new stuffs so that I can apply them to my future coding exercises and assignments.
Basicly I learnt about how to build a Class object properly and how to use some specific methods and modification tools to make my class object more consistent during the past three weeks. Though creating a class object was from csc108 mainly, I enhanced my skills of creating Class objects during my 148 classes.
I find it very useful and more efficient to write the type contract in the function header. For instance: "def __init__(self: 'Point', coord: [float, ]) -> None: " I was not very comfortable about writing this way at first, but after I practiced over and over again, I realized it is truely a better way to construct the code which saves both space and time.
Exercise 1 and the lab exercise also helped me a lot to improve my way of thinking like a computer scientist. During the lab exercise, I was at first confused about what indeed should I do to arrange the information i got and apply them properly in my code-writing process. I then discussed with my partner and figured out that the first step is to name the class and two crucial methods in a precise and brief way. Then we struggled between whether to make the file we got a list or to make it a dictionary. We figured out it is better to make it a dictionary where keys are the number of occurrence of the words in text and values are the words that occurred that many times. It made everything easier to proceed the first main method which is to get the top n word occurred in the file. With my partner, I learnt how to think independently like a computer scientist and think ahead to make things flow more efficiently.
During the lectures of week 2 I learnt about some ADT types - lists, stacks, dictionaries. Also I gained some knowledge about some comprehensions like [expression for x in items] where x is a variable and items can be a list, dict, set, tuple, etc. 'Ternary if' is also very useful in coding. It appears in form of "expression1 if condition else expression2". It does save a lot more space than writing in old 'if' structure and is easier to understand.
During week 3 I gained some knowledge about how to extend the features of Stack, a class object we created before, by writing a subclass of the existing class. We can name the subclass the way how we want it to function. Then we add conditions to the methods inherited from the original class to create the new methods for our subclass. More excitingly, I learnt that we can even create our own Exception Type. For instance, the PopEmptyException that is raised when try to pop an empty Stack.
I'm so glad that I learnt those new stuffs so that I can apply them to my future coding exercises and assignments.
订阅：
博文 (Atom)