Week 12

Hey guys I believe that this is the last blog that I would write for CSC148. It has been a great journey and I'll never regret taking this course. When I looked back, I was only a person who only knew basic computer programming like using if statements and for loops. And now, I have become someone who can write a recursive function in ten minutes. I really appreciate the time and effort my professors and TAs have put in this course. They tried their best to clear concepts for us and teach us everything that they know. This journey will be totally different without them and I'm very grateful for having them walking with me in this long journey.

This is the last week of school so we didn't have much to learn this week. In fact, we spent sometime in class to talk about the running time analysis, which we have done in the last lab. We also did a little bit of wrap up for what we have learned in this course.

My journey may have come to an end in CSC148. However, I believe that this is not the end of my journey in computer science. I'm going to enroll into the Bioinformatics specialist program. So I'll be a half life science, half computer science student just like this year. As one of my instructors always says, "if you find something that you really love to do, then you don't have to work for another day." After taking this course, I believe that I've found the path that I really love. This might not be an easy path. There'll be pain, there'll be tears but there'll also be joy and laughter. I hope that I can stay on this path throughout my years in University of Toronto. If you're reading this and you are considering to get into computer science, or you are already in computer science, I can assure you that you'll have an interesting and amazing time. Computer science is not just about programming or proving algorithms. There is a lot more for you to discover and you'll know exactly what I'm talking about once you're in this field.

So, I guess THIS IS THE END! Thank you for reading my blog. It is great to be able to share with you guys. Wish all of you good luck in the future. Bye!

Tsz Kwong (Samuel) Lee  

Week 11

HEY whatsup guys, I'm back. To be honest, I had a really rough week. I just wrote my second term test today and I think that I'm gonna bomb it. No joke. It's just too hard and I have no idea if I can get over 50 this time. I hope that I'll do a lot better in final exam. So finally it has come to week 11. The week's topic is about sorting algorithms and efficiency. Are you guys ready for it?

If I'm not wrong, seven sorting algorithms have been taught in class up to this point. They are: insertion sort, selection sort, bubble sort, quick sort, merge sort and built-in Python sort. All of these sorts have the same function. They are used to sort a collection of object into a certain order. Of course, the collection of object must be 'order-able' or the sorts won't do their job. The difference between these sorts is the run-time, which is the time each sort takes to finish their job. To compare the run-time of these sorts, we often have to look through the code and find the worst case performance, which is also called the big-O run-time complexity. For example, if sort A has a run-time complexity of O(n^2) and sort B has a run-time complexity of O(n). Then we can conclude that sort B is more efficient than sort A. The sorting algorithms that I've mentioned above have different codes and therefore their Big-O may be different. Bubble sort is often seen as an inefficient sorting algorithm because of its O(n^2) time complexity. However, bubble sort can tell us whether the list is sorted. If there's no exchange at all, then that means the list is already sorted. In another hand, merge sort is very efficient because of its unique method of sorting. It recursively divide, sort and recombine the list and it has a O(nlong(n)) time complexity. Nevertheless, the Built-in Python Sort is faster than most sorting algorithms. Probably only a few customized sorting algorithms can beat the Built-in Python sort.

Efficiency and optimization of code is a very important topic in programming. If the efficiency of the program is too low then it might put too much strain on the CPU or RAM and causes the computer to crash. Not everyone has a high spec computer and therefore, efficiency and optimization of code is important. Especially, for video games. If optimization does not exist, then the game won't run smoothly unless the player has a top tier computer built for gaming. Because of optimization, players with different level of computers can play most of the games in the market now. This has proven how important the efficiency and optimization of code is .

To me, I've been thinking to become a video game developer for awhile. And if I do, efficiency and optimization will be something that I'll always in keep in mind. I don't wanna write a game that is only playable in high spec computers. I want everybody to be able to play my game. 

So yea, that'll be all. Next week I'll post my last Slog in CSC148. Please check it out.

Week 10

How's it going guysss. I hope everything is on the right track for you guys. I can't believe that it is week 10 already and my journey in CSC148 is slowly coming to an end. I didn't even realized that time just passed by this fast. I think I really will be missing my time in CSC148, except the all-night writing programming part. Yes, Part 2 of Assignment 2 is due tomorrow. I think I'll be lucky if I can get more than 3 hours of sleep today. Since the professor spent quite a lot of time in talking about the assignment in class so I want to share with you guys about it. 

In part 2 of assignment two, we have to implement four functions for the regex tree. The four functions are is_regex, all_regex_permutations, regex_match and build_regex_tree. Among the four functions, I think is_regex is the hardest and takes me and my partner the longest to program it. Again since the assignment is due tomorrow, I won't reveal too much of our program here. But what we have to do is that we need to write a sub function to first isolate the deepest regex. By that I mean the first regex in the tree. If it's a bar ('|') or a dot ('.'), we'll split its children into two regexes. Then repeat the process again until the last note of the regex. The hardest part of the function is to figure out the right method to identify the deepest regex. Once we got that figure out, this function is basically done. Other functions can be rebuilt around this method. Therefore, the method is almost 40% of part 2. I guess this is the fun part of computer science. Sometimes your program only needs one important method. But that method is never that easy for you to figure it out. It may take you hours, or days or even weeks. Once you got the solved, you don't really have to worry about the rest of your program.

In this week's lecture, our professor also introduced different sorting algorithms. Using a list of random numbers, we could see that different sorting algorithm perform differently. Some finished the sorting really quick and some may take a longer time to finish the sorting. This is a very important topic to learn because learning the concept of this can really help me with the concept of efficiency. And the efficiency of the program is something that a computer scientist should always be thinking about. 

So far in CSC148, I'm still enjoying this course. Although the midterms are really tough, I didn't lose interest for this course because of that. I have friends who dropped the course after realizing that the midterm wasn't as easy as they thought. I like CSC148 because the challenge never ends and I can always learn something every time when I program. And learning how to program is like learning a new language, a language that let us to communicate with other computer programmers. I think this is pretty cool. I'll keep working hard on my recursion since it is the hardest part in this course and also my weakest part.

I guess that'll be all for this week. I need to get back to work or I won't be able to get any sleep tonight. See you guys later !!!!

Week 9

WELCOME BACK!!!!!! How's it going for everybody? I hope everybody had an awesome week. Well today there's a snowstorm and I have no idea what is going on with the weather! Seriously today is March 12 and when I woke up today, all I can see is snow outside my window. However, U of T seems to think that their students are tough and snowstorm is just a piece of cake to them. So yea, I still have to go to class today. Ok no more complaining, let's get started.

This week again I'm gonna share about what I've learned in lecture and I actually want to talk about my lab, which is lab #8 because I do find it interesting and I've learned quite a lot from it. 

In this week's lecture, we talked about the Binary Search Tree. Yes not just the binary tree, the binary search tree. In a binary tree, different values can randomly disperse at any node of the tree. As long as the tree has the structure: a root plus possibly two children, then it's fine. However, in this case it'll take us a long time if we are trying to search for a specific node because we possibly have to go through all the nodes to find just that one node. This is the reason why we need the Binary Search Tree. The difference between the Binary Search Tree (BST) and a normal Binary Tree is that in a BST, the value of the left child must be smaller than the root, and the value of the right child must be greater than the root. Because of this special feature, BST has a much greater efficiency. It allows us to ignore almost half of the tree after every pass. 

Here is how the search function run in a BST:

say we have to find the value z.

we compare z to the first node's value, if z is smaller, then we call the search function again with only the left sub-tree. And if z is bigger, then we call the search function again with only the right sub-tree.

repeat the step above until z is equal to the node's value.

So can everybody see how efficient BST is compare to the normal Binary Tree?

Now I want to share about lab #8 that I have just finished this afternoon. This lab is mainly about BST and we have to write a function to count all the nodes in the BST that are smaller than a given number. Now this doesn't sound very hard after I've explained about the search function above right? Yet, when we actually started to code, we found that it was not as easy as we thought. In fact, we were stuck for like 15 mins and have no clue on what we were supposed to do. I don't want to share our solution of the lab here or this blog will be super long. But what I've learned today is that all the programs are actually connected to each other in some way. Just like our example in lab #8, we used a function in Stack class to solve the question. Interesting right? So if you are a computer science student, please don't think that you can forget a function after you got tested on it. Because every single can be helpful to your program.

That's all for this week's blog. See you next week!

Week 8

HIIIII everybody, welcome back to my week 8 CSC148 blog. I hope everyone had a great week. This week is not too bad for me. Although part A of assignment two is due tomorrow, me and partner has done almost 95% of it so I'm not worrying about that so much right now. I'll talk about assignment two later on.

Right now, let's talk about the new things that I've learned this week. In this week's lecture, the idea of linked list was introduced. Sounds cool right? In CSC108, I've only learned about lists. But this time, it's linked list. So basically a linked list is lists that are linked together (NO ****!). It is another structure used to store data. It is different than a Tree. In a tree, the root can have multiple children; In linked-list, each node only contains a head and a tail. Head contains a value(or an item), and the tail is linked to the head of the next list. What this means is that the tail of a list is actually the head of another list. Found it confusing? check this out:

As you see in the first list, 12 is the value of the head. and its tail is connected to the head of the next list. Basically the tail of the first list is starting from 99 and everything behind it. If you want to insert something, let's say 15, between 12 and 99. First, you have to set 99 and everything behind it to the tail of the list containing 15. Then, set 15 and everything behind it to the tail of 12. After these two steps, 15 will be inserted between 12 and 99. I hope you'll have at least a basic understanding of a linked list now.

Ok, now I'll talk about assignment 2. Assignment 2 is all about Regexes and for part 1, we have to write a function to create Regexes. I'm sure many of you will have this question in your mind: What are Regexes? Regex is an abbreviation of regular expression which is used in many of the programming languages to match classes of strings. In this assignment, we're responsible for regexes over the ternary alphabet {0, 1, 2}. It is a non-empty string that consists of the symbols '0', '1', '2', 'e', '|', '.', '*', '(', ')'. In the regexes '0', '1', '2' don't have any children. '*' has one and '|', '.' has two. Because Part A is due tomorrow so I won't share my codes here. Basically we have to write a program to create the Regexes that I have mentioned about.

So that's it for this week's blog. I'll see you guys next week.

Week 7

Wowwwww! It's already the 7th week of this course, I am so surprised that the time in this semester went even faster than the last semester. Maybe I just have a lot to learn in csc148 and don't really have time to chill. I just done my first mid-term today and it was tough. I think I'm going to get probably a 50 out of 100. That means I probably have to work harder in the future. 

So this week's topic is Recursion!!!!!!!! Some thing that is very useful but also can be extremely tricky if you don't get your logic right. Let me give a brief introduction to recursion.

First, start with the question, when do we need to use recursion? When we are solving a problem by repetitively using the same trick over and over again, that's the time we should use recursion. Recursion works like a while-loop, basically we put the header of the function in the return statement so when it gets to the return statement, it calls the function again. This is a very important logic in programming since it is used in many different programs. Here are some examples of recursions that are shown in class:

def rec_max(L):

     """

     Return the maximum number in L, possibly a nested list

     >>> rec_max([12, 25, 0, 3])

     25

     >>> rec_max([11, [18, 36], 0)

     36

     """

     return max([rec_max(x) if isinstance(x, list) else x for x in L])

As shown above, the function will go through everything in the list and when it finds a nested-list, it calls rec_max again and put the nested-list as a parameter, else, it'll append the number to the new list. Finally, return the maximum number in the new list. This is a very simple recursion and I believe more will be introduced in the coming weeks.

It is very important to find the stopping point of the recursion when we are writing it or it will go to infinite recursion and the computer won't have enough memory to handle it. Simple stopping points come from using for-loop over an iterable object, just like the example showed above. We can also create a condition so that when the recursion hits that condition, it'll stop. Just like a while-loop. 

Recursion method is extremely useful since a lot of programs are repetitive and will be using recursion in it. For example,  for the Binary tree that has been introduced to us,  a lot of sub-functions in it are using recursion. In addition, Assignment 1 that we have handed in also require us to have a deep understanding in recursion in order to solve it. There is no doubt that recursion will be used very often when we are working as programmer in the future. 

Honestly when the professor first introduced recursion, I was lost in the middle of the Pacific Ocean, have no idea what he's talking about and how the codes work. However, I found that when I actually grabbed a paper and pen and started the trace the program, it was ten times easier for me to understand the codes rather just read the codes over and over. Although it might take quite a lot of time to trace a recursive function, the process really gave me a lot of insight on how the recursive function works and when can I apply the recursive function.

Thank you for reading this blog. I hope I'll share with you soon.

Week 6

What's up everyone I'm back. I was struggling for awhile whether I should write this blog or not. As I mentioned last week, my first CSC148 assignment is due tomorrow. Although my partner and I already had some clue on how to write the Tour.py, we have not written it out yet so we won't know if the codes will work or not. However, I felt that really need a break from the intense programming so I'm writing this blog now. (FYI I'm programming with my partner at Bahen now and we are ready to pull a all nighter) Please forgive me if this blog is not as good as the previous blog that I've written.

oh ya. I've made all my lectures on time this week!!!!!!!! and I'm glad that I made them because a new and interesting topic was introduced this week, which was Trees. Yes, I'm not talking about Biology or Geography class. We were learning Trees at computer science class. You can think of Trees as a special method for storing data. At this week's lectures, Binary Tree was introduced. 

Let me try to explain what is a Binary Tree:

In each tree there're roots. Each root can have a left child, a right child, or none. And each child can be a root itself......... etc. As more and more data was being stored, there'll be more and more roots and children in the tree.

I think the interesting part is that we can traverse the trees in different way. Up to know, three ways of traversing were being taught. They are: Post-order traversal, In-order traversal and Pre-order traversal.

Take it this way:

Post-order traversal = visit left then right, then root

In-order traversal = visit left, root, and right

Pre-order traversal = visit root, then left, then right

For example:

post-order traversal of this will be: 2, 5, 11, 6, 7, 4, 9, 5, 2

in-order traversal of this will be: 2, 7, 5, 6, 11, 2, 5, 4, 9

pre-order traversal of this will be: 2, 7, 2, 6, 5, 11, 5, 9, 4

All of this can be done by recursion, amazing right?

This is very fun too do, and it's a good practice on recursion too. I think for the coming weeks I'll be practicing more on Trees so that I can learn how to write different functions in it. So that's it for now, I need to get back to Assignment 1. Hope we can finish it tonight!

Check for my update next week, see ya!