The Last Slog

Week 12: The Last Slog

As the final week of classes finish, the time to study for finals has arrived! Luckily, the CSC148 final is not until the 23^rd, but there are many others to be done before (at least for me). This week in class, we went over how dictionaries worked, and we also had a review session of everything covered over the semester. The explanation on dictionaries was interesting, as in CSC108, we were told the ordering was “random” (but not quite) in that to us it seemed random, but the computer had its own way of ordering the indexes. I had been curious at what the instructor meant by this, and now I know. The indexes are ordered through hashing. That is, the indexes (which are immutable) are given a number and are ordered based on those numbers. In addition, there was also the review on Wednesday, which helped me remember what was covered this semester.

Outside of class, the main thing was E4. Overall, E4 was not that bad, the code for the function insert was very helpful in writing the two functions needed. This task probably would have been more challenging had the given code not been provided. I did make a careless (and probably common) mistake of returning the node.item instead of the node itself for E4b, which caused the auto test to fail, but this was easily fixed. It seems one recurring problem for me with this class (and in other classes as well) is making careless mistakes even though I understand what I am doing. For example, it is very easy to make a simple typing mistake (such as leaving out a character in a variable name), forget to list include a parameter in a function call, or misread directions (especially in a test when I am nervous). I am prone to such mistakes, which can sometimes be a major problem. The best way to improve this in my opinion is to just check over my work before I submit it. I usually catch most of my errors, but something almost always manages to slip between my fingers (or I run out of time). These mistakes are especially fatal in programming, as one small error can cause the entire program to fail. But with more thorough checking (something I normally do), and maybe having someone else check my work (something I don't normally do but could try), I can hopefully eliminate all of these mistakes.

The second last slog I picked to read is http://47tulips.wordpress.com/. This person found sorting, and big O to be the most difficult unit of the semester, and I feel the same way. To me, big O requires a different way of thinking than does writing code, which may be why some people are uncomfortable with it. This person also mentioned the sorts we learned in CSC 108 were very inefficient compared to the ones we learned this semester. I agree, as I said something similar in my entry on sorting. The very last slog form another person I will read is http://supercskid.blogspot.ca/. I thought this person's descriptions of merge sort and quick sort were fairly accurate. Like the previous slog, this person is also still getting used to big O. However, it was mentioned that the lab for sorting was the easiest. I actually agree with this statement, as a large part of it was just copying, pasting, and making graphs. Interpreting the graphs was not too bad, as we already knew the run times from class, and the graphs confirmed what was said in class.

Well, that was the last slog. Goodbye everyone! See you at the final :)

Sorting and Efficiency

Week 11: Sorting and Efficiency

The last topic of CSC 148 is sorting and efficiency. My first exploration of this topic began in CSC 108, where the bubble, insertion, and selection sorting methods were introduced, and their run times were analyzed. Now we have turned to this topic again with more information. More sorting methods (quick and merge mainly) were introduced, their run times were analyzed, and we began using big O notation to describe efficiency.

To begin with sorting, here is a little summary. For quick sort, a pivot is chosen, then all values less than the pivot go to the left, all values greater than the pivot go to the right, and the pivot is in its proper position. After, quick sort is recursively called on each side of the pivot; the process continues until the list is sorted. For merge sort, the list is first divided in half. Merge sort is then recursively called to sort each half, and then the sorted halves are “merged” together.

Something I have noticed about these sorts is that they are generally much more efficient than bubble, selection and insertion sort. For example, all of the 108 sorts have a worst case run time of O(n²), while merge and quick sort's run times are generally O(nlgn). I wondered why this was, and then it occurred to me. The 108 sorts are iterative over multiple rounds. The number of comparisons in one round increases linearly with the size of the list, giving O(n). In addition, the number of rounds is simply the length of the list or sometimes the length of the list minus one. The number of rounds also increases linearly with the size of the list, giving O(n). This leads to the total number of comparisons/exchanges to be quadratic by the famous formula for the summation of every number from 1 to n. Merge sort, however, takes more recursive and binary approach. By dividing the list in half each round (a binary strategy), the number of recursive calls required only increases by one every time the list size doubles, greatly reducing the run time as opposed to a four fold increase for the 108 sorts. This is where the lgn comes from in merge's run time. So where does the additional n come from? In each recursive round of merge sort, all of the elements in the list are being compared. So the number of comparisons increases linearly with the size of the list, giving O(n). Therefore, the total number of comparisons is the number of comparisons in each round times the number of rounds. The number of comparisons in each round is n; the total number of comparisons is lgn, so the run time of merge sort is O(nlgn). The run time for quick sort offers a similar explanation to merge sort, but only if the pivot chosen lies in the middle of the list. When the pivot is in a middle position, the list is roughly divided in half, with a binary strategy like merge sort. However, when the pivot is too much to the left or too much to the right (in the worst case), quick sort starts to resemble a combination of insertion and bubble sort. The run time complexity here is O(n²), which is the same as both insertion and bubble sort in the worst case. So back to the first sentence of this paragraph, these new sorts are generally more efficient than the 108 sorts because by taking a binary approach, the number of rounds of comparisons is greatly reduced.

Of the things we learned in this class, the one I had the least practice and felt most uncomfortable with was sorting and efficiency (especially run time analysis). However, the examples in class, the past test question, and writing this slog helped me understand it better!