Blog Post # 10 ~THE END~

Blog Post # 10 ~THE END~

Hey all my classmates, TAs,

        It has been a fun and rewarding study term with all of you. I'm glad I made this far. Waking up early three days a week for 9am lectures and lab is definitely not a easy task. And I'm proud to say that I attended every single lecture throughout the term YAY(except the first two lectures when I was still in CSC108).  CSC148 is definitely a challenging course for a not-so-experienced programmer like me, which is why I learned so much and my programming skills improved a lot in this short period of time. 

       Here I will list three of my most proud of accomplishments (don't laugh lol):

      

                1. Finally I'm not scared of recursion and I'm able to code recursively !!!

                

                2. Getting used to using Exceptions 

                3. Learned to code my own test cases (this is so cool~)

    

        Again, thank you Danny for explaining everything so detailed both in lectures and office hours, thank you to all the TA's for answering my question in lab and help centre, and thank you to my classmates to answered my question on pizza. 

        I want to congratulate everyone on their accomplishments and wish all of us can achieve a satisfying grade on the final exam!!! And to those who wants to pursue a minor in computer science like me, I wish you all the best in getting a 75+. ^_^

Blog Entry #9 Assigned Topic

Blog Entry #9 Assigned Topic


Danny has assigned the topic on our last week's SLOG, which is based on quick and merge sorts and their performance. I have already written on this topic, please refer to Sorting and Performance :)

As I was reading my classmates' blogs, I found out some of classmates used visual representations to demonstrate the concept, such as @DPereira (http://dpslog.blogspot.ca) and @justincompsci(http://justincompsci.blogspot.ca), personally I think that's very impressive! And I will try to use more pictures to aid my future blog posts.

Blog Entry #8: Namespaces

Blog Entry #8: Namespaces

         Namespaces are the fundamental idea in Python. I used global names a few time when I try to update the a variable inside a function. After this week's lecture, I realize I did not completely understand this concept in the past, so I did a little bit research on namespaces to improve my understanding. In this blog post, I will briefly talked about what I have learned from the lecture and research.

          One advantage in Python is that you can apply a name to any variable, unlike in other languages such as Java you are required to define the type of the variable first. You can assign the same name to a value and a function, and Python can recognize the type when you call the name.

          For example:
          var = 148
          var =  "I love CSC148"
          var = ["I", "love", "CSC", 148]
          def var():
                ...

          According to the Python tutorial, a namespaces is a space that holds a number of names. They are a mapping from names to objects. Each namespaces is completed isolated. Similar to the example above demonstrates, you can have a module called  Integer and a module called Float and both could have a function named calculate().  You can access the names using prefix such has Integer.calculate() or Float.calculate().

          Another useful concept is scoping. A scope refers to "a region of a program from where a namespace can be accessed without a prefix". Namespaces are also searched for names inside out. If there's a certain name declared in the module's global namespace, it can be reused inside the function.

         Python looks from the innermost scope, which is usually a function, enclosing scopes, global (__main__), to built-in names. You can force the program to access the name by prefixing the name with keywords such as global.

Blog Entry #7: Assignment 2 Part 2

Blog Entry #7: Assignment 2 Part 2

         In last week's blog I divided the assignment 2 into two sections, representation the tree and the matching with a regular expression. This week I will continue discussing the solution to assignment two.

Case # 1: when there's only one character in the tree (e.g. '0', '1', 'e'), in this case, check if the string given is the same as the symbol of the tree, and if the symbol is 'e', allow the string to be empty.
           
               return s == '' if (r.symbol == 'e') else s == r.symbol

Case # 2: when the symbol is '|', either the left child has to be the same as the given string, or the right child has to be the same as the given string, or both if the two children are identical.
 
               return match(r.children[0], s) or match(r.children[1], s)

Case # 3: when the symbol is '.',  the given string only matches the tree if the given string can be divided into two parts, and part one matches the left child, part two matches the second. One problem that I had while coding this case was that when I applied recursive strategy to the coding,  mostly likely the left child and right child will be another complex tree with its own children. Therefore, I cannot just simply divide the string in half which also implies the length of the string is not exactly 2. It could be less than two if the child is 'e' (empty), or more than two is the symbol of the children is '.'. My solution is to divide the string in all possible ways and tests each single case using the recursive strategy.

               for i in range(len(s) + 1):
                      if match(r.children[0], s[:i])  and match(r.children[1], s[i:]):                      
                             return True
              return False


Case # 4 the starNode : firstly I have to admit that I had some troubles getting this right. I tried several strategies and finally got my code working; however, my solution might not be the most efficient one. As the instruction indicates, the string matches the regex if the string is empty. A complex regex also needs to be taken as consideration. For example, if the expression is '(a|b)', the string can be 'aaaaa' or 'bbbb'; another example would be if the expression is '(a.b)', then the string can be 'ababab'. In the case where a dotNode is combined with a batNode, the result could be even more complicated; Therefore,

                if  s is None:
                       return True
                elif isinstance(r.children[0], DotNode):
                      for i in range(len(s)):
                              if match(r.children[0], s[0: i + 1]):
                                     return  match(r, s[i + 1:])
                      return False
               else:
                      return True if False not in [match(r.children[0], i) for i in s] else False

Blog Entry # 6: Assignment 2 Part 1

Blog Entry#6: Assignment 2

Nov 13

Hey Everyone, how was fall break? And more important how was term test?
Personally I felt a bit relief because I started to review last night and today's test was not as hard as I imaged xD.
@Rahul Chaudhary (http://rhlcy.blogspot.ca) also mentioned in his blog that the term test went well because he followed Danny's advice and reviewed all labs and exercises. I guess because I put a lot of efforts in all my exercises and labs, and the hardwork paid off :)


      In this week's SLOG, I will share some of my opinions on the assignment 2 which was due last week. Feel free to leave any comment and I will be excited to read them!



      This assignment consists two major tasks, and the first one is to take in a regular expression (a string) and represent it as a tree (object). Leaf nodes are represented by RegexTreeNode() '0' or '1' or 'e', and internal nodes are represented by subclasses of RegexTreeNode() such as StarNode() '*', BarNode() '|', and DotNode() '.'.
   
      In the __init__() method, I first store every character in the given regular expression in a list.
 
                self.regex = [i for i in regex]
   
      And then I find all leaf nodes '0', '1', 'e', and stored them as RegexTreeNode.

               for n in self.regex:
                     if n == '0' or n == '1' or n == 'e':
                              self.regex[self.regex.index(n)] = RegexTreeNode(n, [])

     Now here's the hardest part (I think): when the size of my list is one, I don't have to do anything (e.g. [ RegexTreeNode('0') ]); when the size of my list is two, I must have a StarNode (e.g. [ RegexTreeNode('0'),  '*' ]); when the size of my list is greater two, I must have a complicated string that involves parenthesis ([ '(',  RegexTreeNode('1'), '|', RegexTreeNode('0'), ')' ]). The first two cases are simple to resolve, so I will elaborate on my solution for the third case. I start by looking for the first right parenthesis, and its corresponding left parenthesis by reversing the sublist before the first right parenthesis and find the first left parenthesis. Given the two indexes for the parenthesis, I can build a tree from the content inside, and replace the parenthesis and its content with this tree. and of course I have to recursively call the function to solve the rest.

      if len(reg) > 2:
                right = reg.index(')')
                left = right - reg[:right][::-1].index('(') - 1  
                temp = reg[left + 1:right]
                reg = reg[:left] + reg[right + 1:]      
                reg.insert(left, create_tree(temp))              
                built_tree(reg)

       create_tree is a helper function that I use to construct the tree from the content inside the parenthesis. There are 2 case, either the content has 3 characters (one node and two children), or it has 4 characters when a starnode is involved.

       if '*' in temp:
                star_ind = temp.index('*')
                star = StarNode(temp[star_ind - 1])
                temp = temp[:star_ind - 1] + temp[star_ind + 1:]
                temp.insert(star_ind - 1, star)
                return create_tree(temp)
            elif '|' in temp:
                return BarNode(temp[0], temp[-1])          
            elif '.' in temp:
                return DotNode(temp[0], temp[-1])
            else:
                return temp


        So up to this point, the first part of this assignment is completed. I think  my solution might not be the most simple way of solving this problem, but at least the logic is pretty sound. Please comment below if you have any question or opinion on this topic.

Blog Entry #5 : Sorting and Performance

Blog Entry #5: Sorting and Performance 

Nov 4th - Nov 9th


        In last week's lecture, we "reviewed"  a few sorting algorithms: selection sort, merge sort, and quick sort. In this week's blog, I will briefly talk about each sorting methods and its performance.

Selection Sort
       The algorithm behind selection sort is fairly simple: keep finding the smallest item and swap it with the replacing item.

    L1 = L[:]
    for i in range(len(L1)):
        m = min(L1[i:])
        j = L1.index(m,i)
        L1[i], L1[j] = L1[j], L1[i]
    return L1

     
       In the average case scenario, the code will run n times to find the first smallest item, and then (n-1) times to find the second smallest item, and then (n-2), (n-3)...2,1. In total, the program runs n (n-1) / 2 times, therefore the performance in big-oh notation is O(n^2). In my opinion, even selection sort on average is not as efficient as quick sort or merge sort (which I will explain in more details later), the coding itself and the algorithm are much simpler. Also the performance t is always O(n^2) no matter the given list is sorted or not.

Merge Sort
       Merge sort is based on the divide-and-conquer paradigm.
     
       Step #1; Recursively dividing the given list into n sublist, each containing 1 item

           if len(L) < 2 :

          return L[:]
      else :
          return merge(merge_sort(L[:len(L)//2]), merge_sort(L[len(L)//2:]))

       Step#2: Sorting all sublists

        while L1 and L2:

          if L1[-1] < L2[-1]:
              L.append(L1.pop(-1))
          else:
              L.append(L2.pop(-1))

       

        Step#3: Combining all sublists

        The average and best cases performance for merge sort are both O(n log n). To sort a given list N with n elements, 2 lists N1, and N2 (half size of the list N) is recursively sorted plus n steps to merge them back to one single list. However, while I was searching various sorting methods and its performance online, I found it interesting that natural merge sort (a sequence of ascending than descending numbers) only takes O(n) running time on a sorted list. 

Quick Sort

       Quick sort is also known as partition-exchange sort, and the idea behind it is to recursively choose any item as the pivot and sort the list by items smaller than the pivot, pivot, and the items greater than the pivot. 

      

      Similar to merge sort, the average performance of quick sort is also O(n log n), it takes O(n) to call the pivots and recursively calls two half-sized sublist.

      In theory, the pivot can be any item in the list. However, the best decision of pivot can divide the list into two equal (or almost equal) halves, and the worst case of scenario is that one of the two sublist is empty. Clearly the choice of pivot have a great impact on the performance. 

       

quick([x for x in L[1:] if x < L[0]])

                + [L[0]] + quick([x for x in L[1:] if x >= L[0]])

     The exercise we did in class simply assume the far left element as the pivot. Unfortunately, in this case, if the given list is sorted, it will create the worst case performance O(n^2).

        

Blog Entry #4: Linked Tree....more trees

Blog Entry #4: Linked Tree...more trees

Oct 29th 

      Another week of studying on trees, this week we learned about the linked tree which is a special case of a tree, with branching factor of 1.  The data structure is built on one node with the next node that it links to. And we also implemented Stack with linked tree. However, I do have a few questions regards to the application of the linked tree. Since the branching factor is 1, what is the difference of storing the data in a list and a linked tree?

     Now moving on this week's exercise, personally I think exercise 5 is fairly easy. Part a requires to recursively set depth to the node and call the same function on its children and add 1 to the new depth. And part b requires to recursively check if both left and right child are empty to determine if the given node is a leaf or internal node, and repeat the process on its children if the given node is an internal node. In addition, I found Monday's lecture very helpful, especially the example with a function inside the function that can be called recursively (sorry if my wording is a little confusing, I can't remember the technique term of this method). When I try the exercise at the beginning, this method did not occur to me and I encountered errors when I attempted to call the set_depth function by calling the whole class.

    I'm glad to see that I've been making some progress in this class, and also a little surprised to realize how much I learned in only 6 lectures. At least I'm getting very comfortable coding with recursions. Back in high school, recursion really intimidates me and for one moment I thought I would never be able to apply this logic. But now I finally start to see the convenient of using recursions and how neat and simple the code can be written this way.

Please leave you comment below, feel free to give me any constructive feedback or you can just say HI. :)