Week11

    Sorting & Efficiency.

     To talk about sorting and efficiency problem, let's go back to CSC108 first. In CSC108, we learnt three simple sorting techniques, which are bubble sort, selection sort, and insertion sort. Although they are implemented in different ways, they achieve quite similar performances. In the worst case, they are all inefficient algorithms which have runtimes of O(n^2). One new perspective to evaluate the performance is to look at their average runtime, which we learnt this week. The average runtime is the average runtime of a function on random inputs. It turns out that insertion sort is the best algorithm among the three on average case.

    Nevertheless, these three algorithms are still considered bad sorting algorithms because of their inefficiency. Thus two new sorting algorithms are introduced in this week's lectures. They are quick sort and merge sort. With the concept of divide and conquer, these two algorithms achieve an impressive runtime of O(nlogn), which is much better than O(n^2) on large inputs. There's a very interesting visualization of the runtimes of all these sorting algorithms (Link: http://www.sorting-algorithms.com/). From this animation, you would have a good sense of how runtime varies in different sorting algorithms.

    There're also other sorting algorithms that could achieve the runtime of O(nlogn). However, most of them are hybrid algorithms from the basic algorithms I introduced above. For example, the built-in sorting algorithm of Python, which is Timsort, is a hybrid of merge and insertion sort algorithms.

Week10

    Recently, I found codes are increasingly hard to understand and process. Especially problems involving LinkedList, Binary Search Tree, and Linked Binary Tree are very challenging. These concepts haven't quite sunk in yet. I need some patience now. I'll have to re-study all these concepts from their fundamentals and fully comprehend their implementations. Hopefully, I can feel comfortable with these concepts when the course ends. 

Week9

    This week, I want to share something that I learnt from working on Exercise3.

    For me, Exercise3 is pretty hard, compared to other exercises. Nevertheless, I successfully solved the problem. Even though my codes work perfectly fine, I'm not satisfied with those messy and ugly codes. There are too many helper functions and messy conditions all over the place. However, I can't quite think of any other way to solve the problem. Luckily, one of my friends was so kind that she shares her solution with me. I was totally stunned by the elegancy of her codes and the thinking behind her solution. I'm not going to hide the fact that she is not even in CompSci. She is from Rotman Commerce. After reading her codes, I questioned myself. Why? Why can't I think of that solution? Why even a Rotman student better than I, a prospective CompSci Specialist? I noticed a serious problem with my programming style. That is, I am not patient, and I always jump right into coding after reading the problems. So then, I sit back into my chair and rethink about this problem. I tried to be as patient as possible. Forcing myself to turn off the screen before I figured out a clear strategy to solve the problem. This is hard, I have to say. But, indeed, it pays out. A cool mind really helps me to program more efficiently and gives me a much cleaner code. 

    My friend, I've learnt a precious lesson from you, thank you very much! :) 

Week8

    Time flies. Only one month left till the end of classes. 
    Why don't we do a short review on what we've done so far? In my opinion, the most important elements of this course are recursion and class construction. I would say that recursion is the most powerful concept in this semester, for the reasons in my last week's post. Certainly, class construction has been an essential idea throughout this course. Stack, Tree and LinkedList are all depended on the design of classes. I think now we are really getting the taste of what Object-Oriented Programming is. 

    This week's lectures are on LinkedList and Binary Search Tree. LinkedList is basically a tree with an arity of one. We've learnt two ways to implement a LinkedList. The more complicated approach is to separate the implementation into a LinkedList node class and a wrapper class for the LinkedList. One benefit of this approach is that it makes thinking recursively more natural to programmers. Binary Search Tree is a tree, with an arity of two, in which the value of each node is controlled strictly -- the value on the left sub-tree must be smaller than the root and that on the right sub-tree must be larger than the root. The other way around might be possible too. The significance of this type of tree is the efficiency of searching. With its rigorous structure, binary search tree greatly reduces the search time it takes to iterate through the data of the tree. This would be crucial for data management with a massive amount of information. 

Week7

    Recursion.

    Recursion is the concept of reusing a function within itself repeatedly to solve problems. A common structure for recursion consists of a base case and a general case. A base case provides functions with conditions to exit and a general case contains recursive calls to solve smaller problems.  Let's take the function factorial as an example. The following is the code for this function:
    
    def factorial(n: int) -> int:
        if n == 1:
            return 1
        else:
            return (n * factorial(n-1)) 
     
    As you can see, there're two conditions in the function. In this case, the if condition is the base case and the else condition is the general case. The base case stops the recursion once the given integer reaches 1 (by the definition of factorial). The general case asks the function to call itself on a smaller input, (n-1) in this case. This problem seems pretty simple but it would be tedious if we have to write down every multiplier of the factorial of n. With adapting recursive structure, we avoid these troubles when building our codes.

    To me, recursion is such a powerful mechanism where the function would split the problem into smaller pieces and solve bits by bits automatically. By automatic, I mean humans are not required to specify the exact pieces (or procedures) for the codes. This mechanism saves tons of works when dealing with complicated algorithms and generally gives you a more elegant code. It might not be apparent to you at the first glance how recursion works. As I mentioned in an earlier post, the best way to understand recursion, it's to trace it by hand. I've done that and now I am used to think recursively.

--------------------------------------------
    My thoughts of the week.

    We did our midterm test this week. I would say this test was fair and diverse in its content. In this course, we haven't being writing codes as intensive as in 108. That made writing codes on paper a bit challenging for me. From this experience, I think I should practice more coding rather than merely studying the theoretical ideas from classes. 

Week6

    Well, A1 is finally done. Have to admit that I spent quite some time debugging and organizing my program the night before the due date. Surprisingly, I found that I am getting much more efficient in doing debugs than last semester. Back then, it sometimes takes me hours to fix a tiny bug. Now, I can easily spot the problem right after seeing the error message. Apparently, experience has got me much more familiar with Python's structure. That's a good news!

    However, a bad news is that lectures are increasingly hard to follow, for me. I can't really absorb much information from the board. The same thing happens to me during CSC108 last semester. But there were those video lectures which really help me comprehend the course materials. I hope there've been similar resources in this course to support students in learning and reviewing.

Week5

   This week has been very challenging with the Assignment 1. But, finally, almost there! Essentially, the concept behind this assignment is not hard. I think the hard part is that the tasks are very complicated and their instructions are not very clear. You have to figure out many things by your own. For example, the methods you need to write in TOAHModel are neither well-listed nor well-instructed. But I feel that's kind of the expectation from us though. Eventually, we are going to design our own program solely by ourselves without any instructions at all. I guess we are slowly approaching there.  For the techniques involved in this assignment, they range from week 2 to this week. Other than the old knowledge from 108, you need to know recursion well, know how to construct nested functions and understand the concept of scope.