Week 11: Sorting and Efficiency

Sorting is something intuitive for most people, we make quick comparisons to decide the placement of an item and sometimes even identify the largest (or smallest) items and put them in the "right" spot. Computers are most certainly more efficient than the average human mind when it comes to sorting very large arrays, but it's not intuitive - they need more specific, systematic instructions. However, some "instructions" (sorting algorithms) are certainly more efficient than others.

Some of the sorts we've encountered are:

•  selection sort - find the smallest item in the unsorted portion of the array and place it in its final spot
•  insertion sort - go through the list item by item, placing each item into its right spot relative to the already sorted items
•  bubblesort - go through the list comparing and swapping adjacent items as needed and repeatedly do this until the list is sorted 
• quicksort - choose a pivot and split the list into two; items smaller than the pivot (left) and items larger than the pivot (right) and then recursively call quicksort on both and then join the sorted left, pivot and sorted right.
• mergesort - split the list into two, sort each and then merge the two sorted lists

Generally, the first three tend to take the longest run time on lists which we can see by looking at the methods that are employed. For example, bubblesort looks at each item in the list multiple times before the entire array is sorted. So it's believable that bubblesort has O(n²) time. (Imagine how long that takes for n large!) The last two employ "divide and conquer" methods which are much more efficient when sorting. Mergesort and quicksort have O(nlogn) run time (the exception is the worst case of quicksort which has O(n²) time) which is much faster than O(n²) time. So quicksort and mergesort are much more efficient!

An interesting point to note, the built-in sort used by Python employs many different types of sorts, depending on the size of the array passed in, which is why it is faster than all of the sorts mentioned above - it makes use of all the benefits offered by various sorting algorithms!

Week 10: Something doesn't match up...

This week the second part of A2 was due, which involved 4 functions; is_regex, all_regex_permutations, regex_match and build_regex_tree. The first hill to get over was is_regex, since my thought process would use it in all_regex_permutations and use a very similar method for build_regex_tree.

However, regex_match gave me a lot to think about...and somewhat of a headache. No matter what I did or how I thought of approaching the problem, I couldn't figure out how to write the code so that it did what it was supposed to do in all cases. In the end, I submitted code that didn't work in (as far as I checked) one case, so hopefully I'll still do well. Turns out a classmate of mine had the opposite problem as me so we'll both have a look at each other's code to figure out our problems before the midterm on Wednesday.

Until next time, good luck!

Week 9: One big oh!

This week we did work on Binary Search Trees (BSTs) and in particular looked at deletion of data from BSTs during lecture. We also started learning about algorithm performance and analyzing the running time of an algorithm in terms of the size of the input n. We looked at the worst case scenarios of sorting algorithms and found that binary search is almost always more efficient than linear search which is pretty cool.

The idea of the big-oh notation is to give an upper bound on the worst case running time of an algorithm. For example, O(n) means that the algorithm's performance is directly proportional to the size of the input passed to it. Similarly, O(n²) means that the algorithm's performance is proportional to the size of the input squared. Since the big-oh is an upper bound, we can see that we can write things like O(n) ⊆ O(n²). That is, the run time of algorithms that are proportional to the size of the input will most certainly be less than (or bounded above by) the run time of algorithms that are proportional to square of the size of the input. In theory, the idea of an upper bound was easy for me to grasp but understanding it on an example is definitely something I have to spend some time on.

A2 part deux is due this week, so time to get to finishing it. Until next time, adieu!

Week 8: Inherit this!

This week I chose to write about the first part of A2...the regex trees.

To be honest, the first time I sat down to do some coding, I was barely making use of having a superclass even though I knew that the assignment was on inheritance. It took me 3 or 4 instances of copy-pasting chunks of code and only making minor changes to them before I finally stopped trying to plough on through the assignment. Even though I conceptually understood the importance and usefulness of inheritance in creating classes, I wasn't applying it. My code would have most certainly worked, I have no doubt, but then what would have been the point of learning and understanding inheritance if I wasn't going to use it?

In hindsight, it was funny to see the way I thought I had a good grip on inheritance and yet there I was, happily writing lines and lines of duplicate code. In the end (thankfully!), I found a way to make some serious use of my superclass and also learned a bit more about how I should be thinking when I'm trying to use inheritance. I guess what I'm trying to say is that it most certainly pays off to actually try applying the concepts we've learned on our own, even when we think we fully understand something.

On to Exercise 3 this weekend I suppose, so wish me luck!

Week 7: Recursion

Let's start with what recursion is...

Recursion is a method of solving a problem that is made up of smaller problems that are all of the same format as the big problem.

At first glance, this seems both confusing and somewhat useless. How am I supposed to solve a problem that is made up of essentially itself? For me, the key part to understanding recursion was the idea of having a base case and a recursive case. The base case is simple and easily solved and the recursive case is made up of the smaller problems that look like the main problem. So the idea is that all the recursive cases will eventually boil down to the base case (which we can solve) and then we can solve the main problem.

The structure of a (very basic) recursively defined function can look something like this:

       def big_problem(n):
           """ Solve this problem recursively. """
      
           # Base case
           if n == 0:
                  do something
           # Recursive case
           elif n != 0:
                  do big_problem(n-1)


Now if we think about this, for smaller recursive cases (i.e. 'n' is small) we can trace by hand what to do and eventually get down to a solution in terms of the base case which we can solve. But what if 'n' is very large or the body of the recursive case is more complicated than the function above? These are situations where recursion shows its true value. It can take a complicated solution to a problem and turn it into a very simple solution to code, provided of course, you can identify when to use it. And the easiest way to do this is by checking the definition given at the start.

So it's two thumbs up for recursion from me, adieu!

Week 6: Growing tree knowledge

As a follow up to the Tour of Anne Hoy, I (oddly enough) managed to figure out a solution to the tour_of_four_stools right after I published my post by refining my shakier ideas so I was pretty happy. :D The time module gave me a bit of trouble but hopefully what I submitted was good enough to get me a decent grade.

As for this week, we looked at the definition of trees, how we could represent them as nested lists  and we also spent some time on binary trees. It's quite similar to graphs (of graph theory) which I'm familiar with and I've also seen a recursive definition of binary trees in CSC240 so it wasn't too much new terminology. We also looked at  the three different kind of traversals that we can do: pre-order, in-order and post-order. Pre-order traversals are pretty easy for me to think about but for the other two I have to keep reminding myself of the definition when I'm going over the examples.

Reading week is here! :D ...so time to get started on studying for my CS midterms.

Until next post, ¡adiós!

Week 5: Towers of Anne Hoy

As a follow up to last week's blog, I did a little reading on property. I found Tamara's post to be helpful, so many thanks!

In this week's news, the Assignment 1 which is due on Thursday has been my focus. I've ploughed through Steps 1-4 and coded (perhaps not as elegantly as I could have) the pieces needed for the 2D and console versions of the game to work. But, (why is there always a but?) now I'm stuck in a rut for Step 5. I've managed to recursively code the M(n) function but I have no clear ideas for how to code the tour_of_four_stools. Hopefully some sleep and messing around with some of my shakier ideas will get me to where I need to be.

Until next time, enjoy this stack of cheese.

Photo credit to amelstrange of wordpress.

Week 4: Lab, Lecture, Let's get started on A1

This week's lab was on inheritance, unittesting (more robust than doctest, you create a subclass of unittest's TestCase to check specific cases for your code) and a bit on property. My group didn't manage to finish it but I think we all generally understood the concepts of all three. Personally, I have to do some reading to get a better grip on property and then see if I can use it on my own. Updates on that to come! :)

This week's lecture was focused mainly on recursion and Dustin did more examples. The remove3s function in particular stood out for me in terms of getting a better understanding of how coding for recursion works. The code side by side with the tracing of the current value of the list in an example with a nested list made it much clearer for me to understand how calling a function within its own body was possible. If you're uncomfortable with recursion, I think it's something good to look at it. I'm more comfortable after I had that concrete example that I could trace through for myself and then check. Figure out the base cases and then do the recursive cases!

I've started reading the code for A1 but the deadline is creeping up on me so I have to get started on some actual coding this weekend. I might get a group going on Monday with a friend so I'll see how that goes.

Until next week, see ya!

Week 3: Object Oriented Programming

To start, what is 'object oriented programming'?

Object oriented programming (OOP) is a style of programming that is used in many different programming languages such as Python(which we are using!), Java and C++. Just as its name suggests, OOP revolves around the idea of "objects". Objects are instances of a class and usually correspond to items or concepts that are in the real world. For example, the 'Dog' objects of the class "Dog" from Exercise 1 last week. These objects have attributes (like Dog.name) and methods (relatable to actions or functions that some item can do or have done to it) like play or call. This makes it easier for people who are not familiar with computer code or a certain programming  language to understand what the code is doing. It also breaks up what otherwise would have been large chunks of code that did a variety of operations into smaller, more manageable pieces which are grouped by their relevance to each other. 

Seeing as the only coding I've been doing has been this past semester in Python, OOP is the only style of programming that I know and I wasn't even aware that I knew it until doing this course. From the reading that I've done about it and my experience, OOP makes sense; well organized code that is easier to understand because of its association with real life items. OOP also has the benefit of inheritance. This is where one class gets most of its attributes and methods from a parent class (and will also acquire any changes made to its parent class post-creation). Inheritance is useful when you want to modify a class in possibly different, incompatible ways or when the original class was sufficient for one audience and the extension of its features would just create clutter. 

I'd love to hear the thoughts of people who have coded in other (possibly less object oriented) programming languages, so comment away! :)

Weeks 1-2: And so it begins...

 ...with the first post of the semester!

Week 1's class for me felt unimaginably long, but I have solved the problem in week 2 - a snack to get me through it!

In week 2 we were introduced to Abstract Data Types (ADTs) and recursion. I really like the concept of ADTs, it's a way to define a class and what that class can do without explicitly writing code for it. This way, the class and its methods can be implemented in many different programming languages. On a smaller, more personal scale, I see it as a way of planning out my moves when creating a class for an assignment.

Recursion is where you call on a function within the body of the function itself. It's a really clever way to deal with certain problems and the example on removing nodes that have less than n edges from a graph really helped me to understand where you would use recursion. I suppose part of that is because I was able to visualize the problem more clearly since I've had some exposure to graph theory.

The first exercise was pretty simple, just review of material covered in CSC108. The hardest part was retraining my brain to match the PEP8 style guidelines but I suppose over time I'll get used to it.

Until next time, ¡adiós! :)