Week 11: Sorting and Efficiency

Here we are again, writing my blog for the final time. This week, we discuss the topics of sorting and efficiency. What, I talked about sorting last week? Yeah well, uh, so what. Let's talk about it more. In programming, sorting is the method of taking a list, and rearranging elements to a certain order, typically smallest to largest or vice versa. Why do we need sorting in programming you say? Well if you have to ask that, then you don't deserve an answer.

Sorting algorithms come in many different shapes and sizes, and they all have different runtimes. Runtimes are the length an algorithm takes to complete, mostly depending on the size of the list, in which case we will call 'n'. For example, the run time of a simple sort such as bubble sort takes n^2 steps. Let's analyse why.

Let's say we want to sort the list [8,2,9,6,7,3,1] from smallest to largest. Bubble sort works by looking at the first element in the list, and comparing it to the next adjacent one. If it's smaller than the one next to it, it will swap them. This goes down the list, and we do this step the same amount of times as there are elements in the list. So we sift through the list n times because we check each element, and we do that, n times, one for each element in the list, so we have n * n steps, or n^2 steps. Let's sort this list to see why.

 [8,2,9,6,7,3,1]

 [8,2,9,6,7,3,1] We look at the 8 and 2, 2 is smaller than 8, so we swap them.
  ^ ^
 [2,8,9,6,7,3,1] Then we look at 8 and 9, 8 is smaller than 9 so don't do anything.
     ^ ^
 [2,8,9,6,7,3,1] Then we look at 9 and 6, where we swap them because 6 is smaller than 8.
        ^ ^
 [2,8,6,9,7,3,1] Then we look at 9 and 7, where 9 is greater than 7 so we swap them.
           ^ ^
 [2,8,6,7,9,3,1] Then we look at 9 and 3, where 9 is greater than 3 so we swap them.
              ^ ^
 [2,8,6,7,3,9,1] Then finally we look at 9 and 1, where 9 is greater than 1 so we swap them.
                 ^ ^
Notice we did this step 7, times because there are 7 elements in the list. But we then start again and perform those 7 checks 7 times, so 7*7 steps, 49 steps. This is how we can analyse the runtime of a sorting algorithm.

There are many different types of sorts, with different runtime lengths. There`s runtime lengths of nlog(n), like quick or heapsort, which for our purposes is the most efficient sorting algorithm when using a standard list or scenario.

My personal experience with sorting and efficiency goes back to grade 11, and my introduction to computer science. We spent an entire unit simply discussing sorting algorithms and how to properly know which to use in certain situations as well as how to program them. A video we watched back then that we got to watch was Sorting out Sorting, a movie from 1981 which was created at University of Toronto. The video basically just goes over different types of sorts and how they execute but what I found the most interesting was during the credits, we get to see a time-lapse of a whole variety of sorts race against eachother in sorting these scattered dots. As we can see from the screenshot below, shellsort, quicksort and tree selection sort are already completed with heapsort close behind. These are because for an array of data with a large size, runtimes with logarithmic lengths will work wonders compared to ones with quadratic runtimes.

https://www.youtube.com/watch?v=SJwEwA5gOkM

 This pretty much sums up my experience with sorting algorithms and efficiency, I hope you had a fun time reading my last post or my entire blog in total. I sure had fun writing it! I wish you, the reader, farewell and good luck with your future endeavors. Happy programming!

Week 10: Sorting

This week in class we discuss sorting. Some students may have been confused as to why we're discussing something we talked about in csc148, but I knew where this was going. Sorting is a little more complicated than most people think it to be. It's not just about getting the job done, it's about efficiency.

We discussed how different types of sorts have different runtimes. We discussed the runtimes of sorts like bubble, insertion, selection, quick and merge. We noted that in many scenarios quick and merge sort have on average better runtimes than the others with nLogn, where n represents the length of the list. This is because sorts like merge and quick recursively iterate through sorting, allowing for cutting down the amount of work it has to complete. I actually have a lot of experience with these types of sorting algorithms from high school where we had a huge section of our curriculum based around it. We even got to watch a very interesting (and boring) video called sorting out sorting, where it just races a whole bunch of different sorting algorithms. Can you guess who won? You guessed right, quicksort, with tree insertion and heap sort following closely behind. But I'll get more into that next week, when I'm forced to write about sorting.

Week 9: Binary Search Trees

Here we are, back again, me writing, you reading about programming. What's this week you ask, binary search trees of course. "What's a binary search tree?" you may ask, well let me tell you. I binary search tree is like an ordinary binary tree, only the nodes are ordered or sorted based on certain properties. The left subtree will contain nodes with the root less than the trees root. The right subtree will contain nodes with the root greater than the trees root. Both the left and right subtrees are binary search trees as well as there are no duplicate nodes.


That's what defines a binary search tree by definition, let's look at an example of one. The image to the left is an example of a binary search tree. Notice the entire trees root is an 8. This means everything to the left of it must be less than 8. If we look at the left subtree, the root it 3, which is less than 8. Then we can look at that 3 as being the root of a binary search tree. Everything to the left of the 3 is less than it, being only the 1. Everything to the right of the 3 must be greater than it. 6 is the next root under 3. Everything to left of 6 must be less, which it is and everything to the right must be greater, which it is.

My experience with Binary search trees has contained some trouble itself. While I understand the concept of them and am comfortable with manipulating them. I find I have trouble with writing one recursively. But once again, this goes back to my trouble with recursion itself. I'm slowly improving, but I still find trouble dealing with subjects like this.

Week 8: Linked List

Linked List, the ole list that refers to a list that refers to list that refers to... you get my point. A linked list is a data structure with two parts. A node, that contains a value of some sort, and a pointer, or a reference to another linked list. Along with trees, they are also considered abstract data types.

In class we talked about the two ways to think about a linked list. One as thinking a linked list contains a value, then the remaining list, or the rest of it. The other way is as nodes with reference to nodes, the more traditional way. We went over created a linked list using multiple classes like a node class and a wrapper class. It took me an incredible amount of time to understand what a wrapper class was. Even now, I'm not certain, but I believe it is used to hold the entire linked list and hold information that would be useful for methods like inserting or deleting nodes.

We also discussed how we can essentially create trees that are linked lists. Then we went to talk about binary search trees. Binary search trees are binary trees that for each root, it will have maximum two subtrees. All values to the left of the root will be less than the root and all values to the right of the root will be larger than the root. This assists in locating specific nodes as it assists traversing the tree when we can eliminate half the tree on each iteration through it.

To sum things up, this week we discussed linked lists and binary search trees, which both are abstract data types that revolve around nodes and references to other abstract data types of similar objects. My personal experience with this topic is that I still have a fair amount of trouble visualizing how to recursively go through and perform whatever method I want. But this goes back to my trouble with recursion itself which over the next view weeks I will try and improve.

Week 7: Recursion

What is recursion you might ask. Well, to think about it visually, if you place a mirror in front of another mirror, both facing eachother, you would get an infinite amount of reflections. The reflection of one mirror, essentially reflects itself, reflecting itself, reflecting itself and so on... If we take that logic, and use it with computer science and math, we can do all sorts of wonderful things.

Let's say we wanted to write a function to evaluate the factorial of a given number:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

When you give an n value, it will start to check if it is 0, otherwise known as the base case, where it returns a static value and not a recursive one. If  is not 0, it will multiply it by the factorial function of n - 1. What this does is repeatedly do the function to retrieve values until we hit the base case. In this case, we ca determine 4! = 4 * 3! = 4 * 3 * 2! = 4 * 3* 2 * 1! = 4 * 3 * 2 * 1 * 1 = 24. You have to make sure you have the base case or else the function will recurs infinitely.

So now that I've briefly talked about what recursion is and an example of how it works I guess I can get to my experience with it. I first encountered recursion in my grade 11 computer science class where we were learning C++. Every student had to pick a topic in computer science and give a brief talk on what it is and how to do it. Of course most people pick a topic that suits there likes and is easy for them. We had some simple topics like reading/writing to a file, creating a GUI, I did some game design and graphics. And then easily the smartest kid in the class goes up, and talks about recursion and trees. Every student is both amazed and completely confused at the topic. Barely anyone can code it from nothing or even comprehend it. Heck, I could barely even understand what he was saying. He goes to talk about the practicality of it and its uses, I'm just sitting there thinking that any example he was doing could be done in another way. He asks us to code a function to find the greatest common divisor of two numbers. I figure yeah I could easily do this, and I wrote something similar to this, only with C++ syntax instead:

def GCD(x, y):

    num = []

    for n in range(1,max(x,y)+1):

        if x % n == 0 and y % n == 0:

            num.append(n)

    return max(num)

I figure "yeah, I did that fast, and it looks efficient, there's no way you can do this better." Then he shows this:

def GCD_recurs(x, y):

    if (0 == x % y):

        return y

    return GCD_recurs(y, x%y) 

HOW'D HE DO THAT! That was genius. I would have never thought of that. Since that moment. Recursion has always puzzled me on how to know what to do. I still have trouble, in class and in the assignments on knowing what to recurs. 

So that is my experience with recursion, a both lovely and infuriating topic, I both hope to use it forever and never use it again. 

Week 6: Trees

Well, here we are again, me writing and you reading about computer science. Well, now that assignment one is complete, we can now begin on trees. Trees are a completely new data structure to me, at least to program so it can provide some trouble. It's extremely difficult to visualize how trees are structured as there's no way to essentially print what a tree looks like inn python without writing your own custom str method.

The reason I presume for us to learn about trees is the way we navigate through them. And of course, as you guessed it, it's recursively. The reason we do this is because all trees start with a root node. Each root node and possibly children. But some of the children might have it's own children. We can essentially view each original child and all their children as it's own tree, therefore looking a layer deeper into the tree. When a node has no children, that node is referred to as a leaf and still can be viewed as a tree itself, just with no children.

In my continual learning of computer science and programming, I've realized if I ever need help with concepts, while I can google or ask a TA, I've only just realized that there's hundreds of other SLOGS out there for me to read. I've become fond of http://slogslogslogslog.blogspot.ca/ It seems that student, "Penguins Go Noot" and I share some of the same problems, but he/she has found solutions that have helped me out.

The hardest part of this week has just been trying to picture and visualize a tree structure, but I'm sure with a lot of practice and constant work, I'll get the hang of it.

Week 5: Tower of Hanoi

So you're given 3 stools and 3 blocks that rest on the first stool, from largest to smallest. You are given the task to move all 3 blocks from the first to last stool one block at a time and can only be placed on an empty stool or one with a larger block on it. After playing this game for a couple of rounds, you notice a pattern. You notice there are precisely efficient ways to solve this in the least amount of steps. After some guess and check, one would notice that it takes (2^n)-1 steps. This can be done for any amount of blocks, where n represents that number.

That is the classic Tower of Hanoi problem given to us this week. Only, it's been tweaked ever so slightly. They added a stool. You might think that only makes it simpler. Well, it times in terms of completing the game, but not for figuring out the most efficient way to do it.

The classic 3 stool Tower of Hanoi problem is world famous for being solvable with recursive functions, and as we discussed last week, recursion is the property of referencing itself. In the 4 stool Tower of Hanoi problem, it also used recursion, but something a little extra. There really is no defined perfect solution for the most efficient way to find the number of steps. No matter what you Google or Bing (jk, don't bing it), everyone has a different opinion. The only agreed part of solving the 4 stool Tower of Hanoi is that there's 3 steps. You move N-K blocks to an intermediate stool, then K stools to the destination, then those N-K stools you previously moved to the destination, While N is the number of blocks, and K is a dynamic amount that changes. No one really agrees on how to determine K. If you want what I think, after computation, I determined K = ciel((2n)^(1/2))-1. While this is not necessarily the best solution, it does result in the most efficient amount of steps. With 4 blocks = 9 moves, 5 blocks = 13 moves, 6 blocks = 17 moves, etc.

Well that covers the Tower of Hanoi problem we discussed this week. We also discussed scopes and namespaces. We covered topics like global, local and non-local variables and saving names in a namespace as well as proper naming of variables and functions. That should do for this week, stay tuned for next week when we talk about trees, so I'll just make like one and leaf (haha, get it?).