Week 11 - Sorting and Efficiency

Sorting and efficiency are two central topics in computer science, yet manage to be overlooked by most computer scientists of the 21st century. Sorting simply means to organize objects in a particular order, generally ascending or descending, and efficiency is a measure of performance versus time, in computer science this is with regards to programs. This we we combined the two together in order to see how something we take to be so trivial (sorting) is actually measured and pitting different sorting algorithms against one another in terms of efficieny.

Before we can analyze anything, we need to be aware of these "sorting algorithms". It turns out wikipedia lists a plethora of sorting algorithms, including bubble, insertion, selection, quick, merge, and tim sort. Consequently the prior list is sorted in order from least to most efficient. But what does it mean to be efficient? As a computer scientist we measure efficiency in terms of constant time and and the number of iterations we use within our algorithm. This "time complexity" lives within a notation denoted by "Big-O" and can represent an algorithms worst, average, and best expected run time with respect to constant time. The most common run times we use to analyze the run times of programs are denoted by the following; O(n), O(lg n), O(n lg n), O(n^2), O(2^n), O(n!), and O(1). It should be mentioned that the lower number within the brackets represent the most efficient run time.

Lets analyze selection sort, the algorithm can be found below:

def select(L):
    """Produce copy of L in sorted order

    >>> select([3, 1, 2])
    [1, 2, 3]
    """
    L1 = L[:]
    for i in range(len(L1)):
        m = min(L1[i:])
        j = L1.index(m,i)
        L1[i], L1[j] = L1[j], L1[i]
    return L1


We have a list <L1> which is being iterated through by the for loop, assuming our list length is n, iterating through n items will take O(n) time. Everything else within the loop is O(1) time approximately because we generalize variable assignments and such to this order, rendering the program O(n). This makes sense, but the line where we copy <L> to <L1> could also take O(n) steps if we were to imagine it with a for loop. This is to say the program has O(n) + O(n) time, but this is would simply be 2*O(n) which is a constant multiplied by our scaling time complexity. The key to time complexity is that we only care about scaling variables, therefore we drop the 2 and end up with O(n) time.

With this being said, tim sort is the most interesting sorting algorithm brought up this week seeing that it is a compilation of many sorts and utilizes certain aspects for certain scenarios, yielding the most optimal results. Although quick sort may be slower than selection sort when it comes to really small lists, tim sort would use the better of the two in the best case.

Week 10 - Sorts and BST

This week we covered various kinds of sorts. Some of them include selection, quick, merge, and tim sort. Of the sorts mentioned, we go from slowest sorting time to fastest respectively. Reasons for this were analyzed in class, mentioning how selection sort iterates n time to see what needs to be swapped, then another n times to swap. This results in O(n^2) time, as opposed to merge sort which cuts the list in half each time, then joines them back together, the join in itself is about n times, but the splitting is log(n), yielding a combined time of n log(n) time. Now we just observe these sorts based on their strict algorithms that do the same job yet in a different way, so why not combine all these sorts to form a gigantic one that does the job best in certain scenarios? Well that is the definition of tim sort, made specifically for Python.

Finishing up BST's we covered deleting from a BST and forming linked lists out of them. This was fairly challenging because creating the Linked List nodes required you to remember that once an object is created on the stack in python, it stays there until the code is done with it, so if you create a linked list node in the call, it is that object that will be within the prior. This was a key component to solving the lab and caused great pain for my partner and I to solve. Other than that BST's were fairly straight forward and I can see great applications of this being to store a list of contacts or numbers where indexing is crucial.

Week 9 - Projects and Stress

This week we have our exercise due, and the second part of our second assignment due next week. I have finished the exercise and just checked my automarking results. Thankfully they show perfect, but for our second part of assignment two I am quite puzzled. The assignments in computer science are pretty vague and I always feel as if they do not teach you everything you need to know for them. Sure, the tools we use are all taught, but the concepts are quite advanced, mainly the cheese algorithm in the first assignment. It's a pleasure getting to deal with such high level algorithms, but it's also scary when your mark is on the line. I've actually gotten a partner for the first time this year to help me out with this assignment, so this collaboration is certainly new and welcomed.

Other than projects in computer science, I have a job application I'm currently working on. The program I need to build for this application is far more advanced than the topics we cover in first year computer science, so hopefully I have enough energy to see me through this test.

Week 8 - Linked Lists

This week we covered linked lists and talked about how they are data structures which are made of nodes that point from one to another. The nodes are represented by objects and contain pointers allowing for a way to explore the list iterating from one object to the next via pointers. Linked lists can come in two forms. One being a singley linked list allowing for appending and deleting from the end, and doubley linked lists that can be appended to and deleted from both the beginning and end of the list. This data structure differs from that of a normal list or array in the sense that it is not indexed, and the only way to explore the list is through iteration. This being the case, exploring and finding an element in a linked list will take O(n) time. 

In addition to linked lists we talked about binary trees and demonstrated methods that were used in the __repr__ method to make them more humanly readable. It is through this demonstration that we saw the power of the traversal techniques learned in the prior weeks. 

Week 7 - Recursion

Up until now we've been taught recursion at a very basic level with nested lists as our starting block, and have expanded to more complex things such as trees. Through this transition the simple concepts of recursion have stayed stagnant.

Recursion is the process of repeating items in a self-similar way, with respect to functions it is the act of calling a function definition within itself. This in itself sounds like an infinite series of process considering that a definition is made up of itself (which is forbidden in English grammar). The solution to this problem is what's called a base case. A base case is defined as something we know for sure, and is unchanging. For example, if we were calculating the n'th factorial, we always know that if n is 0 then the 0th factorial is 1. Why? Well based on the definition of a factorial (n*(n-1)*...*1). Since 0 is a special case, it is independent of the definition of a factorial, hence we always know the answer to it. Using this base case, we have a result that will exit the infinite calls. This being the case, we just have to make sure that we reduce the larger problem to many smaller problems involving the base case, thus yielding the appropriate recursive result.

It is this ideology of recursion that enhances an individuals thought process to be expanded across multiple areas of thinking, thus altering that thought process to be adaptable to multiple scenarios. Just as we were introduced to recursion through lists, we are now adapting this ideology to trees and linked lists. This is a transition to abstract data structures, which involves some high order thinking yet retains that constant definition of recursion.

Week 6 - Scavenging Tree's

This week we reviewed tree's and various ways to search them involving; pre-order, post-order, in-order. These are traversal techniques which end up exploring every node within the tree, but a particular order. We've learned some new terminology with respect to trees, the main one's being the root, leaves, children and parents. The root is the starting node of a tree, a tree which is defined as a node and all it's children. Leaves are nodes which have no children. Nodes which have children are referred to as parents. All of these terms help us better describe trees, and further in the course will help develop algorithms with respect to trees.

In addition to learning about general trees, we were introduced to the binary tree. This is a specialized tree in which each node only refers to two children (otherwise none) are organized in such a way that the right child is greater than the parent, and consequently, the left child is less than the parent. This organization strategy allows for in-order traversals of this tree to result in exploring the tree from smallest values to largest.

As important as trees are claimed to be, I personally don't find a great use for them right now. We've seen them recursively implemented through lists in Python, but they appear to be more an organizational strategy better suited for Object Oriented Programming architecture.

Week 5 - More Recursion and Assignments!

This week in lecture and tutorial we covered more approaches to recursion. Recursion is a pretty complicated topic to understand, once understood you have to train your mind to think in that "recursive" term. This is something that's plagued me for 2 years (yes I started tackling recursion a mere 2 years ago). I've seen many people fail completely at recursion and those who get it in an instant. I've always leaned towards the failing end, although I would understand the reasoning behind it, I've never been able to code my ideas recursively. This week however I think I've achieved something great in my life because I've realized the secret to recursion and have demonstrated that in tutorial.

When taught recursion in lecture, Prof.Heap made it clear to think of the most simplest case and work up from there, using the values obtained previously to propel your examples further and further until you have a generalized formula. Now although this idea is relatively simplistic to understand, being able to combine this ideology with that of pythonic paradigms is yet another challenge. What I mean by this is list comprehensions. Thinking in terms of list comprehensions seemed like an impossible task when I was first introduced to it, all I could think of was "how did he think of this?". It wasn't until tutorial when I was faced with a similar problem that I was able to think like Prof.Heap and end up coding an example that he would have created himself. This was a moment in which I realized the secret to recursive programming, but much is still yet to be learned.

We have our first assignment due this week, an assignment I figured would be easy like CSC108's last semester. Boy was I Wrong. This assignment is the hardest assignment I've been given, why? Well, this assignment is based around solving a conjecture, something that no one in the world has created a definitive solution to. We are asked to provide a "good" approximation? This is a seemingly impossible task but a task we are forced to take on. I've tried many techniques of thinking of the problem and only have one issue which is how to switch between free stools, this is the trick to the problem but I have no idea how to do it with recursion. Previously I said that I now understood recursion, but I am still not a master at it since I cannot solve this problem.

In summary, this week has opened my mind to many new possibilities of programming, and has also humbled me with the task of attacking a conjecture.