Week 12   Last Impression on CSC148

l   Lecture material this week

The topic we covered this week is time efficiency and big-Oh, which I’ve

learned in CSC165 last semester. Because of the second-time learning, they were relatively easy to me.

1) The formal definition of O and Ω

Important trick:

2) running time of code

ü   sequence

running time: constant

nums = [n, n, n]

x = sum(nums)

y = x + n**(1/2) - 42

print('total is: {}.'.format(x + y))

ü   loop

running time: n

total = 0

for i in range(n):

    total += i

print(total)

ü   two loops

running time: n^2

total = 0

for i in range(n):

    for j in range(n):

        total += 1
print(total)

ü   conditional loop

running time: log(n)     ß the part I didn’t know before

total = 0

copy = n

while (copy > 1):

    total += 1

    copy = copy // 2
print(total)

l   The valuable knowledge I learned

In the beginning of this semester, we introduced the abstraction data type (stack, queue, Tree, etc.), which almost including all topics of this term. Under this big topic, we learned class and its subclass, and focused on how a child class inherit, extend, and override from it parent class. Assignment 1 took fully advantage of application of this part. Under the parent class “GameState”, we built a child class for game “subtract sqare” named” SubstructSquareState”. It inherited basic information from its parent class, extended distinct function into itself and overrode the different parts from GameState class. SubstructSquareState was designed only for game “subtract sqare”, but GameState can be used for any games.

The next crucial part we covered is the recursion applied in different typical data structures (list, Tree, Binary Tree, Binary Search Tree, LinkList, etc.). Recursion is a strategy to address problems, in which first we think about the base case, then the recursive steps. Combined with list comprehension, we recur list using this framework: [<function name>(x) for x in L]. As for Tree, we usually use leaf as the base case, and then plug this in to figure out recursive steps. Binary Tree and Binary Search Tree are the special case for Tree, hence we can think in the same way. Because they introduce some special properties (Binary Tree: branching factor of 2; Binary Search Tree: order), we can add appropriate conditions in front of the recursion to avoid unnecessary step and to become more efficient.

l   What I need to improve

My largest struggle but the most interested part is recursion in this semester, which is similar to Rod Mazioomi (http://rodcsc148.blogspot.ca). We both still cannot totally handle recursion and apply it perfectly. I am easy to stuck into a endless loop thinking. I think I still need time to find my own way to finish the recursion quickly and precisely. And I will try my best to think problems in different ways when I write the recursive codes.

Overall, just like what Christian Garcia wrote: “I am just at the beginning of my journey” (http://christiangarciacsc148.blogspot.ca/search?updated-min=2015-01-01T00:00:00-08:00&updated-max=2016-01-01T00:00:00-08:00&max-results=9). Thought this semester, I’ve already experience this magic splendid coding world. Although I am not a student in computer science major or specialist, I will continue the computer science study to explore my potential in this brand new field!

Last but not least, thanks for the help from my professors and my TA! Again, thank you very much!!! ;-) 

Week 11   Revisit an Earlier SLOG Posting

This semester is going to finish and we just left only one-week lecture. I looked back to all my postings. I realized, in retrospect, that the recursion used in almost every single key data structure we learnt (List, Tree, Binary Tree, etc.) Therefore, this entry I would like to revisit my slog week 5: tracing recursion, and talk about recursion more.

l   Further understanding on recursion

On my previous slogs, my fundamental definitions and understanding about Recursion was basically correct, but a little narrow. At that time, I only learned the tracing recursion and recursive codes in the lists. And up to now we touched the recursive application in many data structures, such as the Tree, Binary Tree, LinkList and so on. Recursion is a type of mathematical thinking, which can be flexibly used in varies kinds of problems, not just in computer science.

l   Progress from then on  

From the previous slog, I wrote: “the biggest hardship I encountered was writing recursion myself. I found a stupid way to overcome, that was, used for loop first, and then transferred it to recursion approach.” At that time, I felt confusion and not self-confident on coding recursion. I could only indirectly think the problem, not recursively. But this injudicious method was limited to simple questions. What’s more, it lost the real meaning of using recursion, which is solving problems efficiently and conveniently. I attempt to flatten the data structure, which produced redundancy in running time. However, due to all kinds of applications and a number of practices on labs or assignments, I got a clearer sense on whether a recursion should be used, and obtained stronger skills to apply recursion into practice.

Assignment 3 this time is about this problem. It is aimed at building our skills of coding efficiently and avoiding repeating. In the beginning, I just flattened the entire tree into a list at the outset and then traversed the list instead of traversing the tree. That was because it was really easy to think and to transfer into codes. But after forbade by professor, I tried to keep track of the game states I've seen so far and to traverse the tree directly, which was really painful to me and I always couldn’t get out of my inaccurate pattern. Thanks for the discussion on the piazza and professor’s office hour, we found the way to resolve them gradually.

For instance, counting_distinct_node:

        As can be seen in diagram①, the old approach I used was to return all the nodes of the tree into a list first, and then picked the distinct nodes from that list.

        The method I improved later was to building an inner helper function to recur the tree, and then it produced the outcome straightforward in the main function. It is worthy to mention that I used data structure “set” instead of “list”. Because when you add two same values in the set, it will keep only one of them, which would be very efficient.

l   Reaction to other’s slog

http://christiangarciacsc148.blogspot.ca

I really appreciate Christian Garcia’s posting, since they are quite clearly and readable with excellent paragraph distribution and some interesting pictures.

He also chose to revisit a slog of recursion, same as me. He summarized lots of helpful frameworks and their characteristics, which I agreed with. However, these frameworks will not help a lot when we encounter the complex questions. In my opinion, we do not necessarily dwell on the frameworks of every step. The most important thing is to understand it, and recreate it by codes.