W12: End of the Year!

Today was the last day of class!! CLASSES ARE OVER!!!

I'm so ecstatic that finally after all these hours, days and weeks of university, never-ending assignments and stress, that classes are finally over!! I'm also amazed at how fast the year has gone by... one year of university passed in a snap.

Still, despite how fast it went by, university certainly is NOT a snap (whoever says so is either not human or lying or in a bogus university, no offense). As a beginner in CS, I can't even describe how much I learned in CSC108 and CSC148. In September I'd barely touched coding, and in the past months I've done hours and hours of it, learning about syntax, exceptions and errors, object-oriented programming, recursion, lists and binary search trees and run-time. WOW!

Still, I think the most important thing I've learned is what computer science is about and furthermore, how much of it there is still to learn. I've barely stepped a toe onto the vast field of computer science. It's been an eyeopener to realize, also, that computer science is not at all about the computer; the more important thing is the programmer's ability to solve problems and translate their solution into code. I thought coming into university that the most difficult aspect would be learn the Python language and syntax. I was dead wrong. The computer can tell you where you've made a syntax error, but nobody can solve a problem for you (unfortunately).

Despite my difficulties with computer science (I definitely have a lot of studying to do for the exam), after this year I am certain I want to pursue a computer science POSt and career. The appeal with CS is that although it is challenging, it is also extremely rewarding. It engages the programmer by exercising their creativity, problem-solving skills and communication abilities. And the feeling you get once you finish a problem is unrivaled!

Thank you CS148 for showing me something I can see myself doing in the future. You were an extremely difficult course, but I learned a lot from you!

To end off this SLOG, a quote that I feel accurately sums up all of my realizations this year:

Accomplishment will prove to be a journey, not a destination. 
– Dwight Eisenhower

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.