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.