Week 10

For the last few lectures in computer science, we have been discussing sorting and efficiency. There are multiple types of sorting algorithms, each with their own efficiencies. Some are better to use in shorter lists, whereas some are better to use for longer ones. This also varies for how sorted the list is already.

Bubble sort is an algorithm, which shoves the largest item to the end of the list and continues to repeat for each item. Since it runs through the list first n-1 times, then n-2 etc... until the last comparison of the two elements, the algorithm makes about n*n comparisons as a worst case scenario.

Selection sort is similar to bubble sort. However instead of swapping positions of each comparison (if it must be swapped), it will only move the highest element to the top at the end of each pass (with each pass not including the already sorted section). The number of comparisons is still n*n however it is a more efficient algorithm due to only a maximum of n exchanges. This is good for elements that have sorted elements at the end due to less replacements.

Insertion sort is similar to selection sort, but instead of adding sorted items inversely to the end of the list, it is added in order to the start of the list. Again the efficiency is n*n, however this method is good for lists that are already sorted at the beginning.

Merge sort breaks each list into smaller parts and recursively sorts those parts, eventually merging the sorted smaller lists into a larger sorted list. This is one of the searches that uses recursion, calling itself on each smaller list, then splits that list and calls itself again until each list is size 1. Then each sublist merges into a sorted list and returns itself. This sorting does n comparisons but has logn calls so its a sorting efficiency of nlogn.

Quick sort is another recursive sort, that doesn't use the storage of merge sort. There is a point called the pivot point which is randomly selected (usually the first one). All items less than that point are put to the left and those higher than it are put to the right. Then on each sublist, the sort is called again, returning a sorted list. This ensures that the pivot point always ends up in the right slot of the list. Again this list has n calls with logn recursions so its an efficiency of nlogn.

A note about efficiency: people use big O notation to show the worst case efficiency of a program. For example, traversing a 2-d array with same width and length would be an efficiency of n*n (n items in a list, then n items per item in the outer list). This can be written as O(n*n).

CSC148 Week 7

As we approach we week 7, us programmers are having to familiarize ourselves with a tool called recursion. This a very powerful, but very confusing concept of  programming. Recursion is basically the ability for a function to call itself. Even though this seems simple, the applications of recursion are far from it. Recursion can be as simple as drawing a tree on the screen or as complex as solving the classic Towers of Hanoi problem. However, it is able to simplify many problems in computer science.

Personally one of my biggest flaws in recursion, is my ability to trace the code. I find it extremely difficult to understand what a block of recursive code is supposed to do. Even if I get the gist of the code, the exact result will often elude me. I have found drawing a flow chart useful in tracing the code, since I can visualize the branching aspect of the recursion. However when the number of recursive calls becomes large, this no longer works. Thankfully the recursion in this course has not been too deep and has been somewhat traceable by my abilities.

One of the greatest challenges involving recursion was Assignment 1. Not only did it have a core aspect of recursion in the main algorithm, but it also had many other components of programming that I am rusty on. Additionally, I am rather disorganized when it comes to large coding projects. I find it difficult to remain which class does what, and how they all intertwine. I spent about 2 hours reading the class descriptions before I could actually start the project. Then when it came to the actual recursion, I was confused on how to implement it into our group's classes.

Now that we are expected to understand recursion to a large degree, I think it will show up in more exercises and assignments. This will make the course more difficult, yet a lot more interesting (I was getting bored of exercises where we just make classes).

Week 5

Week 5 is the first week where I've had to step outside my comfort zone. The labs are starting to get difficult and the concepts in class are new and harder to grasp. Plus with the burden of Assignment 1 looming on me (and the multitude of tests teachers decide to assign during this week), week 5 was hectic. However there is upsides to this week. What we learned in class this week helped clarify confusion I would sometimes have about errors in my code. An example of this is when I learned about scopes. For example, I did not know that an object created inside a method could not be referenced in the main of the class. This will help me foresee possible logic errors before they occur.


The lab used interesting aspects of recursion. The construction of a GCD function was an application or recursion I never thought of before. Also I can use this function for help in my math problem sets! Also the frozen list will be useful for coding later on in the course (I tend to like my lists to be frozen after referencing them anyway). Thankfully the examples from last week in class helped understand these problems. However these are just more examples on how recursion is a powerful tool. It keeps creeping up in methods I never thought would need it.

The Assignment 1 is so far a daunting task. Last year, we had to do towers of Hanoi as a problem set in our computer science course, so I am familiar with the concept behind the recursion. However, this is a much more complicated version with lots more features implemented. The addition of an extra possible stool makes the problems so challenging to the point where no solutions can be predicted for the larger number of stools. However a close answer should be possible with our knowledge of coding.

Thankfully we have reading week coming up because this week will be a tough one. Not only is there the regular lab and lectures, but the first Assignment due date is coming up and will make the next few days stressful as I scramble to finish it. At least there is no exercise this week!

CSC WEEK 3

This week in class, we focused on the usage of object oriented programming in Python. Since Python is an object-oriented language, this was a very useful way of organizing our code. We used the example of a Stack class to emulate a stack of real life objects. Due to the forces of gravity, a stack is not able to have an item removed from the bottom of it, but only from the top. We incorporated these properties into our Stack class using our knowledge of computer science with new material of classes.

The concept of a class was introduced to us during the first few weeks. It seems a much more logical approach to modelling real life situations than implementing code without any structure. It also is practical if one wants to use a block of code repeatedly, since all you have to do is call the class instead of rewriting lines upon lines of code. I think the implementation of classes in this course will make our future coding easier.

My adjustment to the mentality of object oriented programming was not very difficult. In previous years, I had covered the concept of classes using Java, another object oriented language. This allows me to think in an object oriented manner more easily than a beginner. My most difficult challenge was learning the Python syntax for class manipulation (as well as some more basic syntax). Since I omitted CSC108 from my courses, I had to try and remember my Python from my grade 10 programming class. Furthermore, with the update of Python 3, some syntax has been changed. I have tried numerous times(and I'm sure I will try again) to use the print function without brackets, each time leading to frustration (my tutorial partner can attest to this). Despite this, I think I should be fully accustomed to Python within the next two weeks.

One of the most interesting things about Python this week was the usage of the underscore in variable names. In Java, it was possible to create access modifiers for variables, omitting others from modifying certain variables. However in Python, the underscore is used to signify privacy. It is assumed that the user of the code would have the courtesy to not modify your variables. Another interesting part of Python is the absence of overloading methods. Python does not need to overload methods since the parameters may be of any type (yet you can still use type contracts to denote the type of a parameter). If a parameter is allowed to be omitted, it is declared as a None type in the definition. Another thing I still have to get used to is the concept of self, and having to incorporate it into the parameters. This gave me many errors during the first exercise.

For the first three weeks of CSC148, I feel that I have readjusted to the mentality of a programmer, despite my one year absence from coding. As the course continues to increase in difficulty, I hope I will be able to adjust.

Note to teacher: I am terribly sorry for the late submission of Week 3. I was unaware I had submitted it under the "Pages" category as opposed to the "Posts" one.

Week 4

4th week in CSC148:

If anytthing the fourth week of 148 has been much like third. The concepts are still fairly easy to grasp and the exercises are still doable without too much thinking. This week we started our first recursion lesson. This was quite an interesting lesson (not just because the pretty pictures we made in class). Recursion proved to be a powerful tool in coding, allowing us to approach multi-layered problems with only a few lines of code.

Basically, recursion is the ability for code to call upon itself. This is useful if we want to have any branching behaviour, such as in fractals. However, it can be use for many more purposes. The example we did in class (aside from the colourful turtles), was finding the maximum of a nested list. We recursively called the function if the item we were inspecting was also a list, returning the maximum of the list each time. This allowed us to efficiently find the maximum.

In terms of the problem set for this week, I found it both challenging and amusing. The challenging part was grasping the concept of exceptions. In Java, we had touched on exceptions, but never in as much detail as we did in class. Wrapping my head around the multiple possibilities of exceptions took some time but I managed to finish the set within an hour. It is cool how you write a class for an exception. It makes it like an exception is its own class. The amusing part of the assignment was to implement the ValueError. The best way (or at least I could find), to satisfy this condition was to actually use a logic error in my code! I never thought in University of Toronto computer science I would ever be asked to purposefully hand in an error!

All in all, I think this week in CSC148 was an interesting week. I can only guess on how we will ramp up the difficulty from here!