Sorting and Efficiency

The last week of the second term is around the corner! Only two more 148 lectures are left and I am almost done my year one! However, maybe the profs wanted us to feel the opposite rather excitement, so they decided to give us a hard midterm on last Wednesday. Well, at the beginning, I thought I might just give up this course or even CS. Thank God that I came up with the answers for each questions even though they were not perfect. Anyways, something is better than nothing on a test.

In these few weeks, we came across with sorting again just like what we did last term in 108. We first had some review on bubble sort, insertion sort, and selection sort. Afterward, the topic Big-Oh was added. Big-Oh function is the upper bound of the worst case run-time model of a particular algorithm. First of all, let's list out some of the new sorting algorithms that I learned in this week.

Assume we have a list of [8, 9, 0, 2, 5, 4, 3, 6, 1, 7]. Let's see what the sorting algorithms with do with it.

1) Quick Sort
We first need an element to be the pivot. We can just take the last element by convenience. Then, we split the list into two halves; the first half is those elements that smaller than 7, the other half consists those bigger than 7. Now, we have two other new lists: [0,2,5,4,3,6] and [8,9]. We then repeat the same process again by using recursion, taking the last element as pivot and split the list into two halves. At the end, we can combine all the elements from the smallest one to the biggest one and this gives us a sorted list.

2) Merge Sort
We need two function for this sorting method. The first one is called merge. We combine two sorted list into one sorted list by using Merge function. The other one is a function that recursively return Merge function on the two halves of a list. If we have  [8, 9, 0, 2, 5, 4, 3, 6, 1, 7]. We will split this list again and again down to [8], [9],[0], [2],[5], [4], [3], [6], [1], [7], then we call merge in each pair. Then we get [89], [02],[54],[36],[17]. Then we do the same thing again and at the end we would have a sorted list.

The efficiency of each sorting can be compared by their worst case runtime on the same object. The quick sort is faster than merge sort since the worst case big-oh of quick sort is n^2 and nlogn for merge sort.

Tree and LinkedList

In these few weeks, we learned about LinkedList object and Tree object. I have met several type of Tree representation such as TreeList - a list of lists, binary Tree - a class contains root and children, and also binary search tree - something that I need to work on now. These different objects give me a lot of opportunities to understand python more. My passion in computer science keeps on growing because of this, too.
In lab, I finally met a fixed partner where I don't need to switch every time I go. And we help each other a lot. Unlike me, she is quite having a tough time with this course. However, she caught things up very fast after I explained some abstract concepts to her. I found it difficult while dealing with the Queue class implemented with the LinkedList. The enqueue and dequeue methods take us a lot of time that we can'y finish the whole assignment. It's quite challenging since we need to figure out which end of the LinkedList we should be doing the enqueue or dequeue. Basically, I think LinkedList is like a nested list, and we need to go very deep of it to look for the tail and do enqueue or dequeue methods. That's the hardest part to solve this puzzle.

The first test result wasn't ideal. I consider myself as a qualified candidate for the admission of ComSci. However, the test result gave me a warning. I should try harder and think deeper in the next few weeks. Hopefully, I can reach my goal in the upcoming test and exam.

You can do it, Chris!

Recursion

By looking up the word Recursion in the dictionary, it means the repeated application of a recursive procedure. When I first saw the technique of using recursion, I thought it was amazing and kind of abstract. We have to break down something and go through each time the recursion works. For me, I think recursion is something we reused itself in the process. We create something while it exists in its own body. It is really hard to understand it for people who are not familiar with computer science.

I first saw this word in high school. I remembered it appeared on the math textbook in the sequence chapter. The recursion defines some kind of sequence where the sequence itself is neither arithmetic nor geometric sequence. Such sequence has the characteristic where a term is dependent on the previous term.

By using recursion, we can break down a huge problem into simpler problem and apply the same approach multiple times to ace a task. The process is going to end while the base case is reached.

For example, when we encounter a list of list, a recursive function is helpful to determine the largest value of this list of list object. Because the object is a list of list, we can crate a recursive program that works for a list and reused it for the elements within the list since those elements are just list. Here, a problem is reduced to a smaller one since the program is "recycled" and we don't need to create more steps to due with the elements inside the list. Recursion, again, suits for the big topic - laziness.

It impressed me when it is even being used in the Tower of Hanoi problem. We solve the problem quick and easy. If I were being asked to solve the problem, I think I will use much more moves to finish it, but with recursion, everything is being done in a few second. However, it is annoying when sometimes we don't recognize the situation for recursion. In the next few weeks, I must understand more about it and grab all the techniques and tricks of recursion.

See you soon!

Cheese :(

Assignment 1 is due in a week! I started two week ahead and I am almost done. I am not a qualified programmer and Piazza is my best friend. Many fellow students throw a lot of helpful questions there and many of my problem are solved from the responses. The hardest part of this assignment is to figure out what the is should be because i will change once the recursion reduced. However, I am not sure if my way if proper, I implemented a function to find out the best solution and I used the equation in the assignment sheet to work back finding what the value of i is. I still use recursive function and it turns out working and giving me the best result. At this point, I don't think this assignment challenges me too much but I felt dizzy when i first looked at the sheet. 

In this week, we worked on recursion a few times. Let's write about it later in reading week. 

So far, I think 148 is more abstract that 108 and we need to practice to understand every concept. The lab is very helpful and I meet new friends every time. When it was in class, I asked the person sit beside me questions, and I learned a lot from them. 

Computer science is not my intention of coming to UofT, but from now on, I will consider it as my future studies. I hope I will make the best choice. 

See you soon! :)))))

Inheritance and Exception (Week#4)

It has been a great week so far. This week, two important topics are introduced, inheritance and exception. We use inheritance to avoid rewriting some codes that have same characteristics. Professor Heap gave us an example on this topic. We have a parent class called Stack. It has its own methods such as push, pop, etc. And inheritance is introduced when a children class called IntStack is being created. Most of the methods are pretty much the same as its parent. We can create the children just by:

class IntStack(Stack)

and we can access the parent methods with Stack.method(...). This is really suitable for our first year goal - obtaining laziness. 

Another big big topic - exception, was 'raised' this week. We can create our own type of exception just by using inheritance:

XXXError(Exception)

We can raise one when something you don't want to see appears. However, when something wrong goes  into the program and you don't want the whole program to stop, an Try option can be built in the code. 

try:

    blah blah blah

except:

    blah blah blathe

The lab and exercise went pretty well and I hope I will start my assignment soon since it's busy these days.

Let's have a chat some time next week.

Object-Oriented Programming

Well, OOP, what a cool name. I've been using Python for a term already and I don't know it's using something called OOP(Object-oriented programming).What is Object-oriented Programming? After I went through some research online, I had ideas now.

This type of programming is an idea. It contains many objects unlike a procedural programming language. Basically, such programming language is split into different parts having different functions and applications. Each part has its own logic and data. It represents one of the small part of the whole program. It's easier for us to organize and think about a task.

A few terms need us to pay attention. They appear in a OOP frequently. First of all, there is something called class. We can understand it by taking it as a blueprint. It describes what something exactly is. It exists in different part of the program. It represents anything as long as something has idea. All classes define attributes and behaviors. In simple words, attribute is some kind of data or variable in the class. Behaviour is what can you do, is like a function. Also the data is abstract, and we need something called object. An object is a something real. We can create many objects within one class. For example, we have a class, which is like a blueprint. From it, we can build a lot of houses, which are our objects. This describes the relationship between class and objects.

Thinking of our world, we are all surrounded by objects. We might have a class called shoes. And we can have different objects which is shoes. We might see heels, boots, or sneakers.

Week 3 is amazing. I learned a lot this week such as Exception, and a new class called Stack. For me, practising is very important. I couldn't survive in CS if I juts did not do any actual programming work. Last term, it's my first time to touch something like Python. Hopefully, I can succeed in this course just like in CSC108. Let's pause for a moment and do my exercise two now. OOP, OP!

Week3 just begins!

First post is right here!