Sorting and Efficiency

Big-Oh. What a fantastic term. When I first saw it, I was completely confused what it meant or what purpose it served. Matter of fact, I came across it after I was ill for a week and was catching up. I was impressed with how fundamental efficiency, and big-Oh, big-Theta, and big-Omega, were in the field of computer science. At around the same time it was being covered in CSC148, it was also being covered in CSC165. I feel like that enhanced my understanding of the concept, as I not only understood the efficiency of programs, I had to recognize it and prove it.

Sorting is evidently a key component in programming. By working with sorted values, it becomes easier to find a given objects. In addition, it allows for a certain level of organization to be present in the data being manipulated by the code. Many sorting algorithms have emerged, each with their own efficiency benefits. It ultimately comes down to the size of the list to determine whether or not the more "advanced" algorithms are necessary, or whether they would actually extend the time needed to sort in the first place.

But this seems to only be looking at sorting at a very basic level. I find the different sorting algorithms to be very interesting when they are compared from an efficiency standpoint. First I examined the three methods of sorting that we were taught last term in CSC108: bubble sort, selection sort, and insertion sort. Efficiency was briefly touched upon, but only in reference to the best and worst cases. Looking back, bubble and selection sort's efficiencies were big-Theta(n^2). Insertion sort was possible more efficient, with the upper bound being n^2, but the lower bound being n. In addition, I recently examined quicksort. While it has the same worst possible runtime, it's average runtime is significantly faster than the three previously mentioned functions, as it is O(n*log(n)). I guess that's why it is called "quicksort".

This is all very interesting, but ultimately, what is it's significance? While I think that efficiency was most easily visualised in sorting functions, it has a much greater role in programming overall. At the fundamental level, efficiency can mean the difference between a usable/functional program and one that isn't. Maximizing efficiency is crucial for ever step of the way, as poor efficiency can become exponentially worse in a program.

So that's my last SLOG. It's not pretty, it's not fantastic, but it's an honest reflection of what I've learned. Bye guys :)

Hey there comp sci, it's been a while

This is mostly a placeholder update, if you will. I have been out of the world of programming for quite some time due to severe illness. I'm back though! Just in time for the term test!

I have very little to contribute to this SLOG at the moment. Minor studying hasn't been eventful enough to be anything of note. I also haven't been to class in over a week thanks to my sickness (lab today will be fun!). I think I'll just get back to studying and then update based on my progress.

See you soon!

A rather uneventful week

This past week was kind of slow for whatever reason. While I find trees to be fascinating, I strongly dislike how the course is approaching them. There's only so many times I can create tree classes for the sake of making a tree class. I want to see the theory behind this applied! I feel like there's so much more I could do now, knowing about recursion and data trees. But it's all being underutilized as we've yet to implement them in a practical sense. I just think that A2 Part 1, for instance, is just so pointless. I understand that we need to create the classes so that we can do A2 Part 2, but I kind of wish we could've done both segments simultaneously. That's just my two cents, however.

On a different note, fiddling around with functions for the LinkedList class in lab this week was quite interesting. I really felt that I am becoming more and more comfortable with recursion by doing things like this. That being said, I don't really have all that much to talk about this week. So I suppose I'll post again next week.

Ciao!

Recursion

def week_seven(blog):
"""We've finally arrived to what is constantly described as the core of CSC148. While the subject is initially bewildering, it is actually relatively simple. Basically, recursion is when a function calls on itself, which is recursion when a function calls on itself, which is recursion is when a function calls on itself- you get the point. What makes recursion so brilliant is what it allows you to do. Without recursion, programming would be significantly more challenging and less efficient. Data trees, for example, are made possible by recursion. Quite frankly, writing about this topic is particularly daunting because of its scope. Instead, I'll focus on my own "journey", if you may, as I learned about this subject.

Way back in high school, I did some programming competitions. My coding was pretty basic, but I still enjoyed doing them. I still remember looking at the solutions, and coming across "simple recursion" as the descriptions. Based on my knowledge at the time, I had no idea what this mysterious "recursion" was. Though, to be fair, I didn't know what a function was either. Now that I'm more knowledgeable about the subject, all those old questions seem so much more simple.

When I learned about recursion for the first time in this class, I was surprised at how simple it was. I always wondered "if a function calls on itself, when will it ever end?". Well, the use of if statements makes the answer quite simple. Though it took a moment to wrap my head around the concept, after this point (and my first recursion tutorial), I felt as though I knew "how to recursion". I practiced tracing recursive functions a little bit in order to fully grasp the concept, and I feel like I figured it out (well, at least I did until I got my marks for the first question of the term test). From there I moved on to trying to implement recursive functions into my code. At the most basic level it was quite simple, however as I described in my last entry, implementing it into tour.py of A1 was a little mind boggling. To be honest I'm still a little confused how that ended up working out, though I'm not complaining.

From there I learned more and more about the usefulness of recursion. So many things were rendered simpler through it's use. I found data trees to be fascinating, and the use of recursion in order to establish and traverse through them was also very interesting. Ultimately, I feel like I still know nothing of the true power of recursion, though I am looking forward to learning more about it!"""

    if (blog.read()):
        return "Thanks for reading :)"
    else:
        return week_seven(blog)

Well, damn. My first SLOG was saved to drafts apparently. Oh well.

For what it's worth, I'll post it now.

Week in review - Assignment #1

After a long hiatus from the SLOG after my first (and only) post on week 3, I am back to the world of computer science blogging. My page is quite barren, but it's better late than never. I hope to touch on the absent weeks in this particular update.

I feel like firstly I should address the elephant in the room: Assignment #1. Thanks to a nice amount of midterms and other assignments, I got started to work on it a little later than I should have. Thankfully, my partner had already begun and thus we were able to breeze through the first four steps. Setting up classes and methods was essentially CSC108 review anyway. While there was quite a bit of polishing that needed to be done to the code, it functioned so we left it be for the time being. The fun part began when we needed to come up with implement the given algorithm to solve the puzzle. The mysterious i value irritated us to no end as we spend quite a long time figuring out what it was. First we tried 1, but that didn't. Then we tried 2, but we started to get errors. Next, we tried to make i dynamic by basing it off of the current n value, but n - 1 and n // 2 to no avail. We finally decided to create a spreadsheet of which i value, for a given n value, would give the ideal number of moves. After we went through it a bit, I noticed a pattern. For odd numbered n's, i was half of n plus one. For even numbered n's, i was half of n. Putting that into programming format, i = (n // 2) + 1, which my partner simplified into i = (n + 1) // 2. Don't worry, I'm done with the shop-talk for now.

Armed with the mystical i value, we were able to start trying to implement the algorithm. Many recursive adventures began at this point, as we aimlessly tried different combinations for a couple hours. Eventually we remembered what was demonstrated in lecture, and broke the problem into two steps. One that would be a recursive function for 4 stools, and another that would be a recursive function to solve for 3 stools. We based our 3 stool function off of the one shown in lecture (giving credit, of course), and gave it the pretty fly name "Anne"-something (it's slipped my memory). Next we made our "pilgrim" function. By a sudden brainwave, I came up with a solution that I didn't fully comprehend (not going to lie, it still boggles my mind how it works), which almost worked but returned an error when the program tried to move a non-existent cheese. After another hour of slamming our heads against the desk, we discovered that in one line we wrote "n - 1" instead of "n - i". This resulted in another hour of slamming our heads against the desk in frustration. I swear, Satan himself manifests in the code sometimes. 

After we implemented the mysterious recursive function that by some computer magic actually worked, we decided to leave understanding what on earth we just implemented until later. Now was the fun part: polishing the code. In the process of making the code more efficient, we broke our program and then fixed it. Next, we finalized our docstrings and examples, and were about ready to call it a night. But despite how much the fatigue was setting it, we just had to do the bonus question. It was more difficult than I originally expected it to be, but after thinking through it, it was easily solved using surrogate TOAHModels and a couple for-loops. 

All in all it's been a fun (albeit long) week in the world of computer science. I've decided to start regularly posting to this in an attempt to salvage part of my mark. Also, it's actually kind of fun.

Until next week!

OOPs, I did it again - Object Oriented Programming

Object-oriented programming. I feel compelled to make a deep comment on how this form of programming mirrors our reality, on the basis that both are composed of objects. In reality, I really just think that it's a cool and effective method of programming. Manipulating these objects in a virtual space allows for great control and depth in the utilization of computers. Although that came out as garbled tech-nonsense, my point still stands. I love OOP because the objects within it act as building blocks for the creation of your desires software. You're basically given the building blocks, and through a mixture of logic and creative, one can create whatever they want. In a sense, object oriented programming is like playing God as you manipulate and control this digital universe.

Enough with all these analogies, though! I'm excited to learn more about object-oriented programming, and further my abilities to utilize modern technology. I want to be able to express myself through technology, and knowledge in object-oriented programming will allow me to do that.

This was a rough first post, but I'm still getting into the swing of things. I'll keep you posted on my progress as I delve into the world of computer science!