Sorting and Efficiency- week 11

Last week, we analyzed different sorting methods including quicksort, merge sort and the built-in sort called tim-sort compare to selection sort and bubble sort learned in CSC108. In general, the best run time is constant, followed by logarithmic and linear. Quadratic is faster at the beginning than the best algorithm nlogn, but getting worse after a certain number. The cases get worse when the power of n increase in the algorithm. In all the runtime algorithm, O(nlogn) is the best algorithm which is mostly applied in binary search tree, gives the least runtime except for constant.

After doing analysis with excel during the lab, I find out Tim-sort is the fastest one which always choose the optimal logarithm during calculation. Bubble sort is the least efficient one which grows in quadratic. The sorting methods rank as bubble, insertion, quicksort, merge sort and timsort from the slowest to the fastest. 

Selection sort sorts the list starting from the beginning of the list and exchange the item with the smallest one in the list, that is to say, the algorithm has to loop over again and again to look for the smallest item each time of iteration, thus the worst case algorithm is O(n²); bubble sort bubbles the largest item to the end of the list during each loop, thus the worst case algorithm is O(n²) as well; quick sort chooses pivots to divide the looping into half, similar as the merge sort that recursively rank the two half of looping jobs, thus their worst case algorithms are O(nlogn). 

The worst case and the average logarithm for both bubble sort and insertion sort are n², thus they are worst sorting methods since n² grows fastest; for quick sort, the average runtime is nlogn yet the worst case is n² as well. Thus it grows slower at first, yet faster than n², as the number of cases increase, it uses longer runtime and it grows faster. All the other cases have nlogn for both average and worst cases, thus they have a shorter run time by cutting all the running process into half. Even though Timsort has nlogn as worst algorithm as well, it will automatically choose the optimal algorithm to use, thus it is always the fastest one. Apart from that, Timsort applies n as memory, thus it is a stable and fastest way for sorting. 

week 10

This week is full of midterms and assignments, however, the assignment two is not that hard. The first function is the most complicated one, but as long as we get it, the others are pretty straight forward. We mainly learned quick sort and merge sort this week, which is a lot faster than selection sort and those we have learned in CSC108 through the use of recursion. We practiced timing the functions as well. Further more, it is more related with CSC165 this week through talking the algorithms of timing. This week's lab is terribly hard which my partner and I have no idea the way to do it, almost nobody in our lab session finished it, we really wish if the answers could be posted so that we can study it by ourselves. Next week will be our second midterm. I did not do well on my first one,  thus I am prepared to review harder and get a better mark for the test.

week 9

This week we have mainly talked about binary trees with balancing children with the left ones smaller than the root and the right ones bigger than the root. Thus, less conditions need to be considered before running recursion for deleting items.Similarly in search list, it is easier by applying the idea of recursion to find the number. However, the binary tree has to be balance in both sides, that is to say, has the same depth for both sides in order to cut in half repeatedly.
We also discussed the run time of different functions. Binary tree mainly use log2n which is almost the slowest in long term. The run time big-Oh is similar to what being taught in csc165. Glad to see how these two courses are finally related. It is interesting to calculate different run time functions and get an idea which one applies better in different conditions. All in all, binary search uses the least step to calculate.
This week's exercise and lab is pretty straight forward by applying recursion, but there are always a lot easier ways to do them and we can improve. A2 part will due in one week which struggle me a lot. Hope I can finish it before next week that I have 3 tests coming up.

week 8

This week is still mainly about linked list, it is good practice for us to remember the concepts by doing it several times. The lab is much easier than last time, which was pretty confusing. Last week, my partner and I sent 2 hours without giving an answer, but this week it is much easier so that we can finish it in one hour. I am still a little confused about applying recursion into the functions especially write in one line. I tried to do that but it seemed does not work properly each time. I did terrible on the test and the most problem occurred for applying recursion and inheritance classes. The order of exception was important as well, there are always conditions in the function that need to be discovered before writing the code which I have to pay attention to next time. Assignment one went on pretty good and my group even raised exception for the class instead of giving precondition which is simple. We had fun on this but we did not start a2 part 2 yet because we prefer to do it after the documents come out. I hope the assignment 2 would go on well! :)

Week 7 Recursion

Week 7 Recursion

Recursion was the main focus what we have been studying for the past two weeks. Recursion is mainly using the solution from the smaller instance of the problems to solve the problem as a whole using the same process until the program gets to some point. The formal explanation would be that recursion is functions that call themselves within their definitions.It is one of the most important idea in computer science that help to build the models of functions. It is a circular idea of solving problems through looping over the same strategy and solve the small instances of the problem. That is to say, break down the questions into smaller part that is easier to calculate; after that, combine all the answers together and stop at some given point. It is an extremely helpful method that calls itself repeatedly within the function. Tree models are the best examples for recursion which runs recursively. Similarly, the Fibonacci numbers in math uses the same method as recursion in programming. It is quite obvious that all the recursion look like tree figures, including the examples of tree models, turtle and Fibonacci numbers. One of the most important point in recursion is to find the smallest instance to start the recursion, and the other one is to find an end point for it to stop recursion. Sometimes, it is hard to find the start point, yet as long as we can find out the start point, then the whole process would be straight forward. 

week 6

This week, we continued to do the recursion, which still seems a bit complicated for me. I worked on A1 a lot this week, but I still did not get a good solution for the function move_cheese. I plan to study recursion more during reading week. Using a tree to interpret recursion is actually easier even though there are different cases, but graphs always help to understand the topics. The week after reading week will be the mid term for this course yet I still don't really understand the most important part of it. This week's lab is pretty easy and the program can be used for the calculation in MAT223, which is really fun.

week 5 post

This week we still stick on the topic of recursion, on Monday we tried to trace some recursions by hand which helped me to understand the process how haoni works even though i haven't look at the assignment yet. I have a pretty good idea on how the recursion works, yet I am still confused about how to write the recursion statements in a line of return. I tried hard during the lab yet I still cannot get a solution based on a line doing it, I end up with a for loop which we did in 108, much easier >.<. For the staff we learned on Wednesday, I found it hard to trace and I did poorly on understanding the 'global' and 'nonlocal' thing. I have no idea why the result changes from 'test spam' to "nonlocal spam" even though several people explained to me, I still cannot understand it. I believe the reason why I cannot understand it is because I did not fully understand recursion. I will go up to the website of python and read the docs to make sure I understand it. Then, I will try to finish my A1 as soon as possible cause there is not much time left. The Haoni thing is really fun though, which seems random yet involves a lot of math and sequences.