review on a previous post

Time slipped. This term is drawing to an end. Looking back, I have learned a lot about OOP and resolved quite a few puzzles along the way. And by reviewing my slog, I could recall all these precious experiences. Here I would like to review a previous post Recursion Continued, in which I discussed about recursions used in trees and recorded my understandings and puzzles at that moment.

When I was writing the post Recursion Continued, we had just been told the concept Recursion for about 2 weeks and were still spending a long time tracing recursions. In the lab that week, it was my first time writing recursions and things didn't turn out as expected. I thought that since I understood the course materials quite well and traced recursions without much efforts(despite some careless mistakes sometimes which I could almost avoid later), the implementation shouldn't be a big problem and the idea behind those methods seemed explicit. Whereas, when it came to writing codes in the lab, I got quite stuck so I turned to my TA and he led me through the whole process with patience, from tracing the base case to completing the entire method. So next time, when I got stuck, instead of frowning, thinking hard to seek for codes that will work, I would rather start by doing easy tasks like tracing which enhances my  understandings while encourages me. As I said in the previous post, First, we need to think about the base case, that is when the case is simple enough not to require recursion. Then we need to write codes for the whole tree, going through every node and calling functions on it. 

While I was doing assignment 2 with my group mates, I remembered one of our group members came up with a solution but we didn't know how to write it down and to be honest I couldn't explain it very clear myself though I could roughly understand it. At that very moment, we started by tracing basic case, then cases a bit more complex, after some time, I felt like I could fully understand what we were doing. Once we got the full picture of the problem to be solved, the tackling of it came natural. 

Another thing to mention, when I was reading my fellow students' slogs, http://celinajiangslog148.blogspot.ca, http://egq148.blogspot.ca, http://csc148danjessicali.blogspot.ca(my favourite 3) I found their ideas quite instructive and their summary on the topics deepened my understandings on the course materials. 

impressions of week 9

impressions of week 8

impression on week 7

This week we talked about binary search tree. It is a special kind tree in which every parent node has at most two children.
                 

’’’Binary Tree node.’’’  

    def __init__(self, data, left=None, right=None):
        ’’’ (BTNode, object, BTNode, BTNode) -> NoneType

        Create BTNode (self) with data
        and children left and right.
        ’’’
        self.data, self.left, self.right = data, left, right

We have different implementations for binary search tree which 

seems not that difficult to understand since we can always refer to a graph if feeling confused. Many things told were similar to those 

talked about in last week's lectures. The new stuffs introduced were about the travelling of trees.

There are 3 orders : inorder, preorder and postorder 

1. inorder

from left to right and recursively

if root is None:
    pass
    else:
        inorder_visit(root.left, perform)
        perform(root)
        inorder_visit(root.right, perform)

2.preorder
from the root to the leaves and recursively

perform(root) 
preorder_visit(root.left, perform)
preorder_visit(root.right, perform)

3. postorder
from leaves to the root and recursively

preorder_visit(root.left, perform)
preorder_visit(root.right, perform)

perform(root) 

summary of Abstract Data Types

We have been talking about Object-oriented programming since the start of this semester. Over the time, with lots of examples and practice on it, I feel much more comfortable with this way of  coding. Actually it is just what it sounds like. Object oriented programming (OOP) is based on creating on objects and writing methods to create data structures that store and manipulate data. With OOP, you are not limited to default object types built in to a language, for instance, lists, strings in python. It has a clear structure, make it possible for everyone to understand what your code does and use them on their own, which makes our real-world jobs more efficient.

Until this week, we have been told 3 types of Abstract Data Types. And here I will give a brief summary on each of them. 

1. stack

A stack contains items of various sorts. It stores data in an order that new items are pushed on to the top of the stack, and  items may only be removed from the top of the stack. Thus, an abbreviation LIFO which stands for ''last in first out'' is used to describe it. When the stack is empty, you can no longer ''pop'' it. With stack, we can check for balanced parentheses which was displayed during lecture(refer to class notes), and the application gives a better understanding on the implementation and uses of stack. Basically, a stack is like a pile of books, every time you add or remove one from the top, and you can tell what the top item is and how big the entire stack is.


2. queue

In comparison with stack, queue stores data in the way of ''first in first out'' (FIFO). 
We practiced implementing queue in the lab. Similar to stack, queue has methods of adding and removing items called ''enqueue'' and ''dequeue''.
And it also has a basic method to check if queue is empty. Besides these
three basic methods, queue could be implemented with  other methods depending on the specific situation. 


3. tree

Tree is a great way of manipulating data, it can represent hierarchical relationships. A tree is a set of nodes connected by edges. There are children nodes and parent nodes. Each node has exactly one parent, except the root. In this picture, root is the node containing value 1. And
node with no children is called a leaf. As is shown, the node containing value of 6 is a leaf.
Trees are made of recursions! A tree contains several sub-trees within it, round and round, just like recursion.To illustrate, in the picture shown in the right, we have a tree with the root 1, but we also have a subtree with root 2, and so on and forth. For me, one important thing is to understand the basic structure, never overthink about it! Sometimes drawing a picture helps a lot.

Recursion continued

Cheers, everybody! Reading Week is coming!

Before taking a good rest, I would like to do a brief review for what we've talked about this week.

We learned a new concept "tree" during the lecture. Below is an example of a tree:

There are a lot of terminologies associated with Tree . As a reminder, a tree has root, nodes, edges, height, leaves and subtree. And there are paths and lengths of those paths. The definitions of those terminologies are explicitly explained in Week 5 slides posted on the course website, and I will not present it in this post.So far, the terminologies are fairly easy to understand.




Later, we were given a few examples of implementation of Tree methods, like the counting of leaves and height of the tree, looking for the maximum number of branching factors, determining whether the tree contains a certain value. In all these methods, we used  recursion. First, we need to take a look at the base case, that is when the case is simple enough not to require recursion. Then comes the real challenge. We need to write codes to examine the whole tree, that is to go through every node(in some cases, we just go through some particular nodes) in a tree and call the function on it. To make it easier, before writing codes, we traced smaller trees in class. Then we combined the smaller instances to get a solution which worked for the entire Tree.

In this week's lab,  we practiced using recursion in Tree. Though I understood the course materials, I found it hard to write the recursion myself. I got stuck with a problem in the handout for almost thirty minutes, and felt really bad at that moment. Fortunately, my TA was really nice. I asked him for help, with great patience, he guided me to trace smaller examples and explained the whole thing clearly. Now I feel much more comfortable with writing recursions.  But, I'm far from doing without problems,  I still need a lot of practice and plenty of time to try to catch up. The coming reading week seems a good opportunity for me. Hope I will get better with some additional practice. 


Wish everyone a good reading week! :)

tracing recursions

We started talking about Recursion last week. Recursion is a quite interesting idea, which requires adequate amount of thinking and can simplify the loops by a lot if used properly. And I guess Danny must be loving it, since it's such a "lazy" way of writing codes.LOL

When I first heard this idea during lecture, a few sentences came to my mind:
To see a world in a grain of sand
And a heaven in a wild flower,
Hold infinity in the palm of your hand
                                              And eternity in an hour.

It may sounds nonsense, but personally I feel there is a correlation. Recursion is just like a sand, inside you find a whole world, and inside that world you still have a sand, and it loops. However, in recursion, you will finally reach a point where you can exit the loop.

We focused on tracing recursions last week, here is a brief example:

def sum_list(L):
    ’’’

    (arbitrarily nested list of int or int) -> int
    Return the sum of all ints in L.

    >>> sum_list([1, [2, 3], [4, 5, [6, 7], 8]])
    36
    ’’’

if isinstance(L, list):



        return sum([sum_list(x) for x in L])   # calls isinstance(), sum(), sum_list() methods 

else:

        return L              # base case

1.sum_list(27) --> 27      ＃ int, depth(0)



2.sum_list([4, 1, 8]     --> sum( [ sum_list(4), sum_list(1), sum_list(8) ] )

                                     --> sum([4, 1, 8])

                                     --> 13                           # depth(1)



3.  sum_list([4])    --> sum([sum_list(4)])      




         -->sum([4])
         --> 4

4. sum_list([]) --> sum(sum_list(x) for x in [])
           --> sum([])     
           --> 0




5. sum_list([4, [1, 2, 3], 8])  --> sum([ sum_list(4), sum_list([1, 2, 3]), sum_list(8)])  

                                                    # already traced depth 0 and depth 1

                                                    --> sum([4, 6, 8])

                                                    --> 18




6.  sum_list([[1, 2, 3], [4, 5], 8])  --> sum([sum_list([1, 2, 3]), sum_list([4, 5]), sum_list(8)])

                                                      # already traced depth 0 and depth 1

                                                      --> sum([6, 9, 8])

                                                      --> 23




7. sum_list([1, [2, 2], [2, [3, 3, 3], 2]])  --> sum([sum_list(1), sum_list([2, 2]), sum_list([2, [3, 3, 3], 2])])

                                                               # already traced depth 0, depth 1 and depth 2

                                                               --> sum([1, 4, 13])

                                                               --> 18




8. sum_list([1, [2, 2], [2, [3, [4, 4], 3, 3], 2]])  --> sum([sum_list(1), sum_list([2, 2]), sum_list([2, [3, [4, 4], 3                                                                                , 3], 2])])

                                                                          # already traced depth 0, depth 1, and depth 3

                                                                          --> sum([1, 4, 21])



--> 26



First, be clear about the base case. 

Then just trace the recursion step by step, and we use the results before, otherwise the tracing will be too long.

impression for the first few weeks

In the last few weeks, we learned a blast about object-oriented programming.We started with object-oriented thinking and basic concepts in ADTs. Then we learned how to implement classes, both supper classes and subclasses. And this week we talked about recursion ---- my favourite topic so far. 

Though most of my friends said there had not been any real challenges till now, I was feeling kind of overwhelmed for the first two weeks. More than once I found myself confused during lectures, which never happened in CSC108 last semester. After class, I had to refer to both instructors' lecture slides to grasp the materials. Then I would read related chapters in course notes. But obviously this made my attendance to lectures meaningless. So I changed my strategy. I chose to read course notes before class no matter how busy I was, then what discussed in lectures finally made sense. I have to admit that preview does matter to me, we had video flips for 108, but for 148 course notes are the only resources for me before classes. At least, I feel much more comfortable during lectures now.

What impressed me most was implementation of generic classes and subclasses. This was our focus for the second and third week, and also it was a major part for assignment 1. As reading my fellow students' slogs, I came across one explaining this topic explicitly, which I would like to recommend.
  
The writer basically mentioned 3 things: 1. the init method for the subclasses  2. NotImplementedError for the generic class  3. different syntax for generic class and subclass. Those were quite good points, and I believe inheritance the most important for this part. Here is something I would like to add based on my working on the assignment and practice in the lab.  

1. When designing your classes, you should be clear about what methods you will have in the generic class. The use of these methods should make sense in every case(subclass). To illustrate, in assignment 1, methods in generic GameState work for every game, not just Subtract Square. So we have a generic game strategy, a generic method to decide who's the next player... But we need to be aware that there is no mention of a specific game in the generic methods.

2. The doctest for generic classes and subclasses. We can find good examples on the course website like shape.py, triangle.py and square.py. And remember to write in subclasses the descriptions of methods inherited from the generic class.

week 3 slog starts

Assigned topic: Why geeks need to know how to write

• a computer programmer should have the basic skill to write explicit comments and documentations for his/her code so that other programmers can understand and use it, otherwise the code is of no value.

• writing comments for the code and keeping a debug journal provide themselves with future references and will save them time when encountering a similar problem. 

I was writing slogs for a whole semester for CSC165, and to be honest it still kind of frustrated me when I heard that slog would be back for CSC148. Though it indeed took me quite a long time to write and read through my fellow classmates' posts every time,  I have to admit writing on a weekly basis has benefited me in several ways:

1. Writing deepens my understanding on course materials. 

This is concluded based on my own experience in CSC165. Each time before starting to write,  I would draw an outline of new materials learned in the past week, both in lectures and tutorials, and also some interesting and informative topics I have come across in the course notes. While writing,  I got a chance to process what discussed in the lectures and  to relate it to my own learning experience. This may span several posts, for example, I may relate a debugging experience to what I learned several weeks or months ago. Besides, what I found helpful was that I could always find out some new problems otherwise would be overlooked by writing down those key points in my own words and reading my classmates' posts. It is always a good idea to learn and seek help (after pondering) from others, especially from my smart fellow classmates.

2. Slogs serve as good resources for later review.

I have read all the logs from the links posted on the course website. Several of them mentioned the same topic that debug notes come in handy and save you a lot of time. Since the same bugs would probably reappear, also the notes give you an alert for your mistakes and reduce the chance you make them later programs. When I was writing for CSC165 last semester, I preferred writing a summary when we finished a chapter. Normally I would write about the general ideas introduced; typical problems and general methods to solve them; common mistakes; my own difficulties while learning and how I solved them, etc. For this semester, I guess, apart from the above, I would also include a fair amount of debugging notes for future reference. 

3. Writing and reading slogs develop my English.

Even if having writing slogs for a whole semester, I still find myself struggling for what to write LOL.  And for someone like me whose mother tongue is not English, it seems that keeping a journal in English is a short-cut to improve writing skills. I don't know whether it is true, but as far as I'm concerned, I just don't see any improvement in my own writing styles(here I mean the precision and elegance of language), whereas in terms of organizing, I guess yes. Besides, browsing others' posts enlarged my vocabulary. More often than not, I would learn some new phrases and oral expressions.