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!!! ;-)