Pretty nice blog post on sorting and efficiency. Check it out!

CSC148 SLOG at UofT: Assignment Topic Three: Sorting and Efficiency (La...:         The run-times of algorithms in computer science are categorized using different function types (logarithmic, exponential, polynomial...

Week 12: constant-time access and review

Final Post for CSC148H1

It is with a small bit of both sadness and relief that I shall write this final SLOG post for CSC148. I have had a wonderful time in this course, and will look forward with eagerness to moving onto CSC207 this fall. Hopefully, I will see many fellow friends and classmates next semester.

This week's final lecture covered the concept of constant-time access, and reviewed some material covered in past lectures in preparation for the final exam. 

Constant-time access refers to the practice of storing references to elements in consecutive memory addresses such that if the index of a list is known, the element contained at that index could be accessed within constant time. The downside to Python list's constant-access feature is most evident when we start dealing with huge lists that requires descriptive names in order to have a meaningful way to access values associated with those specific memory addresses. 

Be aware...

It is worth noting that when we convert strings, or tuples into integers using hash, we have to be mindful of the potential for collision to occur (i.e. two of the same key refers to two different elements). It should also be noted that the number of bits that could be stored in memory is dependent on the size of the memory itself. Thus, it is not possible to store exponentially large number of bits in memory, which becomes a problem when we deal with very large lists that requires a large number of keys.

Studying for finals
Given that the final exercise for CSC148 is due tomorrow, it seems like at this point, all thats left in terms of course work is to finish up our SLOGS and prepare for finals. I managed to score a pretty good grade on the last term test, but I was quite honestly really surprised to find that the class average for our section was 45%. Hopefully during the CSC148 finals, we won't be dealing with such low averages. This leads to a sort of side question: how are other students in our section studying for the finals? Figured I'd leave this open question on the blog (though I HIGHLY doubt if anyone will be answering it here, I'd really appreciate it if you leave a comment below), and will probably post once more on Piazza. It seems like throughout this entire semester, most CSC148 students interacted with one another via Piazza rather then throughout the slogs. Amazingly, there is not a single comment on any of my posts, despite repeated requests for them. Seems like a lot of people are just not really into the whole idea of a SLOG. Just food for thought.

And finally...

Congratulations to all fellow CSC148 students for surviving the course! I'll be looking forward to seeing you all again next year! Good luck on the finals!

And to end with some humour...

Cheers,

Fellow CSC148 Winter 2014 Student

Image cite:

Final Exams! - News - Bubblews. Digital image. N.p., n.d. Web. 4 Apr. 2014. <http://www.bubblews.com/assets/images/news/1831247139_1362455100.png>

Searching and Sorting Efficiency

Search and sorting:
Searching and sorting are common functionalities often employed in programming. Whether it be looking for the largest integer value in a list, searching for a specific name in a dictionary, or sorting a list in alphabetical order, searching and sorting algorithms are used to find (or sort) the things that we are looking for.

Which searching (and sorting algorithm) should I use?
However, there exists a plethora of differing sorting algorithms, ranging from Bubble Sort, Quick Sort, Merge Sort, and etc., which then leads to another whole host of searching algorithms that work on unsorted lists, sorted lists, and almost-sorted lists. Given this wide ranging availability of different options of searching and sorting a given set of data, how do programmers approach the problem of determining precisely which sorting and searching algorithm to use? The answer: it depends on the context of the problem. However, a simple analysis using the big-Oh notation of a function can tells us important information to determine which searching or sorting algorithm to use within a given problem.

Binary search in action

Example of merge sort

What is big-Oh notation?
Big-Oh notation is commonly used in programming to determine the searching or sorting efficiency of a given algorithm. To be more precise, the big-Oh notation of a function gives us its upper bound on its runtime as the size of its input increases. Sorting algorithms such as bubble sort have a runtime of O(n^2). Merge sort, another sorting algorithm, have a runtime of O(n log n), but uses more memory. Binary search (see image above), which employs a divide and conquer strategy, has a runtime of O(log n). A pure binary search however, will only work on a sorted list. Below is a table that displays the runtime efficiency of various searching and sorting algorithms in big-Oh notation.

On a final note...
When using big-Oh notation, it is important to use meaningful notation in describing the asymptotic runtime behaviour of a function. For example, it is perfectly legitimate to say that merge sort has a runtime of O(n^2). However, this doesn't give us an accurate approximation of the runtime behaviour of merge sort since O(n log n) provides a much tighter bound than O(n^2).

Image Citation:
What Should I Do If My System Isn't Working Properly? Digital image. N.p., n.d. Web. <http://www.sdasecurity.com/wp-content/uploads/2013/04/security-system-error-advice.jpg>.
Electric Engineering and Computer Science. Digital image. N.p., n.d. Web. <http://engineering.vanderbilt.edu/images/dept-slide-show/eecs-slide-4.jpg>.
Binary Search. Digital image. N.p., n.d. Web. <http://en.algoritmy.net/image/id/40163>.

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.

Week 7: linked structures

Hello world...
So unfortunately, due to the fact that I was in the Wednesday evening class from 6-8:00 pm on Wed, I was unaware that there was in fact a lecture section on linked structures for this week’s class, given the scheduling of the first term test at the same time as lecture. Nevertheless, the concept of linked data structures (i.e. the “LinkedList” class used in lab) was pretty straightforward, and after reading the lecture slides and one of the readings on “LinkedList” that was posted on the website* (along with a few Google searches on the topic), I feel fairly comfortable with the idea and able to implement a linked data structure should that appear on an assignment or exercise.

LinkedList into Binary Tree?

Even though the lecture slides had clearly pointed out that the example of LinkedList used was a representation of a tree with arity = 1, I’m fairly confident that - with some slight modification to the LinkedList class - it can also be used to represent trees of arity n. The classes LinkedList and TreeList represent more or less the same idea, though how the two implement recursive structures are slightly different. Nevertheless, I found that applying the concepts (i.e. height, branching factor, internal nodes, leaves, etc.) I had learned when we were covering TreeList helped me with understanding LinkedList.

Reflections on the test and other thoughts....

Now, to talk briefly about the test we had: I thought it was fairly straightforward; nothing surprising. The test covered the basic concepts we had learned in class, and there was quite honestly nothing that was out of the ordinary. Yes, there were a couple hard questions on the test that took some time to think about, but in general, I feel fairly confident that I had done well on the test, and I think this was a similar sentiment shared by other students who had attended lectures and labs regularly. For those who didn’t attend lectures and labs, it is to my understanding that it was a “challenging test”, as I was told by one of my friends who didn’t show up for lectures regularly. The cheat sheet we were allowed to bring was sort of unnecessary, since I didn’t use it even once on the exam. However, I found that the time I spent reviewing previous topics in creating my cheat sheet was actually really helpful in preparing for the exam, and made my more prepared in general for the fundamental concepts of CSC148.

*Here’s the link to the article I was talking about. I personally thought it was immensely helpful for understanding LinkedList. 

• http://openbookproject.net/thinkcs/python/english3e/linked_lists.html#the-fundamental-ambiguity-theorem

Week 6: recursive data structures

In this week’s material, we ventured on to the topic of recursive structures with a focus on binary trees (aka the ‘TreeList” class). I thought this week’s lecture was particularly interesting, given that this was my first interaction with ADT with a recursive spin to it.

I found the idea of binary tree’s intuitive and appealing from a functional perspective. I have to admit, it took me a while to wrap my head around the concept, but once I did, I could immediately see the functional aspects of using recursive data structures over traditional methods of organization (i.e. for searching applications).

Binary Tree: a tree made of 0s and 1s?

To my understanding, binary trees are composed of ‘nodes’ and ‘leaves’, where nodes that have children are referred to as internal nodes, and nodes with no children referred to as leaves. The height of a tree is defined as the maximum path length from a root to a leaf. The arity of a tree refers the maximum number of children for any node, which in the case of a binary tree, is 2.

Final Thoughts and Reflections

On a side note, shortly after class, I had a brief discussion with a classmate (who’s been programming in C ++ since he was 13), who told me that when he first learned about recursive data structures, his instructor had used the example of pointers referring to memory address rather than nested lists to explain recursive data structures. This got me thinking some more about recursive ADTs, and made me realize that a binary tree could have just as easily been implemented using pointers pointed at unique memory addresses containing ‘child objects’ rather than using something like a “TreeList”.

Week 5: stools, names, tracing

In week 5 of CSC148, we started this week's material by talking about the concept of "recursive insight". The idea behind recursive insight is to develop an understanding of what our problem is, spot out any patterns, and then figure out how we can break down the problem into subproblems, such that we can develop an recursive solution to solve it.

The Recursive Way...

I found this method of problem solving to be a nice way of figuring out how to develop a recursive solution. In a typical CS fashion, the steps for developing a recursive insight is structured into an algorithm, such that, we as the programmer, can easily spot out when a recursive solution would come in handy when given a programming problem. There is one thing that I would of probably added to the lesson though, and that was the necessity of developing good base cases when creating a recursive function. I found that most of time, when I'm talking to classmates about the use of recursion in programming, many fail to realize how important base cases are in developing a recursive function. 

Tracing

We also covered the topic of tracing a little bit more since last class, which I won't talk about in great detail since I had already blogged about it in my last post. Nevertheless, it doesn't hurt to say that knowing how to trace a program, both mentally and on paper, is a necessary skill in becoming a good programmer. Sometimes its more important to understand how and why a function works than to be simply content with having a working function. This is important because there often come times as a developer when it may become necessary to modify a function to do something different to what the function was initially programmed for, as is often the case in the software development world.

Thoughts or comments for the day?
To fellow CSC148 students: what are your thoughts on recursion? We've definitely have talked about this concept for quite a few times now at this point. What are your thoughts on it? Does it make sense? Leave your comments below!

Also, please let me know if there's something you think I could do to improve this blog; would love to hear some feedback. Thanks.

Week 4: More recursion

I have been meaning to post an update for the materials covered in week 4, but due to numerous exams and assignments that, with my unfortunate luck, crammed all into the period of a single week, this post has been a few days overdue. With that said, time to move on to the topics of week 4!

In this week's CS lecture ("or technically, 'last' week), we went over the topic of recursion once more. Though I personally have a relatively strong grasp on the subject, (due primarily to the fact that I find recursion to be a very elegant way of solving problems, complemented by the fact that I find it to make sense intuitively-speaking) I thought it was nice that we covered some more ground on recursion. On a side note, I found that many of my classmates find the topic of recursion to be somewhat confusing, and that they would use simplifying statements such as "recursion is just a method that calls itself" to describe it, which although is correct, does not necessarily reflect the other facets that makes recursion an elegant solution to solving programming problems (i.e. the concept of breaking a problem down into sub-problems until a base-case solution is reached).

We also covered some ground on the basics of tracing a function, which I think is rather important (as many other programmers would probably agree) in understanding how one's function is supposed to behave and how it behaves in actuality. Before I begin coding any functions in my module, I always have a quick mental side note with myself to quickly run the function in my head to see how I expect my function to be implemented, which I would then compare to how it is actually implemented when I run the module by looking at the results. I find that by quickly mentally tracing the implementation of my function in my head, I become more aware of any potential errors in my code when my program (inevitably) runs into problems during my first trial run. By tracing the implementation of my function, I find myself more "synchronized" with my code, for the lack of a better word, and am able to better understand what my code is doing in my program.

While I'm on this topic, one thing I found to have been particularly useful in my programming endeavours is including a print() statement at the end of functions that I feel "uneasy" about to more clearly see what my program is doing. This little "technique" has been very useful for me when I'm fixing my code due to unexpected errors.

We also briefly went over nameless functions with lambda during lecture. I found the concept to make sense intuitively, and I can easily visualize its practical applications when programming (i.e. reducing time spent creating simple functions that are only used once, as well as reducing the lines of code in a module). However, I must admit that the syntax for creating lambda functions still troubles me in my sleep, as I am very much unfamiliar with the syntax used in creating lambda functions. One of my goals in the next couple weeks is to become more familiar with creating lambda functions, such that I can easily integrate such functions into my code without fear of unexpectedly running into problems due to simple SyntaxErrors. 

Object Oriented Programming

In Python, as in many other programming languages such as Java, C, and etc., object-oriented programming is a fundamental characteristic of the programming language. Objects are created by initiating an instance of an class, with a set of data known as attributes that consists of data types such as int, float, boolean, string, and etc. As well, object have a set of defined methods called functions that acts upon the attributes of an object. Functions can be used to modify, manipulate, or return the data of an object. The data of an object is typically created when a class is initiated. However, it should be noted that in Python, the data of an object can be set outside of its parameters such as in the console. There is not such thing as private/public variables as is the case in Java, though changing the attributes of an object outside of its parameters as defined in its class is in general considered bad coding practice. In Python, every abstract data type is an object.

Object-oritented programming utilizes a concept known as encapsulation, whereby the code of an object is "hidden" from other parts of the code, such that the modification of the code of one object does not interfere with the code of another object. By "partitioning" the code into separate sections, code organization is improved. Through this method of "information hiding", programmers need not fear that changing one section of their code can lead to unexpected changes in another section of their code.

To better understand object-oriented programming, we can look at some real world equivalents of an object. Take for example the vending machine. The vending machine has a set of internal mechanisms that allows it to dispense soft drinks. However, the user of a vending machine does not need to understand the inner mechanisms behind the vending machine in order to use it; the user simply needs to understand the interface of the object to operate the machine. The designer can tinker with the internals of the vending machine and implement a new design for it, but so long as the interface remains the same (or at least similar enough such that the user is still familiar with how to operate the machine), this will not pose a problem. As well, if the designer tinkers with the internals of a single instance of a vending machine, this will not lead to system-wide changes in all vending machines in the world. This same sort of logic applies with object-oriented programming. The implementation of an object can be hidden from the user; the user simply needs to know what the object does in order to use it. We can change the internals of a single object and not expect this to lead to changes in other objects that exists in our code.

For those that are still confused about how object-oriented programming works, I found that the entry on Wikipedia was quite useful to in better understanding the concept of object orientation. The reading is informative, relatively concise, descriptive and explained in a language that is simple to understand. Of course, the best way to understand object-oriented programming is to actually use it in practice, though having some background knowledge in the matter never hurts ones understanding.

Link: http://en.wikipedia.org/wiki/Object-oriented_programming#Overview

Please feel free to make any comments or suggest any changes to the entry below! I'm quite curious as to what sort of sentiments other people in CSC148 feel with regards to Object-Oriented Programming, as I myself find it to be a much more "pleasing" method of programming that appeals to my need for organization and code management. Let me know below in the comments! As well, a note for fellow classmates in CSC148: feel free to link my posts to your blog if you wish to do so (for whatever reasons). Cheers!

Week 3

In week 3...

We covered some basics of object oriented programming in Python with regards to raising exceptions and inheriting new classes. One of the ways we can inherit from a class is by extending a base class using the declaration:

class NewClass(OldClass):
...

Sometimes when writing functions, using a return type to communicate special cases or errors is not appropriate in all circumstances i.e. when your function returns numeric values, which leads to the problem of distinguishing between "error" values and normal "expected" values. This is when the use of exceptions comes in handy, because it allows us to clearly communicate what had gone wrong with our function/program through the use of methods such as raising a ValueError. We can even output our own customized messages when raising exceptions by inserting our own strings into the parentheses of either the preloaded exception methods that comes with Python or in ones that we define in our module through inheritance, thereby creating a even more detailed response to the problems experienced by the use of our function.

We also touched briefly on modifying the "__methods__" of our newly defined classes, such as mutating the "__repr__" object to represent your object as a string.

 I enjoyed some of the materials that touched on recursive programming, as I find it to be an interesting way of looking at problems that has elements of recursion. From an intuitive standpoint, recursion offers an elegant approach of simplifying a problem by reducing it to piece meals and allowing us ("the programmer") to solve each "section" of the problem individually until we arrive at a base case. In general, I look forward to implementing some recursive methods in our next CS assignment.

First Entry on SLOG:

This blog is created to keep a log of my participation in CSC148H1 Winter 2014 at UofT. I will update this blog on a weekly basis to record progress I've made in this course.