W11: Sorting and Efficiency

As with any real-life objects, sorting in computer science refers to the action or various steps of arranging objects into some logical order. It is also essential that a sorting algorithm is efficient; computer scientists want to achieve their goals in the most time-efficient manner. Thus, we are introduced with the concept of big-Oh and the issue of analyzing run-times.

What is Run-Time?

"Independent of hardware, programming language and random events" run-time refers to the number of steps that is required to complete a task. When analyzing the run-time of a program, we generally focus on the size n of a list. Consequently, as the size of a list changes, the run-time changes. The run-time of an algorithm is thus modeled as a function, with n as the independent variable and time as the dependent variable.

What is Big-Oh?

Even if a program's run-time is modeled as a function, the information is not very useful if the function is too complicated. Consequently, an upper bound on the run-time is needed. This is where big-Oh comes in. If function f is O(g), we say that the run time of f is like function g in the worst case. Why is this useful information, you ask? First, this allows us to simplify the run-time of a program (function g) so that the performance comes more intuitively. Second, computer programmers and their clients want to achieve their goal in the most efficient way and be certain about it. By providing the performance of code under the worst conditions, one makes a guarantee about your program (i.e. "it can't get any worse than that").

Not All Lists are Equal

When you think about the variables that may factor into a sorting algorithm's run-time, there are several things to consider:

> How large is the list? A smaller list will generally be sorted faster than a larger list.
> Is the list sorted? For some sorts, a sorted list requires very little work to be done.
> Is the list reverse sorted? For some sorts, a reverse sorted list is the worst-case.
> Maybe items in the list are in random order? You can consider this the average case.

Divide and Conquer!

In CSC108 we learned about bubble sort, insertion sort and selection sort. However, this term we've focused on a two new sorting algorithms (merge and quick sort) that use a method of dividing-and-conquering.

Recall the concept of dividing-and-conquering that was first introduced with binary search trees. By knowing whether a value is less than or greater than the root, the searcher can ignore half of the tree. Each time you go one level deeper into the tree, you split the tree in half and ignore one side. How many times you can split the tree is log n times. Thus, binary search is O(log n).

Similarly, merge sort and quick sort both split the given list and run recursively on the sublists. Thus the depth of recursive calls is log n. However, with each split of the list, every element in the sublist is compared. By adding up the size of the sublists, we naturally get a total of n comparisons. Thus by dividing and conquering, merge sort and quick sort (for a good pivot choice) run at O(n log n).

An Opportunistic Sort

Although dividing-and-conquering algorithms obviously run much better than linear and quadratic ones, the built-in sorting function in Python is even better. Called "timsort", the built-in sort begins by briefly looking at the list it is given. Depending on the circumstances, the algorithm will choose a different method of sorting the list.

Why is this important? First of all, with many algorithms in computer science, there is always a "special" case where the algorithm runs extremely well or terribly. One algorithm is never the best choice for every type of list. Methods like timsort thus better follow the human process of problem solving (as I have mentioned in older posts).

W11: Test Two

If the last test went badly, this one went even worse (and that's saying something).

Last time, although I procrastinated, in the end I still had a solid three days before the test to study. This time, I wasn't so lucky. On top of two other horrible tests last week, as well as a major group presentation... well, I was doomed.

I admit, the group presentation won out – not only was it a research project with an interesting topic, but if I failed to do my share of the work it would not have been pretty. At least if I fail to do the work for something of my own responsibility, it is only my problem. Nevertheless, after so much hard-work it was pretty much impossible to keep my inner procrastinator at bay. It was only two nights before the test that I really started to worry and make the connections to my Test One experience.

Major Mistakes

> Reading the tutorials and not re-doing them. They were very difficult... and the test was difficult too.
> Not working problems out on paper before attempting to code. I realized that computer science is not at all about the computer... it's about being able to problem-solve with your brain, and then translate that into code after the fact.
> Spending my last moments of studying typing up an aid sheet. Although the aid sheet was useful for the last test, this test which was all about writing new methods and functions. Thus, the aid sheet was useless. I kept it beneath my test paper for the whole 50 minutes of the test.

The only thing I can say for myself is that I think I had at least half an hour more sleep than last time.

W10: Sorting

This past week I missed the lectures, which were unfortunately about sorting algorithms and run times – my worst and least favorite topic from CSC108 and CSC165.

In addition to sorting algorithms we learned in CSC108, the prof talked about two new sorting methods in lecture: merge sort and quick sort. After reading through his slides a few times and sorting by hand a few short lists, I began to understand what the two sorts were. However, I didn't understand the run times that they had. Why were the run times for merge and quick sort both in O(n log n)? Are there n comparisons or log n comparisons? But apparently quick sort can have a quadratic run time if a bad pivot is chosen? I was extremely confused.

Thus, this post is not about detailing what bubble sort, insertion sort, selection sort, merge sort, quick sort, timsort and count sort do, but rather the tale of my self-learning.

When in trouble, always turn to Google.

At first, I read Wikipedia articles and other SLOG posts about sorting, but because I found the topic so dry I wasn't absorbing any of the information. Luckily however there are countless computer science videos on YouTube. I find myself someone that learns best when I someone is teaching me, so next to attending lecture videos were certainly the best option for me. With the help of some amazing YouTube channels, I was able to sort out my confusion. For merge sort and quick sort, there are log n splits of the list. However, with each sublist, each element in examined. Thus there are n examinations and log n splits, resulting in an O(n log n) run time. Pictures of merge sort were amazingly helpful also. Although I had worked out problems on paper, seeing very organized diagrams of the two sorts helped a great deal. 

Image of how a list is split by merge sort.

Retrieved from http://www.codenlearn.com/

For anybody reading this SLOG post, I highly recommend the following videos! I found these to be the clearest and most helpful.

Quicksort Explained

Sorting: Ep 09 Merge Sort

Merge Sort

And, for some odd reason, this extremely entertaining Hungarian Dance of quick sort!

Quick-sort with Hungarian (Küküllőmenti Legényes) Folk Dance

W10: A2, Next Test, Next Test, NEXT TEST?!

How I feel about computer science right now:

1) ECSTATIC!

I finished A2! After a week of assignments (which did not go very well) and tests (which also did not go very well) I was absolutely dreading working on A2 and forgoing much-needed rest. To be sure, it was tough and at times mind-boggling, but because A1 was a killer, I had been anticipating much worse. At first, I was intimidated by the heavy recursion that was required, but once I just got down and tackled the assignment (with some handy, old-school paper and pencil) it was a much smoother experience.

The most important thing I've realized from A2: usually the code follows very closely to the actual instructions. I spent an inordinate amount of time considering the rules of a valid regexes and how to convert the rules into code when the answers were under my nose the whole time. Having my code follow the instructions, step-by-step, made everything much more understandable.

2) That feeling of success... VICTORY! RELIEF!

Well, we finally got our results for A1 back and I'm so unbelievably relieved to have done well that I can't really put it into words. A1 was undoubtedly one of the most stressful and yet memorable challenges I've had in university so far (I was still debugging my code one minute before the deadline... I was about to have a heart attack then). And, like I mentioned above, it's nice to get something right on an evaluation for once.

3) Today is the first day of spring...!?

Well, first of all, this is Canada, so the change in seasons doesn't really apply. Nonetheless, it is rather astonishing that we're already in the last three weeks of the university year, not considering the exam period. Assignments and tests and exercises have been going by so fast and in such rapid succession that I haven't had time to contemplate the time. Especially with computer science, once I get drawn into a problem or challenge I can sit in front of the computer for ages. I haven't been outside at all today, and I only recognized it was "spring" when I saw the Google Doodle.

4) Back pains.

What I LOVE about computer science that I haven't gotten from any other subject is that I can get very immersed in solving CS problems, when for many other things my attention span is about five minutes. It is very interesting converting "physical" entities into objects that can be handled on the computer – for example, Trees, which can be drawn out (physically) and manipulated in Python.

What I HATE about computer science: the back pains. I'm happy I've accomplished my work for today but my back is screaming in protest. Exercise may be a good idea.

5) Next...

Next week I have a major presentation on the same day as the second term test for CSC148, and unfortunately I have not begun to work on the presentation, nor do I understand anything about sorting. Oh, and I also didn't do very well on the last test, so I really need to do well on this one.

WELL.
That's the university life, eh?

W9: BSTs

My weakness is working with binary search trees... there was a week back when I skimped on BSTs by telling myself I knew them well enough. Well, that was certainly a lie.

First, the tutorial this week was killer. I mean I pretty much sat there watching my tutorial partner do all the work, and then afterwards had my partner (and the TA) explain everything to me. Even when I got home and tried the tutorial again, I botched it.

My biggest challenge and frustration from this week came in lecture, where I might as well have listened to the prof speak ancient Greek when he was demonstrating how to delete a node from a BST.

Later, after rereading the lecture notes multiple times, I've been able to get only the gist of it. Basically, if the node has no children, you can simply delete it. If it has only a right or only a left child, you can delete the node and reattach the child with no issues. However if it has both children, you replace it with a) the greatest value in the left child or b) the smallest value in the right child. This way, the order of the BST is maintained.

Although I've gotten that much understanding from revisiting the lecture notes, the code for this method evades me. There is the _delete helper method and then the delete method? I am SO confused.

EDIT: I've been able to get some help on this, thankfully, although I'm certainly not confident enough to write my own delete or insert method.

W8: A2 pt.1

This week has been a crazy, hectic week, but nonetheless I am happy to say that I accomplished A2 pt.1!

After A1, I promised myself that I would start the next big assignment at least a week beforehand. However, when the due date (yesterday) crept up on me, I could feel the fear again. Thankfully however, A2 pt.1 was as the professors promised and not intended to be extremely challenging; it just required very thorough thinking and coding.

Unlike previous exercises, the focus of A2 pt.1 was clearly to get students to learn about designing classes and make their own design choices. Before this assignment, we mostly had classes handed to us that we had to put further work into. Building a class from scratch, however, is a completely different matter.

For me, the toughest part about A2 pt.1 was simply beginning. Since the assignment was all about design, I knew I needed to first design on paper the structure of my class, and then code for it. At first, I was unsure whether it should be something like a parent class, and then a star, bar, dot and leaf child class. It seemed a little odd to me that to build a tree, the user would have to use different constructors. And then how would the __repr__ method work? I also had to be careful with duplicating code, because that would be a major design flaw. This assignment really put into the light the difference between coding and designing a program. It's much more work making decisions and being sure that they are the correct ones!

W8: LinkedLists

Although it is confusing, I enjoyed learning the two methods of thinking about LinkedLists. However, while the distinction between the two methods seems crystal clear as the prof explains it in class, sitting alone before my computer, it suddenly becomes difficult to distinguish them.

So first, before I reflect on LinkedLists, a short note on the two methods (see link):

1) This is the "list within a list" structure, where a LinkedList has a "head" or "value" and the rest of it, which is also a LinkedList. A format like this is useful, because each list has is the same and so the same operations can be performed on them.

2) The "node and reference" structure, where a LinkedList is more like a chain. Each chain is node, that contains a value and a reference to the next node. This format is useful because a programmer doesn't delve layer by layer into the list, but rather jump from node to node.

Right now, I think I'm more familiar with the first method, just because we've been focusing a great deal on recursion and the nested lists idea goes way back to the first weeks of this semester. However, I'm getting the feeling that the prof leans more towards the second method, which I must admit, seems like it'd been easier if only I could master it.

Though I'm not quite there yet, I am slowly understanding both methods better (the lab tutorials are extremely challenging but informative). Also, did I mention how much I've come to appreciate tuple unpacking?! It comes back full force with LinkedLists, and finally I've understood why a programmer would do tuple unpacking rather than conventional line by line variable assignments. If you do separate variable assignments, its possible that a value (especially in a mutable class) has changed before you assign it. However, with tuple unpacking, the left side of the equation symbol is evaluated first, and then assigned to the right side. MAGIC!

W7: Recursion

To state it simply, recursion in computer programming is when a function calls itself. One might ask, like I did at first, how a recursive function is useful if its definition implies that it runs for eternity?

Trying to call an improperly written recursive function, for example:

    def f(x):
        return f(x)

will indeed get you:

    RuntimeError: maximum recursion depth exceeded.

Which basically means that Python apologizes for being unable to run the function infinitely. So the example above is not exactly a recursive function.

Good recursive functions will have two basic components. First, a "base case" which tells the computer what to do once a certain condition is met, and second, a "recursive step" where the function calls itself.

Consider the following example. Suppose you have jar containing two flavors of candy: mango and raspberry. You detest mango but love raspberry. You blindly pick out one piece of candy at a time. If it's raspberry, you eat it and walk off. If it's mango, you discard it, and reach again. If you reach the bottom of the jar, you walk off.

In this example, the function can be seen as you reaching into the candy jar. The base case is finding a raspberry candy, eating it, and walking off. Here, walking off the same as exiting the function and it also occurs if the jar is empty. The recursive step is finding a mango candy and reaching in the jar, again. This is the part where the function calls itself (i.e. you call on your arm to repeat the action).

As you can see from the example, the base case is equally as important as the recursive step. The base case is the entire purpose of the function and the recursive step is the means to get there. A bad base case is equally as detrimental as a faulty recursive step. Furthermore, although it is usually very easy to see when recursion is required (do you have to do the same thing multiple times?) it is not so easy to decide what exactly you want to get out of it.

It is apparent how useful recursion is in computer programming. A programmer may have something they want to achieve that will take several loops but they do not know exactly how many. Thus recursion is necessary:

    1) Recursion saves space by replacing the many lines of code for (regular) loops
    2) It is more readable and better follows the human process of problem-solving
    3) It can achieve something that may take zero loops or hundreds of loops.

The last point is especially demonstrated when working with objects such as Trees, where a Tree can be a single node or conversely hundreds upon hundreds of nodes and leafs. A single recursive function can, for example, count how many nodes there are in any type of Tree, no matter what size. Such cannot be achieved by a single regular function.