I revisit my week 5 SLOG that I talked about my first impression of recursion, which was not so good; I am glad that now I am comfortable understanding and writing recurssive functions. Like I pointed out before, it is essential to know how to trace a recurssive function before you can write one. And tracing is also a useful method to test whether the function you wrote works correctly.
After a long period of time working along with recursion, I find that recursion is extremely efficient and can save us a noticable amount of time and lines for the problems that could break into parts. For example, as another SLOGer wrote, 6! could break into 6x5!, and then 6x5x4! and so on until it approaches to 1!; then we can use 1! as our base case recurse all the way until we get 6!. It is an really interesting example that gives me a clear mathematical comprehension of how recursion works.
Sunday, March 29, 2015
Sunday, March 22, 2015
Week 9: Prepare for the Test
We had the second term test in this week. I feel less confident for this test than the last one since I have learned more complicated structure: linked list. According to my last week's SLOG, I find that drawing diagrams for linked list methods is extremely helpful during the test as well.
For this term test, I managed my time efficiently so I did not rush during the test as the first one. However, I did not feel confident about this test...I must say that the biggest failure is that I did not prepare for the part of definition of Tree(question #1 on the test). I overly relied on the past test so I did not think about such question will be on the test. Luckily, I went through the inorder/preorder/postorder traversal once so I have done the order question right(hopefully).
Due to the TA's strike, we still do not have a chance to get our tests back to see what we did wrong. Hopefully the strike will be settle soon:)
For this term test, I managed my time efficiently so I did not rush during the test as the first one. However, I did not feel confident about this test...I must say that the biggest failure is that I did not prepare for the part of definition of Tree(question #1 on the test). I overly relied on the past test so I did not think about such question will be on the test. Luckily, I went through the inorder/preorder/postorder traversal once so I have done the order question right(hopefully).
Due to the TA's strike, we still do not have a chance to get our tests back to see what we did wrong. Hopefully the strike will be settle soon:)
Saturday, March 14, 2015
Week 8 Linked Structure
Week 8 is all about linked structure. Unfortunately I was sick on Monday, so I did not have a chance to be introduced to this new topic. When I returned to the Wednesday's class, I was stunned by the concept of linked list and all its methods. The only thing that was understandable was the diagram. It gives me an overall understanding of linked list and how each node in the list relates to each other, and perhaps how it works.
Because of the absence of the first lecture of linked list, I spend extra time reading the course note and slides. I find the most helpful way to understand and solidify the linked structure is the lab, though due to the strike the lab was cancelled. By following those codes, I can gain better comprehension of those methods including the ones that once stunned my during the lecture. I also find that drawing diagram is extremely helpful to both comprehension and implementation of the code. Here is one of the diagrams I drew to for the append method:
Drawing graph gives me a visual understanding of how the method work; sometimes it also gives me hints to solve similar problems as well.
Wednesday, March 4, 2015
Week 7: A Challenging BTNode Method
In week 7, there are more about recursive methods and the Tree class. The contents of lectures are clear and easy to understand. However, for the first time I feel the lab exercise is challenging. Both my lab partner and I struggled to implement the method list_longest_path(node). This method supposes to return a list of the data of a longest path of the node. We started with an if statement that indicates the base case:
if node is None:
return []
Then we also found cases that do not need recursions, which is the Tree only contains one leaf(the length of the path is 1):
elif is_leaf(node):
return [node.data]
So far we were confident and clear. However, what we did not notice is that, besides the case above, there are two more cases that we could implement directly without recursions(the length of the path is 2); and these codes are very important for the recursion to work:
elif node.right is None:
return [node.data, node.left.data]
elif node.left is None:
return [node.data, node.right.data]
With these codes that construct a loop for the recursion to work, we finally successfully implemented list_longest_path(node) method:
else:
left = list_longest_path(node.left)
right = list_longest_path(node.right)
return [node.data] + left if len(left) > len(right) else [node.data] + right
The main problem we encountered was that we always forgot to contain the node.data of the parent tree in the list. We also had a hard time figuring out how to make the program choose the longer path amoung node.left and node.right.
There might be tuns of similar problems that I will encounter in the furture, but the ideas of implementation are the same. Therefore, understanding the essentials of implmenting recursive methods will be extremely helpful for me in my furture programming experience.
if node is None:
return []
Then we also found cases that do not need recursions, which is the Tree only contains one leaf(the length of the path is 1):
elif is_leaf(node):
return [node.data]
So far we were confident and clear. However, what we did not notice is that, besides the case above, there are two more cases that we could implement directly without recursions(the length of the path is 2); and these codes are very important for the recursion to work:
elif node.right is None:
return [node.data, node.left.data]
elif node.left is None:
return [node.data, node.right.data]
With these codes that construct a loop for the recursion to work, we finally successfully implemented list_longest_path(node) method:
else:
left = list_longest_path(node.left)
right = list_longest_path(node.right)
return [node.data] + left if len(left) > len(right) else [node.data] + right
The main problem we encountered was that we always forgot to contain the node.data of the parent tree in the list. We also had a hard time figuring out how to make the program choose the longer path amoung node.left and node.right.
There might be tuns of similar problems that I will encounter in the furture, but the ideas of implementation are the same. Therefore, understanding the essentials of implmenting recursive methods will be extremely helpful for me in my furture programming experience.
Sunday, March 1, 2015
Recursion
Recursion is a tricky but really fun part for me in the study of computer science so far. I am fascinated by the idea of repeating itself within itself, though this idea is also a little complicated to understand and apply. Recursion is very convinient in programming since it simplifies and divides the problems into parts and solves them part by part. It saves lots of unecessary codes and is able to solve extremely complicated problems by several simple codes.
During the lectures we learn and understand recursion by tracing it, from the simplest base cases to the more complicated ones. The first recursive method we encountered is sum_list. We first take a look at an extremely easy example call such as sum_list(27), which the argument is an int rather than a list. So that we can simply figure out the condition for recursion. Then we can clearly see how it works for a list, such as sum_list([1, 2]) and a nested list, such as sum_list([1, [2, 3]]), and so on.
With the understanding of recursive methods, now we are able to implement them and apply them! Though the first implementation of a recursive method takes me about an hour to solve it, applying recursion to some methods will become easier after some practice. In last week's lecture, we've tried to implement BYNode.evaluate() method using recursion. I find that it is easier to solve the problem by thinking about the base case. After solving the base case, consider a typical example that needs the idea of recursion.(Agreed by another SLOGer) This is the most difficult part since it is the main part of the function that requires lots of thinking and deep understanding of the method. When both 2 parts are done, we can write them in the 'if...else' form.(We can also check whether the code is correct by tracing them.)
During the lectures we learn and understand recursion by tracing it, from the simplest base cases to the more complicated ones. The first recursive method we encountered is sum_list. We first take a look at an extremely easy example call such as sum_list(27), which the argument is an int rather than a list. So that we can simply figure out the condition for recursion. Then we can clearly see how it works for a list, such as sum_list([1, 2]) and a nested list, such as sum_list([1, [2, 3]]), and so on.
With the understanding of recursive methods, now we are able to implement them and apply them! Though the first implementation of a recursive method takes me about an hour to solve it, applying recursion to some methods will become easier after some practice. In last week's lecture, we've tried to implement BYNode.evaluate() method using recursion. I find that it is easier to solve the problem by thinking about the base case. After solving the base case, consider a typical example that needs the idea of recursion.(Agreed by another SLOGer) This is the most difficult part since it is the main part of the function that requires lots of thinking and deep understanding of the method. When both 2 parts are done, we can write them in the 'if...else' form.(We can also check whether the code is correct by tracing them.)
Subscribe to:
Posts (Atom)
4.jpg)