Week 10 Frustrated With Markus

I have absolutely no idea why i got ZERO for week 7 SLOG and my remark form for week 3 has yet been looked at.  In the SLOG handout it said that i just have to write A paragraph or so on the assigned topics but I am pretty sure i went far beyond that. I spent my whole Friday for week7 SLOG, in which i described in detail the advantage of using recursion over iteration. I think my topic fit nicely with the assigned topic for that week which was "recursion". So even if you disagree with some of the contents in my Slog or basically don't like it , am i deserve at least 25% for following the instruction ? However, i don't think my SLOG just worth 25%. Beside from pointing out the facts, i also give plenty of demonstrations using code- that i made by myself- to back up my point. Moreover, i integrated the contents from several posts to prove my point, which don't think the professor event expect.

Another frustration is the A1 mark, while most of my friend already got their mark back, i am waiting like forever to see mine on Markus. Most people have at least 4 test reports for their A1 and i just got 1 that was post about a month ago. I don't really know what to do since i don't know how well my code run in later tests that i did not have the reports for.

But any way, let talk about an interesting problem that i encountered in the lab this week. The problem was that:

Source : Lab#9 handout

So we have to write a function named inorder which take a binary tree and return the root node of a linked list which is formed by in-order transversal of three. The problem would be much easier if we were allowed to use list or other container classes as intermediate storage site. However, we are not allowed to do so! Let walk through a very standard approach that helped me to solve such a hard problem like this:

Step 1: Assuming that we are allowed to use List as intermediate container. Let simplify the problem, what if you are asked to return the in-order transversal of the tree in form of List rather than LinkedList ? Then the solution will be very similar to this. 

def inorder2(r):
    return inorder2(r.left) + [r.item] + inorder2(r.right) if r else []

Step 2: I then asked myself that is it easy to convert a list into a LinkedList? The answer is yes.

def l_to_LL(alist):
    return LLNode(alist[0], l_to_LL(alist[1:])) if alist else None

 Step3: Although it is illegal , but we now can basically solve the initial problem by using the two function in step 1 and 2 as helper functions.

def inorder3(r):
    Tree_to_list = inorder2(r)
    list_to_LL = l_to_LL(Tree_to_list)
    return list_to_LL

 Step4: I look at my code and find a way to turn this illegal solution (since i use intermediate storage) into a legal solution. I note that list has a built-in __add__ function that can be used to concatenate one or more lists together and therefore make the task of turning a tree into a list in-order transversal so easy(Step1). It implies that if LinkedList also has an __add__ function that allows me to concatenate two LinkedList together then i can solve the problem without using any intermediate container. But we are not allowed to define another method inside the original LinkedList class, so i have to write a function 'add' that is outside of the LL class and force it to behave like the __add__ method in List. 

def add(root: LLNode, item: LLNode): # mimic the function add in list.
    old = root
    def _add(old, root, item):
        if root.link:
            return _add(old, root.link, item)
        else:
            root.link = item
            return old
    return _add(old, root, item)

def inorder(root: BTNode) -> LLNode:
    if root.left and root.right:
        return add(inorder(root.left), LLNode(root.item, inorder(root.right)))
    elif not root.left and root.right:
        return LLNode(root.item, inorder(root.right))
    elif root.left and not root.right:
        return add(inorder(root.left), LLNode(root.item))
    elif not root.left and not root.right:
        return LLNode(root.item)

The problem is solved!

The lesson i have from solving this problem is that by writing helper functions that  mimic Python list i can solve any similar problems that involve interaction between LinkedList and BinaryTree.

Extra# 3 cn! sorting algorithm

Using random class, i just make a very simple sorting algorithm that has the time complexity T(n) = O(cn!).

import random
a = [random.randint(0, 10) for n in range(10)]
print('initial list', a)
while not all([a[i] <= a[i+1] for i in range(len(a) - 1)]):
    random.shuffle(a)
print('sorted list', a)

Week 9

I got the busiest week ever for computer science. And until now, when I am writing this slog, there are still a bunch of stuffs that I yet completed. Let walk through everything happened this week.

In the lecture, we were talking about time complexity of different types of sorts. I know that most people would only focus on the most efficient types of sorts like selection, insertion or bubble sort. But I had a special interest in the type of sort that professor Heap called “horrible sort”. Horrible sort has running time ‘cn!’, and it is the second slowest type for sorting - according to lecture slides. I thought about it when I was in the bathroom this evening, and came up with an algorithm that I believe has time complexity of ‘cn!’. (Check out my extra post # 3)

The lab works for this week was heavy. We were asked to write just one method count_less(num) for Binary Search Tree class, which count the number of nodes that less in than num in the tree. The fun thing is that we not just had to write it once but 4 times using direct, indirect recursion and iteration. My partner and I managed to get the first three functions, which only used recursion during the lab hours. But I had no idea how to write such an iterative function that did the same thing as the recursive function since the ADT binary tree only favor recursion.

The e3 was much harder than e1 and e2. It took me a day to solve it last weekend and I thought that my codes were perfect. But when received my autotest result on Monday, it turned out that I failed ¾ of the test cases. At first, I thought there was a bug in my code but I was later informed that it was a mistake in the tester code and it was fixed. I got the second auto test this early morning, and again, another error was found, not in my code (I believe) but in the tester code. Its very annoying now since the deadline is tomorrow and I still not heard anything from the professor. I don’t know if I should to fix my code according to expected result of an invalid test case in the auto test file or keep waiting for the confirmation from the professor.

I’m suspecting that some of the test case used in auto test file was intentionally made to be invalid! Maybe, the professors just want to test how well the students understand the instruction or they may want to distract us from doing the second assignment, which due soon after e3. Who know?

Over the last few days, I have been working on the second part of assignment 2. My program so far looks promising. It ran smoothly for all of the extreme test cases that I made. Since, I already completed ¾ of the work and still have a week ahead, I feel pretty confident and hopefully it would be the one I have highest grade in!

It was everything that I want to say for this week! In week 10 Slog, I will talk in detail about the second part of this assignment in detail when the deadline for the assignment has passed.

Week 8

Week 8, it was the worst week ever since I came to U of T. I got below the class average after spending the entire last half of the reading week to review for the midterm. I misunderstood the last question and overthought the third question and ended up getting only 2 in both… I wish that I could have another chance but it is just a dream. But anyway, I am studying hard for revenge in the second midterm, which is coming up.

I also finished the first part of the assignment 2 on Monday, it was easier than I expected. I spent some time to work through the first two functions is_regex(s) and all_permutation(s) in part 2. The is_regex(s) seemed to be easy, but the second part when I have to produce a set of all permutations of s caused me a lot of problem. I don’t know if the professor will allow us to use permutation iterator in module intertools to solve that part, otherwise, it will be fairly complicated.

I also want to make some comments about the assignment 1. I read over the test file of the TA on Markus, I was really surprised that he/she used very large number of cheese. I even more surprised to realize that my tour function only gives the best number of moves for small number of cheeses, up to 10. But when it gets higher than 10, it will no longer produce the best number of move. I really don’t know where the bug is but hopefully I won’t lose too many marks for it. I also failed one of the two test cases for bonus part, which is a little bit disappointed.

In the lab this week, we have to mimic all of the functions of normal list by using LinkedList. I managed to get some of the extra question such as writing reverse, __eq__, copy_ll for LinkedList. By first drawing picture, I now have much better understanding about LinkedList and afford to do all of the basic recursive functions __setitem__, ___getitem__, … fairly quickly. I think my lab work is the only good thing in the entire week.

That are all I want to say about this week. Like usual post, I want to give my self a grade … 1 out of 5 probably is what I deserve since my term-test performance was not so good L

Week 7, Recursion Recursion!

Unlike usual post, this slog will be all about the assigned topic "recursion".

So what is recursion? it basically is a process of repeatedly breaking the bigger problem- which is either hard or seem like impossible to solve - to smaller problem which is easier to solve. It's more or less like the poof technique that i learnt in CSC165 called 'induction'. But in recursion, rather than proving the basis step, i have to find the solution to base case (often known as basis step of a recursive function). And according to blog.ezyang.com, i can use induction to prove whether my recursive function is correct since inductive hypothesis in induction behaves like recursive call in recursion! Which sounds very interesting but the prof didn't mention about it in CSC165, may be it was too advanced for the first year.

A question came to my mind when i first made a recursive function 7 weeks ago is that, "why do i have to make a recursive function while i can use 'for' or even 'while' loop to solve the problem". And after working through all of the exercises, term test and especially the assignment 1, i got pretty good ideas why do we need recursive function. 

Let consider an example:

def slog_example1(list1): # without using recursion
    """(list of int) --> int
    return sum of list1 which has max list depth of 3.
 
    >>> slog_example1([1,[2, 3, [4, 5], 1]])
    16
 
    """
    total = 0
    for i in list1: # 1 time
        if isinstance(i, int):
            total += i
        elif isinstance(i, list):
            for i in i: # repeat 2nd time
                if isinstance(i, int):
                    total += i
                elif isinstance(i, list):
                    for i in i: # repeat 3rd time
                        total += i
    return total

def slog_example2(list2):
    """(list of int) --> int
    return sum of list2 which has unlimited list depth.
 
    >>> slog_example2([1,[2, 3, [4, 5], 1]])
    16
    >>> slog_example2([[[[[[[[[[[[1]]]]]]]]]]],1])
    2
    """
    if isinstance(list2, list):
        return sum([slog_example2(n) for n in list2])
    else:
        return list2 

Two functions slog_example1 and slog_example2 are both performing the same task which is calculating the sum of integer elements inside the nested list. The recursive function slog_example2 can calculate the sum of integer within the list of any depth(max: 979 - check out my first extra post), whereas the maximum list depth that can be afforded by the iterative function slog_example1 is only 3 since i only repeated my 'for' loop 3 times. So unless i am patient enough to retype the 4 lines within my 'for' loop 980 times- which is rather a crazy thing to do, i would refer to use the recursive function slog_example2 to solve the problem! Imagining that if the same problem is given in the exam with infinite list depth which method should you choose?

So, the first obvious advantage of recursion over iteration is that it turns a problem that seems impossible into a possible problem. But now let consider another version of slog_example2:

def slog_example2v2(list2):
    """(list of int) --> int
    return sum of list2 which has unlimited list depth.
    >>> slog_example2v2([[[[[[[[[[[[1]]]]]]]]]]],1])
    2
    """
    return sum([ n if isinstance(n, int) else slog_example2v2(n) for n in list2])

That is the beauty of list comprehension that allows me to turn 980x4 lines of iterative code into 1 single line of recursive code. Recursion together with list comprehension not just make the code look elegant but save programmer's time and possibly money. Moreover, in some case, the recursive solution is even more understandable than the iterative solution since a recursive solution is usually very short, typically from 1 to 10 lines.

We now look at the time complexity of those three function. If you copy and run the following code in your python, you would be able to figure out which one of the iterative, recursive or list comprehension+recursive take longest and shortest time to process (check out my second extra post):

import time
def time_test():
    start = time.time()
    slog_example1([1,[2, 3, [4, 5], 1]])
    a = time.time()-start
    print('iteration takes: ' + str(time.time()-start) + ' to run')
    start = time.time()
    slog_example2([1,[2, 3, [4, 5], 1]])
    b = time.time()-start
    print('recursion takes: ' + str(time.time()-start) + ' to run')
    start = time.time()
    slog_example2v2([1,[2, 3, [4, 5], 1]])
    c = time.time()-start
    print('list comprehension + recursion takes : ' + str(time.time()-start) + ' to run')
    dict_time = {'iteration': a, 'recursion': b, 'lc+rec': c}
    print('longest time: ', max(dict_time, key = dict_time.get)) # return the method that takes longest time
    print('shortest time: ', min(dict_time, key = dict_time.get)) # return the method that takes shortest time

The result is that for  a nested list of any depth and at any length, the recursive code (without list comprehension) always take longest time to process, whereas, the iterative code though is longer take least amount of time. So i can conclude, although a recursive solution is generally very short, it is not necessary that it takes less time than an equivalently lengthly iterative solution. Time complexity therefore is the biggest disadvantage of using recursion (at least in the programming language like Python).

My last point is about debugging, in my own experience, it is much harder to debug a recursive function since it requires me to keep track of the whole stack consisting the results to many smaller problems not just the variables like in iterative function. 

Week 6 Tired!

Yes, i got very tired week! It was not because of CSC148 first assignment which i already finished last week, it was all of the quizzes, midterms, assignments from other courses, that drove me crazy. Moreover, when i checked my A1 file yesterday night, i realized that the TA only gave me 1 out of 4 for my Slog, they said that i missed the post on Object Orientated Programming (Week3) but it was right there, so i submitted a remark file on Markus and hopefully that one of TAs will check it out and remark my Slog.

During the lecture this week, we were introduced "Tree" which is a very common data structure in any programming languages. We talked about different terminologies used in Tree data structure, such as parent, children, node, root, leaf, edge ... which are fairly interesting and understandable. However, when the professor implement Tree in Python, i was kind of lost! Not only me, but my partner who sat next to me also had no idea. I am little bit worry about it now since the mid-term is coming soon in less than two weeks. Luckily, i have 9 days off from school, so i definitely will go over all of the course's material and hopefully be ready for the midterm before the class start again.

The practical tasks for this week was really interesting. We were asked to rewrite 4 functions , but instead of using list comprehension like in the sample codes, we had to write the codes in the traditional line-by-line form. I learnt how to use some of the very useful Python built-in functions such as any() and zip(). I especially like zip(), it is extremely useful and efficient when i have to iterate over several lists. Below are some of the common uses of zip():

Example1: Turning column into row! In MAT223 midterm that i sat about 6 hours ago, one of the easiest question was to find the transpose of the matrix ([1, 2, 3], [2, 4, 5], [1, 3, 2])! So i developed a program to solve the question.

def transpose():
    Row1 = [1, 2, 3]
    Row2 = [2, 4, 5]
    Row3 = [1, 3, 2]
    Matrix = [Row1, Row2, Row3]
    Matrix_inverse = []
    for d,e,f in zip(Row1, Row2, Row3):
        Matrix_inverse.append([d, e, f])  # the rows now are turned into columns.
    print(Matrix_inverse)

Example2: Turning 2 corresponding list into dictionary with key and value.

def transfer(instructor_list, course_list):
    '''
    >>> transfer(['Paul', 'Tom'], ['CSC108H1', 'CSC165H1'])
    {'Paul' : 'CSC108H1', 'Tom': 'CSC165H1'}
    '''
    return dict(zip(instructor_list, course_list)) # return a dictionary with names of the instructors as the #keys and the corresponding course that they are teaching as the values.


That is, that are all that i want to share for this week! Over the reading week, i will make some extra posts when going over the course material!

As usual, I would like to give my-self a grade of for my overall learning experience! 3/5 seems to be a reasonable grade, since i yet have a completed understanding about "Tree" data structure.

Week 5

Hello every one, normally i wrote my blog at the beginning of the weeks but i changed my mind this time, writing it on Friday because i want to share with you guides some of my thought after working through all of the tasks in the Assignment 1. I expected that the first CSC 148 assignment would be very easy ! (as i already experienced the easiness of the 1st CSC 108 assignment) . Unfortunately, my thought was wrong. I planned to complete the assignment over the weekended, but until today ( Friday), i still can't figure out what to do with the bonus question and moreover i yet completed any of the docstrings for the function that i wrote. In detail, i don't really understand the difference between the 2 methods TOAHModel._eq_ and TOAHModel.same_strategy. I think that the docstring descriptions of these two methods are little bit vague, so i did make a question in Piazza and hopefully the professors will get back to me soon. :)

The first 4 questions in the assignment are not that difficult but it is very tedious. The biggest difference between CSC 108 and CSC148 assignment is that in CSC 108 I was given detailed descriptions, parameter names and plenty of examples which help me to easily understand what a function should do. But in 148, nothing was given beside from the function names and some short vague descriptions, so I have scan through all of the given classes to figure out how other class to answer some questions. For example, how many parameters do i need, does the function return any value or None, what are the data type of the parameters ...

Question 5 is Hell no more no less! I took me 4 days of hard works until i finally got the solution with some helps from the TA in the CSC help center. The TA there are super nice, one of the TAs sat with me for like 20 minutes, explaining to me in detail what was wrong with my recursive function. Another TA there also taught me how to count no of steps of a recursive function made, which is extremely useful! I rarely came to the CSC help center, i think i came there one last semester for CSC165 weekly exercise but never for CSC108. But from now on, i will come there whenever possible!

The lab this week is about recursion, i and my partner did pretty well in the first two exercise when we are asked to trace through 2 recursive function. But in task3, when i had to code a recursive function, i struggled for an hour and half but still got it wrong at the end. The TA told me the solution, but it made me feel really disappointed about my self. I probably will have to work more on recursion during the reading week in order to prepare for the mid term that is coming soon.

In the scale of 5, i give my self a grade of 3 over 5 for my learning experience, lab performance and effort this week.

Extra # 2 Python goes to sleep!

So this is my second extra blog. Like last time extra blog, i want to show an interesting Python code that i discovered. So here is the code:

import time
def fun():
    start = time.time()
    a = 'ynnuf yrev era uoy'
    for i in range(len(a)-1, -1, -1):
        print(a[i])
        time.sleep(1)
    print('The for loop takes: ' + str(time.time()-start) + 'to run')

So if you run this code, the program will print a message that you may or may not recognize yet, haha! But the point is not the message, but the way it print the message, normally we print the entire message at once but by using the method time.sleep('time in second'), i can delay my print statement each time the loop is executed, generating some sorts of animation. Moreover, i can also calculate the time taken for the program to execute my for loop using the method time.time()!

Week 4

Third week of class was over but i still feel like the class just started! May be because i have done any assignment projects yet as i normally learnt most by working through challenging problems in the assignments (at least in CSC108H1). 

The first assignment was posted on Friday and i will have about 3 weeks to complete it. I briefly read through the handout and noted that the theme of the assignment one is the Tower Of HaNoi. At first, i thought there would be something to do with Ha Noi's turtle tower, a famous tourist attraction in my hometown, Ha Noi Viet Nam. However, i was quiet upset to figure out that there is nothing to do with my home town, Tower Of HaNoi actually is a mathematical game, which, according to Wikipedia, has a "recursive" solution. So it was not too difficult to guess that there will be some recursive functions that i will have to code over the next few weeks.

As usual , we have a two hours lab each each. In my opinion, the tasks in the second lab were a lot easier than the first one that i told you in the last week blog. I and my partner worked all the way through the tasks fairly quickly and we got 30 minutes spares at the end for the efficiency problem. One of the possible solution was that for the dequeue function, instead of actually remove the element from the queue, we could use a variable that keep track of the position of the very first element in the queue. Every time, the function dequeue is called, the tracking variable is incremented by 1, thus the running time is reduced significantly. 

In the scale of 5, i give myself grade 4 for my own learning experience, class performance and effort in this week. 

Extra#1 Recursion Limit

An interesting fact that i just knew ...

def max_recursion_call(number):
    print("The maximum number of recursive call is: ", number)
    try:
        max_recursion_call(number + 1)
    except:
        print("That's it")

By calling max_recursion_call(0), i figured out that the maximum number of recursive call can be made in Python is 979 times.

Week 3

It is just the third weeks of class after the winter break, but i am feeling a lot of pressure. The second week lab exercise was harder than i thought and struggled me and my partner for a while. I took CSC 108 last semester, we studied class and object but we did not have to write a full class, like the one in the lab exercise. And normally in CSC108, the questions told me exactly what should i do with the class (Eg: how many parameters  __init__ function should take, what methods should be included, ...). In CSC148, only the scenario is given and i have to look for noun, verb and adjective in the scenario then design the whole class's structure from them. It definitely was harder and took me sometime to adapt to.

I also learnt from the first week lab that i should do a detailed class design on paper first before starting any codes, especially when i have to deal a long and fairly complicated class like the one in the 1st lab. Otherwise, i just end up wasting a lot of time to rewrite the codes.

The homework exercise though is easier. I especially like the second question when i have to create 2 classes: Toy and Dog. I created a dog with my real dog's name as a parameter, and it is really funny when my dog created the sound "Yip! Squeak" when he played the toy, which i made for him (creating a toy object). And i guessed he really liked his toy, so i let him play the toy hundred times by setting n = 100. 

I really like the idea of the auto tester too, we have chance to see our mistakes and fix it before the deadline. I hope there will be the auto tester for next exercises.

On Wednesday, during the lecture, the class were introduced the idea of recursion. Although recursive function is not a new thing for many students, the recursive function used in the class was much more advanced than the one we studied in high school. I am looking forward to future lectures to see how much more complicated can it be!