Sorting Algorithms, Oh look! More Sorting Algorithms

Hello Everyone,

Well, I'm in a rather melancholic mood, it appears that this may well be my last proper blog post for 148. How time flits away, drawing us inexorably to our demise.

First,  some limericks:

Heap taught us so much so deep,
How much we thought, should our brains keep,
Now it matters naught, we are in steep
And many times feel like saying 'beep' this 'beep'

My dear TA, alas! This is the last time that you shall have to endure my poetry (if you read it at all that is). Will you miss it? I do hope that it brightened up your day ever so little.

Anyways, the relentless march of continuity hath ordained that we must be parted. So back to Sorting.

Why do we care so much about sorting algorithms?
Computers essentially do things that human beings are not very good or very slow at or both. Sorting is one of the things which human beings are just not suited to. I'll illustrate with an example - Consider a town with a million people. Say you had everyone's names and phone numbers, how long do you think it would take even for a group of 10 people to sort all those names alphabetically? A computer on the other hand would be able to sort such a list in a matter of at most a few minutes - even using bubblesort! So computers are inherently suited to handling large quantities of data which human beings are not quite so adept at. Moreover, given the ever increasing amount of stuff that is produced, sorting it to produce usable information is an every increasing need.

Approaches?
In my opinion, one of the remarkable thing about sorting is that people had 'thunk' up so many different ways of doing it. And moreover, these different methods vary so dramatically in their run-time. <- This really blows my mind. Just leveraging human creativity a little we can make such dramatic improvements.

Iterative Methods:
Really speaking no matter how clever you are, in the worst case, it's almost unavoidable that the run-time of a iterative algorithm will be any better than O(nlog(n)). In fact, I don't think very clever people can even come up with an algorithm that is better than O(n^2) for iterative algorithms. The reason being is that you're going to have to compare n items with other items at least 1 time and most often many more times than that.

Divide & Conquer Methods:
The most efficient method we have learnt is by far the sorting algorithms that use divide and conquer. They take advantage of the power of logarithms to keep run-times low. That's really the key here. To illustrate how powerful this concept is, think back to the guess a number game:

Guess a number between 1 and 100
User -> 50
Machine -> Too high  ## Notice that we've literally halved the interval that we need to guess at just in this one step
User -> 25
Machine -> Too low ## Again, same as above

In a very few steps we can narrow down the range of numbers that we have to guess to find the actual number. This is the power of logarithms and the power of divide and conquer algorithms.

Efficiency
This is something that really fascinates me about sorting algorithms. If you think about it, it's quicker work for a computer to use recursion repeatedly and make have a humongous call stack rather than simply compare individual list elements. A human being comparatively, would be much better suited to doing the comparison that keeping track of crazy numbers of recursive calls. It just goes to illustrate the point that computers are good at things that human beings are not good at. Although I think here that there is some trade-off between memory requirements & time. It seems like making a humongous call stack would require lots of memory even though it requires little time.

Big O
I think it's important to mention a few words about big O and what it really means. To be honest, this concept really deceived me. I though, "Meh, O(n^2) and O(nlog(n)) are almost the same, why are we being so pedantic and trying to make these teensy improvements in efficieny."  However, allow me to illustrate the difference:
Consider one sorting algorithm that runs in O(nlog(n)) and another that runs in O(n^2).
Consider input n = 100, then we get:
1) O(100^2) = 10,000
2) O(100 * log(100)) =roughly 648.6 ## Pretty huge difference eh?
Now consider a list of size 1000:
1) O(100^2) = 1,000,000
2) O(1000 * log(1000)) =roughly 9,960. ## Now the difference really pops!

Just imagine scaling up the data and what happens. Even for medium sized lists of say 100,000 elements (which by the way is a very realistic size - e.g. store each words that occurs in string that represents the contents of a book in a list), the run time of the quadratic algorithm goes into the billions! Whereas the other one is still in the low millions!

I don't know what else to write!

So the time has come to say good-bye dear TA,

God bless and good luck,

Yours,
Seigal

Sorting Algorithms

Hello E'rbody,

First a haiku :

Sorting a heap of cards,

words issued from Heap,

yet none penetrated too deep

I'm quiet disappointed that no one has thought yet to leave me any comments about my poetry. (Hint Leave a comment.)

This week we're learning yet more sorting algorithms. I think the purpose of learning so many different algorithms is so that we get a flavour of the myriad different methods there are to approach a computer science problem.

In any case, two of the algorithms we learned were normal iterative ones, and this week we started on quick sort which is a divide and conquer type. As recursion is becoming more and more natural to me, understanding the recursive nature of the divide and conquer algorithm is not so difficulty.

Essentially, there are three steps:

1) Break the problem into smaller ones

2) Solves the smaller ones recursively

3) Combine up the results from 2 in a proper fashion.

E.g:

Say I have [4, 2, 3, 1]

I'll split it [4, 2] & [3, 1]

Solve each part recursively so [2, 4] & [1, 3]

Now combine [2, 4, 1, 3]

But in our combine step we need to be careful and put the right thing in the right place, so put 4 and 2 in their right places [1, 2, 3, 4]

Ta-da sorted!

Anyways, that's all folks.

Adieu,

Seigal

Binary Search Trees

Goooooooood Morning UofTTTTTTTTTTT,

I hope at least some of you understand my salutation reference. If not, do yourself a favour and watch Good Morning Vietnam.

This week we've gotten into the basics of Binary Search Trees. But i'll talk about that more later. I think I finally learned the basic, most important and profound lesson of CSC148 yesterday night at 10.37PM whilst working on e3.

"THINK THEN CODE!"

which for me translates into 

"DON'T EVEN THINK ABOUT BOOTING THAT COMPUTER TILL YOU KNOW HOW YOU'RE GOING TO SOLVE THE PROBLEM".

All along I've been trying to hack my way through the exercises and assignments, and while they were initially fairly simple and just required knowing how to work syntax, now the require actual problem solving. As a result, this lesson is becoming more and more important.

Now, back to BSTs (kinda sounds like STDs no (!) :p) Essentially I think what is crucial about BSTs is that we learn about the properties and use their properties to solve our problems. For example, suppose we wanted to implement a __contains__ method in a BST class. The dumb way to do it would be to traverse through every single node in the the tree and check if it's there. The smart way to do it would be to use the fact that BST entries are arranged according to size and halve the number of checks at each node.

Anyways, I need to go program now.

Bye,

Seigal 

Linked Lists

Hello Folks,

First order of business, lousy poetry.

About LinkedLists did Danny teach,
He thought, surely all's a-peach!
But caused me to screech
And Beseech for release!

Actually, it isn't all that bad. Over the weekend I had to study for a mid-term on Monday so I hadn't the time to learn the readings.
LinkedLists are very interesting data structures. At least for me, it's the first time that I've ever been exposed to a recursively defined data structure. The general idea is that we don't need to worry about the details of what's at each particular node of the list and we don't need to worry about indexing etc matching up if we make changes to the node. All we need to be careful of is that once we do whatever method, that we still end up with a chain.
Actually, that is a good visualization for LinkedLists, they are chains on data. So for example, if we wanted to change the value at a particular link in the chain, we just need to go there and change that link.
Whilst say we wanted to add a new link to the chain, we would need to join the part of the chain before the position where we wanted to insert the new link to the the start of the new link as well as join the new link to the part of the old chain just after the position where we wanted to add the new link.

Not much else to say except that I really need more programming practice.

Live Long and Poop Regularly,
Seigal

Rec -I got it!- sion

Hello Y'all,

Today's the first day back from reading week. I'm actually happy that school started again! Now, a quadruplet:

In the scalding waters of Uoft was he baptized
So far said he,  Reading week? t'was a good revive
Before the Mid-term week demise
He prayed e'rday that he'd not be eulogized...

In a way I am a sadist, subjecting poor, over-worked and down trodden TAs to my god awful poetry. But hey, I have an audience! And they have to read it! Mwahahahaha...

Anyways, back to recursion.

As you would have noticed from my post last week, recursion completely escaped my mental grasp.  Whilst I generally agreed with the concept, I didn't understand it well at all. In particular I didn't understand what was happening. Then in class I thought I heard Danny ordain, "Understand it by the stack method!". So I went home and tried this...It was an utter disaster. So I wrote to the rightful minister of the Church of Python and Father Heap said, "Son, you have sinned! I said DO NOT UNDERSTAND it by the stack method. Learn it the human way, plug in unknown values!"
So I did this.

Now, a full week after receiving the Holy Father of the Church of Python's advice, I understand recursion.
You cannot imagine what a relief this is, along with no small measure of satisfaction.

So, what is recursion in my words? A few points that I have understood
1) Don't worry about details when understanding what the function does
2) First understand the big picture and then move to figuring out the details
3) Recursion  must have: a base case, a recursive call and the recursive call must be on smaller input.

How to code a recursive function?
1) Think about what will happen in the base case. ALWAYS start with the base case.
2) Once you have that down, then work on where the recursive call will go in your function
3) Make sure that the input to the recursive call is smaller than the input you started with

It's really hard to put in words my understanding of recursion. I agreed with the principle before, it's just that now the 'penny dropped'. It just makes sense now.

Debugging?
1) If you have a max rec depth error, either your recursive call is not working on a smaller input or your base case is not properly defined
2) Any other errors, such as wrong output values etc, just trace through your code starting from the smallest possible unput and work your way upward and see what happens.
I personally find it extremely helpful to trace through the recursive code on a input that's just one bigger than the case to visualize what is happening.

Is recursion useful?
Definitely, why? Because it is an intelligent way of coding. As the Holy Father has said, 'laziness my flock, it is the first virtue'. Since we wish to do the same thing over and over and over again, why rewrite the code again and again? This is where recursion comes in.
I think that many problems that could be solved by recursion could also be solved iteratively, but just thinking about the mess of that code is giving me a headache. Bottom line - recursion saves work. It may take a little longer to get started with the code because it requires more thinking but in the long run, it's a lot less overall work.

When to apply?
For me - If I hear myself say the words 'do this and then do this again' or 'over and over again' that means think recursion.
It's really easy if you sound off the way you're going to solve a problem.
For example -
I want to calculate the number of peaches on a peach tree. Suppose that the leaves can be either well leaves or peaches.
So I would say to myself, well I will go down the first branch and see if the first thing is a leaf or peach, then do that again for the second, then the third etc etc
I hear myself saying, 'do that again', which tells me to do the same thing which means recursion.

An example?
Here's my example of useful recursive code:
1) From a family tree, figuring out how many boys were born versus the number of girls.
2) Drawing beautiful fractals. I took MAT335 and the pictures in that course are really just breath-taking.
3) Recursively drawn video-game graphics. This is a fun one. Suppose you are in a forest. Then rather than making an entire forest, you just make portion of it. Then you use that to recursively make the entire forest whilst adjusting certain values such as the number of palm trees, number of rocks, number of birds etc etc

And finally, the Pièce de résistance :
Even GOD (the real one, not of Church of Python) uses recursion! Broccoli, Sunflowers, that fossilized sea animal, shells! How can it not be useful! (By the way, does this imply that one of god's virtues is laziness?)

Sorry for the long post.

Kuda Hafiz,

Seigal

Re-can't understand-sion

Hello Folks,

This last week has been an absolute nightmare.

A1 was due to Thursday, then I had another huge problem set due Friday, and another due Saturday AND even another due Sunday...AND even another due Monday.

Anyways, I guess this is part of school life. But back to CSC148, I am really struggling to understand how recursion works.

I understand the concept behind it that, that we just call the function that we are defining on a smaller input.

But the "penny" hasn't dropped on how this works. How does the function know what to do with the smaller input? How do we stop it from going on for ever? It's all very confusing.

Anyways, that's what I'm working on over reading week.

Bye,
Seigal

Dazed & Confused (& Panicked) :(

Folks,

The real flavour of CSC148 is coming on strong now.

This week we covered scopes for names in Python. It seems relatively straight-forward so I have nothing to say here.

However, last week's lab on unittest just blew my mind. Did you know that when using the unittest class you need to write test in front of each test case. I pulled my hair out until the very end of the tutorial when the TA mentioned that this was needed. Why Python? Why? The rest of you allows for such flexibility with names and here you want this?
This calls for a sonnet.

There once was a boy
He thought he knew Python
But unittest showed he knew bok-choy
And his confidence - a bygone!

To Danny : Please teach us unittest again

Thanks for reading the bad poetry.

Oh by the way, the panicked part in the title - Not started A1(!) FML.
Cheers,
Seigal