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!