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.