Week 11 Sorting and Efficiency

When talking about the efficiency of an algorithm, we often break it into two: time efficiency and space efficiency. And currently, we focus more on the former one. There are different cases in which we measure the time complexity of algorithms: best case, average case and worst case. We cannot simply say a program is efficient or not without analyzing the behaviors of the algorithm in those three different scenarios.

We introduce big O notation, which provides an upper bound for the runtime of our algorithm, to simplify our analysis. We often choose the simplest and tightest bound, for example O(n), O(nlogn)...Understanding the algorithm analysis is very important and necessary in this information-exploding world. Although the effect of choosing a time-saving algorithm is not very obvious in our current study, when we are dealing with large data it can be a significant difference between two choices of algorithms . The performance of the algorithm does count.

In addition to selection sort, bubble sort, insertion sort, we basically learned merge sort and quick sort in CSC148. We can tell from the chart provided above that the merge sort and the quick sort are more efficient than those previous sorting algorithms we learned in CSC108. Both of the two algorithms are based on the use of recursion. We can use Master Theorem to compute the time complexity of a recursion algorithm. I learned this from my TA in lab.

I found this website very useful in understanding efficiency of the algorithms "http://bigocheatsheet.com/ ". So I'm sharing it for you all.

However, sorting algorithms are not limited to those I mentioned above. There's also an important sorting algorithm called tim sort, which is used for the python built-in sort. 

Week 10

As before, here I'm sharing my code for lab #9.
But for this week, I'm writing really long code for these two functions and I think it really need improving.
Sometimes I don't think lab is a good way to improve our skills for coding especially for the difficult ones. One needs his own independent thinking and needs some time to stay alone, which is more productive than working in pairs.
Labs are becoming harder and harder. And sometimes I have to finish it at home, which adds on my workload for this course.:(

Week9

Here I'm sharing my code. This is for the extra problem in lab#8. I found it soooo interesting to use Stack data structure to avoid using recursion. It's so clever to do so but I'm not sure which one is more efficient.

This is also the code for lab#8 BST_rec1.That's not challenging, so do the other two tasks in lab#8.

In my point of view, tree is a very interesting and useful data structure. But sometimes I can't fully understand my own code even if the program can run properly without error. But anyway, we don't have to trace recursion, which is a very silly thing to do.

Week 8

I'm quite interested in "copy". In order to figure out what it really does, I wrote some code. And here I'm sharing it and I hope any of you can benefit from it even if it's very simple:)

And also, like I always do, here I'm sharing my own code for lab#7. There may be some mistakes in it. And these may not be the most efficient way to implement those methods.

Week 7: Recursion

Recursion is something that requires quite a bit thoughts and every time you think about it deeply, you will get a better understanding about it. We have been learning recursion since the fourth week and I am confident about designing recursion functions now although I was very confused about it(which can be noticed in my previous slog post).

Here, I'm sharing my own trick about designing recursion functions.
Firstly,you have to assume that the function you're writing is already defined. For example, if you wanna write for the n-th case, you will have to assume that the previous cases have already been defined somehow and you can use them by calling the function itself whenever you want. Finally, check that whether your function has base case. If it does, leave it, you're done. If not, add a base case for your function to know when to exit the recursion. Usually, we use if statement to add base cases, but that's not always the case.

I found a very interesting website "http://projecteuler.net/", where you can find some nice programming practice. And I practiced recursion on it by writing the fibonacci sequence. Here I'm sharing my code.

Now, I'm really concerned about the efficiency of recursive functions because it always takes a lot of time for a recursion function to execute. Although some functions can only be written using recursive structure, there are many other functions that can be written in simple and regular ways. I hope we will learn more about how to improve the efficiency of our program later on.

I wanna share a word from one of the slogs from my classmates at the end--------------"Recursion---my worst enemy and my best friend".

Week 6

The assignment 1 is due this Thursday and my partner and I are working together on this relatively tough work. We did some tests to test whether our program works fine.

Reading Week is coming soon and I'm happy to have plenty of time to find more interesting things about computer science during the break. I have a plan for this reading week including learning more recursion and doing more practice, and learning some new programming language such as objective-C and Java...

We learned some new things about "Tree" although we have already encountered binary tree problem in one of the previous lab. Apart from some terminology of trees, we learned how to implement different methods to, for example, count the leaves, nodes and so on. It requires quite a bit thoughts and a good understanding about recursion.

I find labs really helpful. I can not only meet challenging problems and discuss with my fellows, but also make friends at the same time!

Anyway, I love programming:)It makes me feel alive~

Week 5

This week is for ASSIGNMENT ONE!!!!

I spent many hours working on the assignment.

I found the lab for this week is very challenging and needs quite a bit of thought, especially those extra problems. But it helps me understand recursion better.

We basically learned recursion and function scopes this week. And I found the explanation of the assignment 1 by our professor is very useful.

Anyway, I have to make more efforts in order to achieve a better understanding about python programming.

Here, I'm sharing my code of the extra problems for this week's lab.
I'm not sure about the correctness about my code, so if any of you find there's something that needs improving, please leave a comment! Thanks a lot!

Week 4

This week, we mainly learned recursion and some applications.
It firstly seemed to be magic because the function can call itself recursively as if it is already defined. But as I learned more about it, I found that it just execute many times until it gets a return value and it will put its return value to the last step until all the steps have been accomplished. It needs base class to tell when to stop.
I can understand most of the examples of recursion functions but I still have some difficulties in writing my own recursion functions. I found tracing the recursion is very useful in understanding it.
I have read the handout for assignment 1 but I haven't started coding yet.
I hope I can finally understand recursion fully.

Week3: Object oriented programming

So far, we have been learning object oriented programming for 3 weeks and it gives me a feeling that object oriented programming is revealing a much more colorful world of programming for all of us. And there are so many new stuffs to learn and to think about. We no longer depend on and learn from the weekly video lectures which have limited time and material in it, but are supposed to read more professional articles and discover those sometimes confusing but useful methods on the Internet on our own. This can be not only very challenging but frustrating as well, because every time I read those articles, I can't wholly understand them, and I feel like it's still a long way to go to become a professional and experienced programmer.

During the 3-week studying about OOP, I find two things quite interesting. One is that almost everything in Python is an object. For example, we can do many things with "list", because any list is an object from maybe "List Class", and those methods are defined inside this class. Therefore, every object has its own memory address. An interesting analogy about class is "Human Class". We are all different object of "Human" class. We have names, which are the attributes of the objects from this class, and we also have "methods" such as eating and drinking, which may result in the change of our weights and heights that are attributes of this class. The other interesting thing is that there is inheritance among classes. Every class inherits automatically from "object" class, which has many special methods in it such as "__init__", ""__eq__"". And we can also override those old methods without changing any code from the parent class. What's more, we can use the built-in function super() to call the methods in the parent class any time we like, which gives us much freedom. However, I think we lack practice about class inheritance and I hope we will encounter problems about it in the assignments.