Week 11: sorting, recursion limits

Busy, busy, little bees

This week has been a painfully busy week for me; got a few assignments due by the end of this week and a couple final exams that I need to study for, so I'm going to try to keep this blog post short.

This week's lecture basically went over different sorting methods, and expanded a little further on the concepts we've talked about last class. We went over some more big-Oh notation stuff, then went on to talk about recursion limits. One of the things we looked at during lecture was the idea of using 'memoization' to improve the efficiency of a function. We specifically looked at the python implementation of the Fibonacci function, then improved its runtime through the use of memorization (the difference in speed was significant).

Tim-Sort 
Another topic we covered in class that I thought was interesting was the Tim-Sort. To my understanding, tim-sort is the standard sorting algorithm used in the Python standard library. It utilizes the fact that in most real-world data, lists tend to be already partially sorted. I do wish that the instructor had been a little bit more clear on exactly how tim-sort works; we only briefly went over tim-sort during lecture. I understand that its probably outside the domain of this course, but I think it would have been pretty cool to get a more in-depth rundown on tim-sort out of intellectual curiosity. My understanding on tim-sort is relatively limited, so I would really appreciate it if someone reading this post might be willing to enlighten me on how tim-sort works.

Until next time!

Week 10: sorting big-oh

To talk briefly about A2...

Assignment #2 was due during this week, so that had taken up a significant amount of my free time. I thought the assignment was a relatively straight forward project that wasn't extremely difficult, and I'm pretty sure most people thought it was an relatively easy assignment. Looking forward to get my marks back for this project. Guess all that's left at this point is just preparing for T2 test and the finals. How did everyone else feel about A2? Did you think it was a hard/easy project? Leave your thoughts on the comment section below (please)!

Moving on to this week in lecture...
In this week's lecture, we talked about the big-Oh notation of some popular sorting algorithms, specifically with references to quick sort and merge sort. Among the sorting algorithms that we have gone through in the past week, quick sort and merge sort are the only ones that have O(n log n) in average case, versus the poor performance of sorting methods such as bubble sort and selection sort which have O(n^2).

Sun Tzu said: Divide and Conquer!
Quick sort and merge sort are interesting because both utilize a divide and conquer strategy to achieve optimum efficiency. For those who have never heard of the term divide and conquer, in the case of programming, divide and conquer strategies break a problem down in smaller problems, such that the problem as a whole becomes easier to solve. For example, merge sort works by repeated dividing a list into small sub-lists until every sublist is of length 2 or smaller, at which point each sublist is then sorted and repeated merged together, until a sorted list is created (see image below).

Merge sort in action

Final thoughts for the day...
As usual, what are everyone else's thoughts on the different sorting algorithms seen in lecture and lab? Which one do you think is the best? Do YOU know of an even quicker way to sort a list? Please let me know in the comments section below!

In the meanwhile,
Cheers



Image Cite:
Merge Sort. Digital image. N.p., n.d. Web. 4 Apr. 2014. <http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/Gifs/mergeSort.gif>.

Week 9: BSTs and big-Oh

In this week's lecture, we went over the topic of binary search trees and the use of big-Oh notation in describing runtime behaviour of functions. The topic of binary search trees was relatively straight forward, and simply expanded some more on the concept of linked data structures that was done last week. The topic of big-Oh, however, was much more interesting, since big-Oh could could as a useful measure of algorithmic runtime efficiency.

Binary Search Trees
The explanation of how a binary tree works in lecture shared many similar similarities with the LLNode class done last week. Like the implementation of LList, the implementation of BST utilized both BTNode and a wrapper class. We then went over some simple tree traversal methods that was covered in an earlier lecture when binary trees were first introduced. I thought the section on deletion of a node in a BST was quite interesting, since it had never come across to me that the deletion of a node could be problematic, given that some nodes may contain two children. The basic concept of node deletion was relatively straightforward (see image below), but I do plan on reviewing the material some more to make sure I get the material into my head.

Binary search tree node deletion

Big-Oh Notation
The concept of big-Oh notation was in fact something that I was already quite familiar with, since we had covered the concept in CSC165 during a previous week. I actually wished we had talked about big-Oh a little bit more, since the instructor had only made brief mentions of it as the lecture progressed. Obviously, the concept of big-Oh itself was relatively simple: it provides an upper bound on the runtime as the input size gets increasingly large. Hopefully we could cover the concept at a more in depth level during next lecture.

To other CSC148H1 Students:
What do you guys think of the topics we've covered this week? I'm sort of curious about how others feel about big-Oh notation and binary search trees. I can imagine that some of this materials may be a little bit hard to digest, so it would interesting to see how others are faring with it all. Leave your comments below!


Image citation:
4.4 Binary Search Tree. Digital image. N.p., n.d. Web. 4 Apr. 2014. <http://lcm.csa.iisc.ernet.in/dsa/img168.gif>.
Big-Oh Design. Digital image. N.p., n.d. Web. 4 Apr. 2014. <http://i0.wp.com/www.stampede-design.com/blog/wp-content/uploads/2013/08/big-o11.png?resize=498%2C512>.

Week 8: linked structures

Brief Overview:

This week's lecture dived into the topic of linked data structures in programming. We first looked at the concept of a linked data structure represented as a linked list by analyzing the LLNode class and its associated wrapper class as provided in lecture. A handy diagram from the CS department at SFU provided below gives a visual representation of what a linked list looks like in the abstract.

We then moved on to the idea of a binary search tree, which was essentially a linked list, but with two children (see diagram provided below). The code implementation for both types of data structure was relatively simple. In the code provided during lecture, the implementation of a linked list and a binary search tree both used a wrapper class as a method of organization (BTNode and BST; LListNode and LinkedList).

"Flattened" binary tree?
I had noticed that a LLNode object was essentially a BTNode object, except for the small difference where LLNode has a single child whereas BTNode has two. In fact, had the instructors not explicitly stated the differences between the two through the use of descriptive names, it would have been very difficult to distinguish the differences between the two. This little observation made me realize the importance of having meaningful names when creating classes to represent linked data structures, since confusion can easily arise when we start naming attributes or methods in the LLNode class with names that are typically reserved for the BTNode class. At the same time, its interesting that from the perspective of the python interpreter (assuming that the interpreter was somehow sentient), how a LLNode or BTNode class functions is unrelated with respect to the names given to the various methods and attributes of that class; the names exist solely to infer meaning to the code for the person reading it. Its a simple observation, yet quite profound at the same time the more that I thought about it.

Final Thoughts
How is everybody else faring with the concept of linked structures? Do you think its difficult/easy? Confusing/clear? Leave your thoughts in the comment section below!

Image citation:
Recursive Definition of a Linked List:. Digital image. N.p., n.d. Web. 1 Apr. 2014. <http://www.cs.sfu.ca/~bbart/225-beta/ind5.png>.
Binary Search Tree. Digital image. N.p., n.d. Web. 1 Apr. 2014. <http://upload.wikimedia.org/wikipedia/commons/a/a9/Unbalanced_binary_tree.svg>.

Recursion

# Example of recursion in nature and physical systems (i.e. formation of frost crystals)

What is Recursion?
Recursion as a concept has been around in history before the invention of computers. Properties of recursion can easily be observed in nature as well as in physical systems. At this point in the course, I’m pretty confident that most, if not all, students in CSC148 are familiar with the concept of recursion. Everybody understands recursion a little bit differently, but the fundamentals are typically the same; when you create a recursive function, you start by defining you base cases that solves the problem when it’s “small”, then implement a solution that essentially breaks your problem into smaller chunks up until your base case is reached. Recursion as a programming method of solving problems has HUGE appeal in terms of functionality, and I would think that it is one of the fundamental concepts of computer programming.

# Recursion used in advertising of products

Recursion in application:
To illustrate how recursion is used in application, take for example the following function:

def count(lst):
    return sum([1 + count(x) if isinstance(x, list) else 1 for x in lst])

This function counts the number of elements in a list, including elements within nested lists. It does so by counting the number of non-list elements in lst, and calls itself on lists that are nested within lst. The base case in this example would be the else statement that tells the function to just return 1 if x is not a list, or in other words, a non-list element. A typical function that solves the same problem, without using recursion, could span from 8-25 lines, depending on how one implements the function. However, with the use of a combination of recursion and list comprehension, all that code is squeezed into a single line. Thus the use of recursion in this particular problem presents a cleaner, more concise view of how count() is implemented. As well, the use of recursion simplifies how the programmer approaches this particular problem, which can be taken to be true for any other problem that is of a recursive nature.

Be aware...
The use of recursion can be tricky at times; the possibility for infinite regress is always open if the base case is not defined clearly, such that recursion DOES not ever reach a base case, and instead loops in a continuous manner indefinitely. However, with a strong understanding of how recursion works (complemented with a little practice), the use of recursion in programming is extremely powerful for solving programming problems.