Sorting and Efficiency

This SLOG entry is about sorting and efficiency.
The first time I encountered the topic of efficiency was in last semester's CSC165. We were taught how to read a piece of code and write a proof for its big Oh, big theta, and big omega.
The first time I encoutered sorting was in CSC108, where we learnt about bubble sort, selection sort, and insertion sort.

In CSC148, we looked at the following types of sorting.
First was select sort, where the minimum value of the remainder of the list is constantly found and switched with the item at index i, which is the starting index of what we define as the remainder. Then we define the remainder to start at index i + 1, until we reach the end of the list. This way the worst case is when the minimum value is always at the end of the remainder list, where for a list of length n, to find the minimum value we will have to search through n items, the n - 1 items, then n - 2 items. Added together, selection sort will have a big oh of n (O(n))
Then we looked at quick sort, which is a recursive function that takes an index i, and calls quick sort on a list of values smaller than the one at index i, and calls quick sort on a list of values bigger or equal (excluding L[i]) to the one at index i, then puts the two lists and value L[i] together in order. The big oh will be O(n) since to find the values smaller or larger to value L[i], the whole list of n values will have to be searched through.
Then we looked at merge sort, which also calls on function merge. Function merge takes two sorted lists and adds items into a new list in order. Merge is O(n), where n is the bigger length of L1 and L2. Therefore merge sort's worst case runtime is n/2 + n/2, which is still n.
Although for all of the above, the big Oh is n. This doesn't tell everything about efficiency. By testing on a list of 10000 objects, selection sort took the most time.

Recursion (once more)

Before we were told that this week's slog topic is recursion, I wrote about recursion in a previous slog entry.

This is the URL to the previous entry:
http://ehslog.blogspot.ca/2014/01/first-taste-of-recursion.html
Today's entry will be based on the last entry because I don't want to repeat too many of the same things.

As previously mentioned, I find recursion new and interesting. My understanding of recursion, method wise, is calling a function within the function itself. Purpose wise, is to cut the problem down into smaller problems that are easier to solve.

I remember an analogy that I came across during the period when I still couldn't grasp the concept of recursion. The analogy was about a stack of chairs. If you had 99 chairs to move, you will first consider moving the top 98 chairs, then consider moving the top 97 chairs, and so on, until there is only one chair to move, which makes it much feasible than moving 99 chairs at once.
This analogy outlines my understanding of recursion.

I think recursion is useful when a problem can be narrowed down into smaller pieces. Also in situations such as nested lists, we saw in class how recursion makes it easier.

Trees

This week in class we were introduced to the abstract data type Tree.
Most methods of the class Tree used recursion, which again reminded me of the importance of recursion in programming.

Assignment 1: Tours of Anne Hoy

This week's focus was on Assignment 1.
For assignment 1, I grouped with 2 other people and formed a group of 3. This was the first time that I grouped with other students for an assignment, so I wasn't really clear on how to work as a group.
To me it was either writing our own code separately and combining ideas at the end, or discussing and writing the code together. We tried the second method first and ended up chatting for the few hours with 0 progresses on the assignment.
So then we went home and wrote our own pieces of the code.
However when it got to writing tour.py, I got stuck on how to find i and how to write the recursive function. So then our group met again and I finally found the value in group work.
Sometimes there are problems that one cannot solve on their own. And this is the time where discussion and group work becomes valuable.

First Taste of Recursion

This week in class we looked at recursion over nested lists and recursion for permutations. To me, recursion is completely new and never thought of. The concept of calling a function within the function itself was at first very confusing. However I was able to understand it through tracing the steps one by one, though it took a bit of time.

Not only was recursion new and confusing to me, list comprehensions were also troubling, especially when it is used in combined with recursion. My approach to understanding list comprehensions is through rewriting them into the longer form which I am used to from CSC108. This way takes quite a bit of time and defies the purpose of list comprehensions, so I hope that I can learn to understand list comprehension itself through repeating this approach many times.

Another new thing we learnt was the nameless function lambda. Lambda is a function without a name that is called only once. However most functions of lambda can be accomplished by list comprehensions.

One thing I did not understand from this week was the permutation example given on the CSC148 course website.
The function was:

def perm(s: str) -> {str, ...}:
    return (set(sum([[s[i] + p for p in perm(s[:i] + s[i + 1:])]
                for i in range(len(s))], []))
            if len(s) > 1 else {s})

The main thing I did not understand was the use of sum in the function. Isn't sum only for numbers?

SLOG 1 (Object-Oriented Programming?)

These first weeks of CSC148 has been weeks of adjusting, understanding and growth. Both lectures and labs required adjusting to a new learning style compared to CSC108 in the previous semester. This is by learning and understanding new knowledge and concepts, and to change an grow to fit the teaching style of CSC148.

The first difference from before was object-oriented programming. In CSC108, I was used to programming by writing function by function by function. However in lectures of CSC148, programming is based around classes, whcih was new and interesting for me. Compared to just a list of functions, classes seemed more organized, catagorised, and structured.

The second difference was labs.In CSC108, labs were optional and we just had to complete lab exercises online. In CSC148, we now have to attend labs and complete exercises with a lab partner. This was hard for me, because programming with someone else was a lot different from programming alone. When being the navigator, I often felt the urge of getting hold of the keyboard and typing myself. Also I was aware that if I think and work at a pace faster than my partner, she might not be able to think through it herself. As according to my friend in another tutorial section, she doesn't learn a lot from the tutorials because her partner always solves the problem before she can fully think through it. So I stopped myself from over contributing. However because of this, the progress of completing the exercises in lab01 was a lot slower than it should have been, and was not fully completed. So in lab02 I didn't restrict myself from contributing and the exercise was completed within an hour, although I still don't know if this is good or not. However I have still learn't a lot by taking lab01 home and correcting and debugging it. Through debugging lab01, I learnt some thing new. Which was that dictionaries cannot change size during iterations. Which I did not know before.

Another interesting thing that happened this week was learning the ADTs stacks and queues in lab02. In particular, analysing the runtime of stacks and queues of different sizes. It resulted in that the runtime of stacks don't really grow with the size of the stack. However queues grow lineraly with the size of the queue. At first the concepts were abstract and hard to understand, but then I pictured a stack of paper versus a line-up at Starbucks. When adding paper and removing paper from the stack, the stack remains still and unmoved. However the line-up at Starbucks is constantly moving as people enter and leave the line. This gave me an understanding of the queue runtimes. Afterwards, when we were asked to think of more efficient ways of implementing queues, I tried thinking of how I could have a line-up at Starbucks so that the people in line doesn't have to move. Then I realized the only way is to have the cashier moving. But if the cashier keeps moving on, the counter will have to be infinetely long. Then the TA introduced us a new concept of a circular queue, which then I pictured Starbucks counter being a circle with a cashier that moved around inside the circle. Then the people will not need to move. But this is not efficient in the real world, because the cashier will be very tired, and its not that big a deal to move along with a queue. From this it could be seen that not all aspects of programming can be made into an analogy in real life.