Week 11: Sorting and Efficiency

The way we describe a program's efficiency is by measuring its “big-oh”. If f(n) is the function of the runtime of a program with input of size n, its big-oh is an upper bound of f(n). Here's the order of big-oh functions, from smallest to largest, or best to worst:

There is a large variety of sorting methods. Efficiency is an important characteristic that distinguishes these different methods. In CSC108, we learned bubble sort, selection sort, and insertion sort. These methods were easy to understand, and work well for lists of smaller sizes or lists that are close to being sorted. However, these methods all make a large number of redundant comparisons between items, so their runtime grows exponentially, quickly making them very inefficient. In CSC148 we learned quicksort, merge sort, and heap sort, all of which are far more efficient because they make far less individual comparisons and passes through the lists.

A helpful classmate posted a link to Big-O Cheat Sheet, and here's a chart detailing the efficiency of the sorting methods we covered in class.

I learned something very interesting in lab this week: that Python's sort() function is extremely efficient because it chooses the best sorting algorithm to use based off the list you input. Good work, Python.

It's easy to forget to pay attention to efficiency when writing programs for class because we often don't have to deal with large inputs. However, it the real world efficiency is absolutely crucial. Do you think Google would mind if their search algorithm took hours to return results?

Well, that's all for now (and ever).  

Week 8

Lectures this week focused on LinkedList, an abstract data type. They are composed of a head and a tail. The head contains a value/object, and the tail contains another LinkedList, and so on and so forth. Spoiler alert: this data type links very well with recursion!

Last week my partner and I had difficulties using LinkedList, but this week we really spent time visualizing them and talking to our TA until we definitely understood them. Drawing what happens to LinkedLists during prepend, decapitate, etc, especially helped. I plan to use the process of manually drawing out what happens in code in the future because it's definitely an effective learning tool.

Test 1 results were returned and I was very happy about them. I only lost one mark, but with the adjustment over different test copies I gained .7 of a mark! Aren't mark adjustments the best?

Week 7

I tried finding a good recursion joke as an intro for this post, and this is what happened:

Oh Google, you're cute.

I'd also like to give credit to Sobbing Mathematically for finding this gem:

        What’s Benoit B. Mandelbrot’s middle name?

        Benoit B. Mandelbrot.

Okay, I'm done with the mediocre jokes for now.  This week's topic is recursion!  Recursion is a self-referencing form of repetition. Most recursive functions have a conditional statement within them that either calls the function again or does not. The latter is called the base case, the section of a conditional statement that does not provoke recursion again. A base case is all that keeps a function from entering into infinite recursion, which is something we'd like to avoid. Thankfully instead of letting a poorly written recursive function fall deeper and deeper within itself until the end of time, Python soon raises a runtime error for “maximum recursion depth exceeded.” I'm actually quite curious as to what defines the maximum depth.

Recursion is definitely a large part of this course (especially in A1,) and considering how helpful and concise it is, I don't doubt it will be a large part of future courses and careers. The computer science community is not wholeheartedly set on recursion however, for depending on the situation and language, iteration can take up far less time and space.

At first it was difficult to visualize how a recursive function would work, or how I wanted one to work when writing my own, but after manually writing out the tracing of a function I've found them much easier to understand.  The more I studied it, the easier it got.  What a surprise!

Week 6

The topic of the week was Trees, which are an abstract data type. Let me break it down for you. A Tree is a set of connected nodes containing values. A root is a node with no parent, there is exactly one root per tree, and every other node has exactly one parent. A leaf is a node with no children. Height is the longest path in a tree, and arity, or branching factor, is the maximum number of children on any node in a tree.

Tree traversal is a difficult concept to write about because it requires a visual understanding. This video, posted on piazza by a helpful classmate, made me understand traversal so easily. To recap:
Pre-order: root, pre-order left subtree, pre-order right subtree.
In-order: in-order left subtree, root, in-order right subtree.
Post-order: post-order left subtree, post-order right subtree, root.

We also went over the implementation, methods, and attributes within the Tree ADT. It will be interesting to write programs utilizing Trees in the coming weeks.

In Lab 5 we looked at functions written with comprehensions, including Python built-ins zip and filter. The goal was to rewrite these functions without comprehensions, so in other words to manually expand them and as a result better understand how the comprehensions work. My lab partner was absent, but even with working alone I didn't find it too difficult. All of the tools shown in this lab will definitely be helpful in the future as they make code cleaner and more efficient.

A1 was due this week, which I handed in on time, woo! While it took longer, I'm glad I worked alone because it ensured that I understood all of the code, and I know that will help with future tests. I would have liked to spend more time finding the optimal solution for four stools, and I'm confident I could have completed the bonus portion, but in the middle of midterm madness I had to prioritize and chose not to do those things.

Reading week time! I hope to get work done, but we all know that's not going to happen.

Week 5

In lecture we further discussed the Tower of Hanoi problem, specifically looking at how recursion can be applied to solve it. We analyzed a move_cheeses function to recursively solve the problem of three stools, and it's up to us to edit that code work for four stools. The deadline for A1 is quickly approaching, the horror! We also talked about tracing recursion and how you should only trace far enough to understand it; tracing too far can quickly get veeerrryyy complicated. I've been finding recursion tracing a bit confusing and difficult to visualize, so I plan to focus on that when preparing for Test 1.

Another lecture topic was scope. From smallest to largest, the ranges of scopes are:

• Local: default scope of a variable when it is declared. This scope only covers within the function the variable is declared in.
  
• Nonlocal: useful with nested functions, a local variable declared in the outer function can be declared nonlocal in an inner function to access it there.
  
• Global: the largest scope. When declared global, that variable is accessible in every scope.

An example of how the use of these different variable declarations affects their scope can be found here. It made the concept of scope very clear.

This week was the first lab I missed because I had a calculus term test that afternoon and chose to prepare for it instead. I'll go over the lab when I have time (so in other words, probably not until summer.)

Week 4

This week's lectures discussed Assignment 1, recursion, and testing. I have yet to find time to meet with my partner, so I have only read over the instructions and given code for the assignment.

Exercise 2 seemed daunting at first, but once I actually started writing the code for it I realized it was very simple and quick to finish. The exercise's use of Exception subclasses with more specific names is something I intend to use in future assignments. I'm glad we covered exceptions early in the course because they are an easy and effective way to make a program much more professional.

The lab this week went well, especially because I am very fortunate to be working with a partner who is on the same page as me in terms of work ethic, and whom I get along with very well. This not only helps me learn much more during the labs, but it also makes them far less headache inducing than they can be. The only things I had an problems with was the optional use of “property” to prevent clients from altering attributes in ways you don't want to affect your class, and some syntax things about unittest. In these labs, whenever you need to show or ask your TA something, it can take up to fifteen minutes before they get around to you. As a result, I didn't have the opportunity to clarify property, but I intend to ask about it at the beginning of next week's lab.

In my physics class I was able to complete a problem set question much quicker by writing a program than by hand. The skills I learn in computer science are often transferable to my studies in physics.

Week 3

Hello, world! (Sorry, as cheesy as that is, it seemed like an appropriate beginning.) Please pardon the wonderfully awful pun I used for this blog's URL.
     
This week's topic is Object Oriented Programming (OOP), which is exactly what it sounds like: programming that is oriented around objects. CSC108 mostly taught procedural programming. While there is no noticeable difference in productivity between procedural and OOP uses, according to a study by Potek et al, OOP became the most widely used programming paradigm in the 1980s because it is a much easier approach to conceptualize because it feels much less like being in the Matrix and much closer to reality. A reading assigned in week 1 of CSC148, a section from How to Think Like a Computer Scientist: Learning with Python 3, states, “Usually, each object definition corresponds to some object or concept in the real world, and the functions that operate on that object correspond to the ways real-world objects interact.”

Objects are instances of classes, and instances are specific versions of an overall type. For example, I am an instance of the class Student. Every class is comprised of specific behaviour and attributes, or methods and data fields. They allow you to create new data types that aren't already built in to your language of choice. Speaking of languages, Python, Java, and C++ are the most commonly used languages for OOP. In CSC148, we work solely with python. I have two years of previous experience working with an object-oriented approach in Java, so I am certainly not struggling to understand the first three weeks of material in the course.

Well, that's all that's required for now. See you next week!