Sorting Algorithm and their Efficiency

    This week’s final (?) slog is about Sorting Algorithms and their efficiency, which is like a combination of the things I learnt in CSC108 (Sorting Algorithms) and CSC165 (their Efficiency or time complexity). 


    Sorting is the process of analyzing and then organizing a collection of data (for example, lists) in a particular order. There are many different types of sorting algorithms, and they are bubble sort, insertion sort, merge sort, quick sort, selection sort and Python’s built-in sort, ‘Timsort’, which is a combination of merge sort and insertion sort. I will now briefly talk about each algorithm.

    Bubble sort, basically, runs through each element in the input and switches the element if it is ‘out of order’. Obviously, it is not a good idea to use bubble sort on large inputs. Insertion sort partitions the input into 2 regions (sorted and unsorted); it checks each element in the unsorted region and inserts it into the correct position in the sorted region. The algorithm for insertion sort has two nested loops – one for the unsorted region and the other inner loop for the sorted region in finding the position where the element should be ‘placed’. Additionally, there’s selection sort, which goes through each element and swaps the element with the smallest element in the input array or list. Similarly, there are two loops for selection sort: a for loop for each element in the input and another for finding the smallest element in the rest of the input list. Thus, these algorithms have runtime of O(n^2).

    Next, we have merge sort, which splits the input data or list into 2 equal halves and continuously splits each half until a single element is in either half, which then sorts the ‘halved’ sections and finally merge the two halves until the entire list is formed. Clearly, this algorithm calls itself recursively. Similarly, quick sort also recursively splits the input data into 2 (possibly, unequal) halves about a ‘pivot’ element in the list, where the half to the left of the pivot contains the elements that are less than the pivot element, while the other half (to the right) contain the elements larger than the pivot.

    In CSC165, we used upper, lower and tight bounds to describe the time complexity and efficiency of various algorithms. The ‘in-depth’ analysis of algorithms taught in CSC165 has helped me in analyzing the time complexity for CSC148. We use the upper bound of runtimes, using the Big-Oh notation, which eliminates constant factors, to give us a measure of an algorithm’s efficiency. Worst case runtimes are, just as the name says, the most (or worst) time an algorithm will take to perform. Anyway, in the lectures and lab sessions, we analyzed the efficiency of various sorting algorithms. We found that merge sort and quick sort both had O(n log n) runtimes, which uses the ‘divide-and-conquer’ technique, whereas bubble, insertion and selection sort all had O(n^2) worst-case runtime, which is worse than the logarithmic runtime. Thus, merge sort and quick sort were found to be more efficient compared to the latter 3 sorting algorithms. On the side note, a runtime of O(1), simply means that the runtime is independent of the size of input, and O(n) means that the runtime grows linearly with the input size. The order of runtimes from best to worst is as follows:  O(1) < O(log n) < O(n) < O(n log(n)) < O(n^2)

    I found that algorithms with logarithmic runtimes were the most difficult to understand because at first, I didn’t get how one can tell if something is logarithmic, and in addition to that, I found it really complicated to analyze the ‘divide and conquer’ methods; not that it is difficult, it is just a bit too complex for me to keep track of, due to the recursive division of the input’s data. Because of this, I didn’t quite get the last two questions of the CSC148 mid-term Test 2, which was about algorithm’s time complexity. Therefore, I hope to spend more time practicing my algorithm analysis for both CSC148 and CSC165 before the final exam! Well, I hope this post helped by giving a quick and brief explanation of sorting algorithms and their efficiency (sorry for its length) and farewell!! J

Week 7: Recursion

     Hi, again! It is week 7, and my main task this week is to discuss about Recursion, which is a technique for solving a programming problem. Firstly, recursions usually require the function to call itself multiple times. From my understanding, recursions require the user to analyze the task by breaking it down into smaller problems until you find a ‘base case’, which helps solve the problem.  In my opinion, recursions can be very tricky and it really requires a lot of thinking in order to get the coding right. However, it is very useful in the sense that it makes the code (or solution) look simple and refined.

    After practicing recursions, I found that all recursions must have a base case, which, personally, is the most important, yet difficult in writing a recursive function. However, once you have figured out the base case of the problem, recursion becomes real easy because a recursive function is basically a function that calls itself. I found a great website that contains a brief explanation, as well as some examples of recursions. This website (http://www.openbookproject.net/thinkcs/python/english2e/ch11.html), along with the other posted readings from the course website, helped me fully understand the concept behind writing recursive functions. However, I plan to continue practice in writing recursive functions (although recursions should be avoided when programming) so that I would not forget how a recursions works.

CSC148 Week #7

   Reading week is over and Assignment 2 is up with the deadline fast approaching!!! I haven’t posted anything on week 6 because I was busy with studying for my other midterms, along with fixing some ‘last-minute’ errors in my Assignment 1. On the other hand, reading week was a great relaxer for me although it was too short! I am disappointed in myself because I planned how I would spend my reading week productively, but in the end, I did not do ANY work, when I should have started working on my Assignment 2. Additionally, the first CSC148 midterm occurred this week Wednesday (February 26, 2014). I must say the exam was quite easy although I did make a few mistakes in one/two of the questions, which I hope doesn’t cost me a lot of marks. Anyways, in the end of last week and this week’s lecture we examined a new concept of recursion in Python…that is Trees.

   A Tree is a class – it has its own parameters and methods or functions. A Tree is used to store data in Python, and its structure is like real tree that is linked by nodes, which can have zero or more ‘children’ and at most one ‘parent’. Some terms to be familiar with when dealing with Trees in Python are root, leaves, internal nodes, subtree and forest. More than one trees in Python is called a FOREST (LOL), and a subtree is a portion of a Tree structure. Internal nodes are just as the name says…nodes that are ‘inside’ a tree, and has children, so they are not leaves or a root. Leaves are the nodes at the bottom level of a Tree, while a root is the node at the top of a Tree (which is the opposite of a real tree). Having these terms/names helps me remember its features by relating it to a real tree.

   I have noticed that recursion plays a major role in Trees. Trees have some main functions like height, which is the maximum or longest path from some node to a leaf, and depth, which is the length of the path of a node to its root. Also, the main method used to analyze a Tree is called traversal, which comprises of preorder, inorder & postorder. For more information on each traversal method, see the link below, which someone brilliantly shared on Piazza (the course ‘forum’ website). 

   http://www.youtube.com/watch?v=83qfcisjol4&feature=youtu.be

CSC148H1S Week #5

One of the randomly chosen slogs that I have chosen to read this week was http://runningcomment-ary.blogspot.ca/. I must say that I can COMPLETELY relate with this person, though I am not as busy as this person! However, I am similar in the sense that I am taking six courses this semester, and I don’t know if it’s just me, but I feel like I have tons of work to do especially during these 2 weeks….Assignments & Mid-terms (though, it is not unbearable…it just seems like I have no time for a social life!!!).

Unfortunately I was unable to attend this week’s lab because I had my MAT137 Test during the lab session. On the other hand, I have read through the lab#4 handout, and I was able to understand the given codes by tracing them. Though, I am a bit puzzled about the last section of the lab (“Freezing copies lists”). However, I will attempt to go through that section of the lab during my free time.

The first lecture of this week (week#5) was mainly about understanding the recursion code for the Towers of Hanoi (our assignment -_-“). I felt like this class was supposed to give us a hint for Assignment 1, like we’re supposed to implement this code in one of methods for the assignment, but I still do not know where exactly! This week, my group managed to find a third member because we realized that we still had tons left to do for the coming week (on the side note, we’ve only just finished step 3 of the assignment…yay!!). Well, my main goal for week#6 of this semester is to be able to complete my studying for ALL my exams this week AND (successfully) complete all my assignments (especially CSC148H).

Slog #2...Recursions!

      It’s the fourth week of the winter semester; one month has gone by! This week started off a bit stressful for me, since I had an Economics test on Monday (I’m praying for a good grade!!), and Calculus problems set due on the same day. In addition to those work, Assignment 1 for CSC148 was posted online….how great!! I read the handout and the contents seemed very foreign to me, especially TOAH model. I can predict that the next 2 weeks are going to be extremely hectic for me because of CSC148’s Assignment 1 and mid-term tests for my other courses. I am really worried about the Assignment because I had just started it with my partner and we were totally confused and clueless of what to do. I’m praying that we will be able to finish Step 2 (at least!) before the end of next week!!

      Anyways, back to CSC148….this week’s lectures were mainly about RECURSION, which was something new to me. Thus, I had some difficulty understanding how recursion works. However, my main goal for the next week is to actually go through recursion one step at a time, until I feel comfortable writing it on my own, especially for Assignment 1. By the way, Thursday’s lecture was a bit interesting….TURTLES!!

   This week’s lab wasn’t too bad. The lab helped me reviewed unittesting, as well as class structure. Thanks to the lab, I felt a bit more confident on writing class and their structure. I was able to learn many new things or techniques in the lab, as well! One of them being the way we can test the Exceptions in unittest (i.e. AssertRaises). Another thing I learnt was inheritance (i.e. “super().”). This was my first time actually writing code that ‘inherits’ some attribute from the (parent) class, and by doing so, we were able to slightly alter the class or subclass. Also, I am grateful for my lab partner, who explained to me how it works. In my opinion, this week’s lab was quite enjoyable, as I was able to walk out the lab room learning and actually understanding the content.

   Well, there goes my week! Hope it’s better next week! J

CSC148H1S Week 3

    Time sure flies! The first three weeks of this semester have gone by so quickly! In the first week, I felt completely lost in the lectures, however, as I discovered the great help offered in this course, along with the weekly extra reading material, I hope to grow more confidence in programming, as well as understand ~95% of the material covered each week (or else, I'll have a ton of work to do before exams!). There were several foreign terms introduced in the lectures, which include ternary, ADT, Stacks and Recursion. My understanding of these terms was achieved by doing some extra reading, and taking some time to understand the code. Also, something that was mentioned by the professor and was new to me was the way in which one can make some data “private” by adding an underscore (‘_’) before the name. I really enjoy when my professor relates each ‘topic’ to some real-world situation, and this helps me understand what exactly is being done in Python. He usually includes in his slides, a paragraph relating the Python material to the real world. For example, in introducing Stacks, he summarized the methods that can be done with Stacks to real situations, and allowed us some time to read and analyze the paragraph. This really helped me interpret what is being taught.

    In addition to the lectures, there are also lab tutorials. At first, I disliked the idea of having to work with a partner in all the labs, since I comfortably worked alone for most of my CSC108 assignments. However, after attending my second lab session, I realized how important and helpful it is to work with a partner, especially in Computer Science. Thanks to my brilliant lab partner, we were able to finish the majority of the tasks provided, and he helped me understand how a ‘Stack’ works.

    The first two-three weeks of Intro to Computer Science were mainly about OOP. What on earth is OOP?? OOP stands for Object-Oriented Programming, which basically, is creating and using “classes” and “objects”. From my understanding, a “class” is a ‘blueprint’ that is defined by an individual (python-user) to represent a type of object and its operations, and an object is a ‘thing’ created from class, which tells it to do something. In programming, objects are usually called “instances” of a class. So, OOP is a type of programming that creates a sort of framework (a "class") for some data, which includes the functions or methods in which the data can perform. Some important traits of OOP include reusability (Inheritance) and “data hiding”. Data hiding is making some data “private” so that no user can interfere or access the data. Simply adding an underscore before the variable name does this "data-hiding". Additionally, “Inheritance” essentially means that one can “transfer” some features of an existing class and apply it to some new class, which can be extremely useful and time-saving when dealing with complex object-oriented programs. All of these outline a few of the many features of OOP.