Week of March.30.2013 - Sorting and Efficiency

One of the most important concepts in Computer Science is efficiency.  When it comes to any language, a general algorithm must take the least amount of steps in order to complete the task, otherwise you will be wasting precious resources, and tasks may take longer.

For example, we learnt about insertion sort, and quick sort.  Both algorithms are used to sort items, and sorting items is extremely important, especially when we want to search within the list of items.  Binary search belongs to big O of lgn, meaning the time it takes to accomplish the task of finding an item takes only a constant multiplied by lgn, n being the number of steps, and it grows at a rate of lgn when the lists increases.  But one important precondition for this algorithm to work is if the list is sorted.  Insertion sort belongs to big O of n^2 for the average runtime, and quick sort on the other hand belongs to big O of nlgn as the average runtime, showing significant better performance over the former.

That being said, quick sort is not the only super sort that is capable of nlgn runtime.  Other sorts such as merge sort, which splits the list in half continuously, and merges the multiple lists into a sorted list which essentially breaks the problem into halves, which is where the lgn comes from, multiply that with the actual length of the list, and you get nlgn runtime.

March.01.2013

On the week of March.01.2013 we learnt about linked lists.  Luckily for me I had learned it previously in my high school, the difference was the use of variable names.  The next node would be initialized in the previous node stored in a variable called next, and this was all written under java.  So basically a linked lists is an object that consists of two variables, the current item value, and another variable, such as next, to point to the next list.  For example the linked list consisting of:

12 -> 14 -> 15 -> 17 -> None

Means that 12 is pointing to 14, which is pointing to 15 etc...  If I wanted to get to the node that consists of the item 15, I would refer to the head of the list, such that node with 15 is head.next.next.

Week of Feb.23.2013 - Recursion

Recursion to say the least is a difficult concept to wrap your head around.  Mainly because it involves the process of having a function to call itself, which is a common method of solving problems, especially problems with multiple depths, such as having to compute the sum of a given list of lists, or multi-dimensional arrays.  Each time a function calls itself, the program uses up more ram, and in fact is a common way for hackers to get access to your computer due to the fact that if you continually call a recessive function, you may get a heap error, that is when your sandboxed memory reaches the top of the heap.

In order to avoid a heap error, all recursive functions must have a base case, or else it will go on forever, and force the OS to crash the program.  After the base case, there is usually the condition(s) for which the function calls itself.

Let's start by creating a basic factorial recursive function.  First we would need to decide the base case.  We know that 0! is equal to 1, so we can say that if 'n' – n being the parameter of the function – is equal to 0, then the function shall return 1, otherwise we want to return n*factorial(n-1).

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

Tracing through a few examples, factorial(0) goes straight to the base case, and returns 1.  Let's trace something slightly more difficult.
factorial(2) goes straight to the else, giving us 2*factorial(2-1), evaluating factorial(1) gives us 1*factorial(0), which we evaluate factorial(0), reaching the base case, which returns 1, then the previously called function returns 1*1, and eventually returning 2*1, giving us that factorial(2) equals to 2.

Week of Feb.02.2013

Last week seemed to have focused heavily on recursion and one class was based on specifically solving TOAH's problem with three stools, where as our assignment we must solve it with four stools.  Overall, most of the weekend was spent on completing the assignment, and some difficulties that occurred was understanding what to actually do on the assignment, due to the overwhelming amount of code that was given to us.  After a few hours on the first night, we were able to figure out what we were supposed to do, and completing the first two steps took about an hour.  On day two, we were able to complete step 5, and finalize the assignment.  Step 5 was the hardest due to the fact that tracing such a large program recursively was quite difficult.

Week of Jan.26.2013

This week we went over a little more recursion, and learned about inheritance in our class.  Luckily for me I am familiar with inheritance, but recursion was always a difficulty of mine to trace.  Recursion can be thought of as a piece wise function, where the base case is the case where the function stops calling itself, and begins to return the value from the previous function call until the function finally returns a final value.  One example can include a factorial function, where as the base case where if the input x is 0, the function returns 1, otherwise multiply the input with the function call input x-1.

Sudocode:

if x = 0 => 1
else => x*f(x-1)


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

     

Week of January.16.2013

Before we get started, I wanted to quickly brief about what Object Oriented Programming, otherwise known as OOP.  An object is made up of a class, which contains properties and methods that can be used to change change certain properties of that object, or actions that the object can do.  For instance, if I have a class that that simply creates a fraction of a numerator and denominator, I can simply make methods to calculate the improper fraction for that instance of the object, or the mixed fraction of the fraction.

I have been taking computer science courses since I was in grade 10, that being said I never started taking computer science seriously since grade 11, due to the fact that we were learning an obsolete language at the time (Turing).  Nonetheless, one of the most important things I have learned at my high school was Object Oriented Programming (Otherwise known as OOP).  It made programming 70% more efficient and creating programs significantly faster.  I never realized the power of OOP before I first started using it, and have since then had tremendous amount of experience programming with OOP using Java.  OOP with Python is not a huge difference from Java, has the same idea, with a few syntax differences.  Other then that, I would like to add that I was very fortunate that Computer Science was offered at my school, and I wouldn't be here today if I had no taken it there.  Cheers!