Week 11 – Sorting and Efficiency

Okay so…first of all I would like to take a moment to acknowledge the fact that this is my last Slog post for this year *cry*.

It’s been a pretty good semester and I definitely had fun in CSC148, and most of all, I learnt more about the wonderful world of Python Programming!

So in this post I will be finishing things off by explaining Sorting and Efficiency!

What’s sorting?

Most of you probably know what sorting is in general terms. You take a list like this: [1, 3, 5, 6, 2] and if you sorted it so that it was in ascending order, you’d want this list to be returned: [1, 2, 3, 5, 6]. However, there are many ways to actually code an algorithm that can actually sort a list. Here are the main ones we focused on this semester:

Bubble sort

Merge Sort

Quick Sort

Built-in sort

Most of the descriptions for these sorts can be found here and in my previous blog post.

What’s efficiency?

So with all these different sorts, how do we know which one is the best? We find this out by counting how many steps each different type of sort takes sort a list of length n. In other terms, we’re calculating its runtime. Since I took CSC165 last year, calculating runtime wasn’t a new concept to me, and I was pretty familiar with it. When counting the number of steps an algorithm takes to sort a list, you usually count how many comparisons are made. Normally, this is also done with the worst-case possible, since it gives an upper bound to the run-time (in other words, the maximum possible runtime). We write this by using Big-O notation. Here’s a graph showing Big-O runtime of different functions:

For example, if we had a list which was in descending (worst case) order, and we wanted to sort it into ascending order using bubble sort, this would give us a runtime of O(n^2). This means that the maximum possible runtime would be a factor of n^2. And as expected, if you have a longer list, more comparisons would be made, which would mean the runtime also increases.  Another example is merge sort, which, as I stated in my last post, has a runtime of O(nlogn) since you keep splitting the list in half.

So if an algorithm has a faster runtime, then it’s more efficient, which makes it a lot better, and obviously, as programmers, we want efficient algorithms which will solve problems for us quickly!

That’s all for now! Good luck on the final everyone!

Week 10 - Sorting

Well this was a pretty hectic week! Let’s start off with what happened in lectures.

A lot of lecture time was spent going over Assignment 2 and a few tips on how to get certain functions working. I found this really helpful since it gave me a better idea on how to code regex buil_regex for example. It also helped with understanding what our base cases should be, which was pretty important since most of our functions were recursive.

After a lot of thinking, coding, improving (and repeating this cycle) we finally got A2 Part 2 done. It was definitely a pretty interesting assignment, and challenging, but we got it done! The main function we had trouble with was is_regex() since there were so many different cases we needed to keep in mind. build_regex also caused a few problems, thankfully, my partner and I managed to figure out a way to get it working!

But this week’s lecture was pretty interesting! We mainly went over different sorting functions, are two main focuses being quick sort and merge sort, and the difference in their runtime. When we learnt about merge sort, I understood it pretty quickly, since it basically involved splitting the list in half and sorting those lists, by splitting them in half again (RECURSION ALERT). This picture basically describes how it works:

Since this function is splitting the list in half multiple times, this gives it a runtime of O(nlogn).

Then there’s Quick Sort.

At first, it took me a while to understand the whole concept of the pivot and how it worked. However, this picture explained quick sort pretty well:

In short, this function picks a random pivot and sorts the list on either side of it. I thought that Anish (http://www.anishslog.blogspot.ca/) explained it pretty well, and his post helped me understand why the runtime of this sort was O(nlogn), which is since the pivot is chosen logn times and there are n items in thse list.

Lab 9

I found this week’s lab quite easy, since it was on binary tree and it was very similar to our exercise. For the first part, we had to code a function that would find the inorder traversal of a binary tree using LinkedLists. After a bit of drawing out how our function should work, and of course recursion, we managed to get the function working. The second part was to create a function that produced a LinkedList version of the longest path in the binary tree. This was almost identical to Exercise 3 where we had to make a function sum_to_deepest, so my partner and I made a function similar to that and then instead of adding the values, we just made sure they were printed.

That’s all for this week! Good luck on Term test 2 everyone!

Week 9

Week 9 – Binary trees

So this week was Binary tree week!

These trees aren’t too different from regular trees, the only differences is that each node has two children, hence the name binary. Another fun fact, the child on the left of each node is always smaller than the root node, and the child on right is always bigger. In a way, this makes them simpler to use and search through than regular trees. This picture is a pretty good representation of a binary tree:

And that’s another thing we did this week! We worked on how we would search through binary trees to find, insert or delete values. Since Binary trees are more structured, all we need to do is compare our value to the root’s value, and if it’s larger, then we go to the right, otherwise we go left, but if it’s the same then we know to stop. By using recursion to search through the tree, and by using this form of Binary search, we actually don’t need to go through almost half the list, and this makes our program much more efficient since it cuts down the runtime as well, to about O(lg n) where n is the size of the sorted list.

We also reviewed the other sort methods seen in 108, such as Selection sort and Insertion sort, and compared their runtime. Thanks to CSC165, calculating runtime and Big O wasn’t a new concept to me and I’m actually quite familiar with it, which made this week’s material easier to understand.

 

Lab 8

I found this week’s lab was pretty interesting. We basically just got a bit of practice working through binary trees and binary tree node functions. My partner and I had to write the recursive function count_less to count how many nodes had values less than the given argument. However, we had to implement it in different ways for example, either by adding a nested helper function or a helper method. I found it pretty confusing at first since I’m not used to writing nested helper functions and working with Binary trees, however, after getting through step-one, the rest of the steps were pretty similar and didn’t take much work. And of course, recursion practice is always good!

Week 8

Lecture

Hi everyone!

So this week’s lectures were based on learning about the Linked List class. This class is pretty similar to a nested list, except the LinkedLists have a first parameter as an item, and the second as a LinkedList. Here is an example of the class LinkedList:

class LinkedList:

    """Linked list class"""

    def __init__(self: 'LinkedList', item: object=None,

                 rest: 'LinkedList'=None) -> None:

        """Create a new LinkedList

        item - The first element of the linked list,

        Not present if self will be the empty linked list.

        rest - The linked list that contains the elements after item.

        Not present if self will be the empty linked list."""

        self.empty = (item is None) and (rest is None)

        if not self.empty:

            self.item = item

            if rest is None:

                self.rest = LinkedList()

            else:

                self.rest = rest

As the description says, the first item in the LinkedList is either a value, or it’s empty, and “rest” is either a LinkedList or empty. Some methods that we’ve created for the class LinkedList include:

Prepend (Put an item at the front of the list, and move the previous first item into “rest”)

__repr__(Returns a string representation of LinkedList)

Decapitate (Delete the first item in the LinkedList)

This week we learnt how to implement some of these methods in the LinkedList class, for example:

def prepend(self: 'LinkedList', head: object) -> None:

old_head = copy(self)

self.rest = old_head

self.head = head

self.empty = False

We also learnt how to implement other methods, such as insertion and deletion, basically how to add and remove values from the LinkedList. Luckily, I found it pretty easy to understand since it’s similar to how nested lists work, and the recursive functions we’d have to write would be similar to nested list functions.

Lab 7

In this week’s lab, we had to implement a few methods into the LinkedList class such as:

__len__

__setitem__

__delitem__

insert

After last week’s lab where we had to write our old class Queue and it’s methods by using LinkedList methods, this week’s lab seemed a lot easier since I now had a better understanding of LinkedList and how it’s methods worked. Although we had to use a lot of recursion to implement these methods, my partner and I ended up completing this lab without too much difficulty.

Assignment 2 Part 1

And finally the Assignment update! The link for Assignment 2 is here. At first, when my partner and I started reading the assignment, it seemed a bit complicated, especially since trees were a new concept to us. We were confused about why we’d need multiple classes represent the trees, however, after a bit more reading and coding, we found it actually made things a lot easier if we made classes for each different type of regex, and using a Regex superclass which we could inherit __init__ and __eq__method, and then simply write out the __repr__ method for each class (since each one would start differently, inheritance wouldn’t be effective here).

That’s pretty much it for this week!

Week 7 - Recursion

Hey guys!

So this week’s assigned topic is Recursion! I still haven’t perfected actually writing code recursively, but I’m going to do my best to give a general overview on what it is and how it works.

What is Recursion?

So recursion is writing a function in terms of itself. In other words, it’s like the inception of code, you’re writing a function that can call itself. This picture basically sums it up:

So the reason people use recursion is because it’s easier to solve problems by writing recursive functions. It allows you to use a function to solve the big picture, and then call the same function to solve smaller sub problems.

How does recursion work?

Recursive functions are similar to if/else statement. For example:

def r_sum(nested_num_list):

                tot = 0

                for element in nested_num_list:

                                if type(element) == type([]):

                                                tot += r_sum(element)

                                else:

                                                tot += element

                return tot

The key part of this recursive function, or any recursive function for that matter, is the base case, which is highlighted. This is the part of the function where it doesn’t actually call itself. Without the base case, the function would go into an infinite loop (infinite recursion) and you’d never get an answer, which isn’t what we want.

If we entered sum([2, [3, 4] 5]) into the python shell, this is what would happen: 

1. Since the first element is an int, not a list, it will go straight to the base case (else) and 2 will become the new total
2. Since 3 is in a separate list, the function would go to the “if” and call the function again, so that the contents of the list can be added.
3.  Since the function is called again, a new total would be created and 3 and 4 would be added to make.This total is then added to the original total to make 9, and the function continues to the last number which is 5.
4. The output of this would be 14.

When is recursion used?

Recursion is used a lot when creating functions and methods for trees, since they are all so similar. It makes it easier to write tree functions recursively to search through nodes and leaves in a tree to find a particular value or to check if all numbers are the same type. Basically recursion is used a lot to traverse trees.

For example, one recursive tree function is:

def total(tree):

                if tree is None: return 0

                return total(tree.left) + total(tree.right) + total.cargo

This recursive function finds the total value of the cargo of the given tree, and all its children.

How have I found learning about recursion?

Well since this was a completely new concept, I found it confusing at first and pretty hard to understand. I still haven’t mastered it but I’ve definitely got a better understanding of it and can write my own recursive functions more easily. I found that once you understood what you needed as your base case, it was a lot easier to write functions recursively, since you’re just putting in place where you want your function to loop! It was definitely an interesting learning process and I now find recursion pretty useful, especially when you want to solve a big problem that has smaller and similar sub-problems.

Mini Glossary

Recursion: Writing a function in terms of itself.

Recursive call:  When you call a function in its definition.

Base case: The part of the function where there is no recursive call.

Infinite recursion: When the function goes into an infinite loop since there is no base case.

Week 5

Lecture

So this week was just a bit more on recursion. We learnt a bit more on how recursion works and how to trace through recursion functions step by step. Tracing isn’t one of my strongest points so it took a few examples before I got the hang of tracing through recursion code, but it was definitely challenging in a good way and an interesting learning process!

One of our tracing examples was:

def rec_max(L):

"""

Return the maximum number in possibly nested list of numbers.

>>> rec_max([17, 21, 0])

21

>>> rec_max([17, [21, 24], 0])

24

>>> rec_max([17, [21, 24], [18, 37, 16], 0])

37

"""

return max([rec_max(x) if isinstance(x, list) else x for x in L])

The point I started understanding how the tracing for recursion worked was when I figured out when exactly I had to start using the base case and then work backwards from it. It was frustrating at first, but it worked out in the end! Another useful technique was learning when I needed to just plug in values so I wasn’t tracing too much.

We also got a few examples with the Python visualizer, which definitely helped when it came to tracing through the recursion and understanding the step-by-step process of such functions. We even got a bit of help on the move_cheeses function for our Tower of Hanoi assignment which definitely helped as both a recursion example, and understanding how to make the code in our assignment more efficient.

Lastly, we also went through a few unittest examples so we had a better understanding on how it worked and how to use it.

Lab 4

I probably learnt the most in this lab than I have in any other lab, since this time we actually got to practice using recursion for the first time! Our first two exercises were tracing through recursion code with pencil and paper, which is pretty useful since our exam will be the same way. Also we had to make sure we were following one of the programming rules: being lazy! While tracing through code, we had to try and plug in values we’d worked out earlier to avoid tracing too much, a pretty useful trick in the Python programming world!

The rest of our exercises focused more on actually writing our own recursive functions, which was a bit daunting at first since I’d never done it before. Luckily, after figuring out what our base-case was, my partner and I found putting the rest of our function in a lot easier than we thought it would be. So I definitely learnt a lot from this week’s lab!

Assignment 1

Now for an assignment update! My partner and I are making pretty good progress with it so far! We’re almost completely done with step 4 of our Towers of Hanoi assignment. We’ve finished our TOAHModel.py file and it works great with GUIController (It’s actually pretty fun to play). The TOAHModel file seemed pretty challenging to finish at first, but as we went through it and the code got more familiar then it gradually got easier. Hopefully ConsoleController isn’t much harder, but since we’ve got most of our code in, it shouldn’t be too difficult. 

This assignment is definitely a lot more interesting than 108 assignments since it involves trying to work with different files and making sure they work together, and we have to write our own functions instead of them being half-done for us. Since it’s a game, it’s also a lot more fun!

That’s all for this week!

Week 4

What is recursion?

Hey guys! So this week, our lectures were mainly focused on the basics of recursion. This wasn’t a completely new concept to me since I had gotten glimpses of recursion in CSC16 when we looked at the halting function. However, I was pretty unfamiliar when it came to actually coding my own recursive function.

I learnt that, basically, a recursive function is when you define a function in terms of itself. In other words, you call the function in its own definition so that you can use it to write smaller sub-problems. Most recursive functions are similar to if/else statements.

Recursion examples

For example if you wanted to write a recursive function for the sum of every even number up till a given even number, that woud look like this:

def sum_even_num(n):

                if n == 0:

                                return 0

                else:

                                return n + sum_other_num(n-2)

The most important piece of this function is the base case. This is the part of the function which doesn’t call itself, in this case, this is the “if” part of the code. If entered in sum_even_num(4) into the python shell, the following would happen:

1.       The function would go straight to the “else” part since n != 0.

2.       It would return 4 + sum_other_num(2)

3.       The function would loop over again and go back to the else part

This chain reaction would keep going until n = 0, and the function would return 6. The function would go into a chain reaction until it reaches the base case and has a final answer to return.

This week’s lab

I’d say this week’s lab was pretty fun. I got to practice coding some classes and Inheritance, and I worked well with my partner which is always good! The functions for motorized.py were easy to code, especially since we could relate them to real-life. I was already quite familiar with classes which also helped. The testing part of the lab took a bit more work, especially for me since I hadn’t used unittest that much in CSC108. But once we remembered the basic format and documentation for testing, it got a lot easier to write up the test classes. In general, I’d say that the practice from this lab made me much more confident about coding classes and testing functions.

Starting Assignment 1

So for our first assignment we’re supposed to recreate the game “Towers of Hanoi” which is linked here:

http://www.cdf.toronto.edu/~heap/148/W14/Assignments/A1/a1.pdf

So far my partner and I have read through the given code and added the basic methods to TOAHModel.py, so we’re off to a pretty good start!

My reaction

I really enjoyed the lectures this week, the fact that I was learning a new concept made it even more interesting. It was a bit difficult to understand at first but after I wrapped my head around how the base cases worked to stop the function I found it much easier to trace the programs. So understanding recursion was definitely my main achievement this week.

That’s all I can think of for this week! Good luck on Assignment 1!