Week 12: Sorting and Efficiency

Despite how fast modern computer seem to accomplish our everyday tasks, there are still physical limits on the rate at which they can process information. It takes a real, non-negligible amount of time for a computer to read and execute a line of code. When performing a task on an input of a given size, some algorithms can be very efficient for small sized inputs, and hopelessly slow for larger inputs. This efficiency can often be modelled mathematically, as we will see.


When modelling the speed, or runtime, of a computer program, it is important to always take the worst case scenario. This means that it is the most useful if size is not considered the only factor, but other qualities of the state of the input as well. For example, if a sorting algorithm takes a list of 100 elements, it is not immediately clear how long it will take to process, since nothing is known about the state of the input, other than its size. It might already be sorted, in which case it would be absurd to say the algorithm works instantly for all inputs of that size. For this reason, it is important to take the worst case: the input of a certain size that will cause the algorithm to run for the longest time.


In class, we learned a variety of sorting algorithms, including insertion, selection, bubble and merge sort. Of these four, the first three have O(n^2) worst case time complexity, meaning for if the input is varied by n, then the time they take to sort the list varies quadratically. This means that for large inputs of n, they will take a long time to finish. Merge sort is different; it is O(n*log(n)). For large n, logn will be less than n, so this algorithm is faster than the previous three. However, this does not necessarily mean merge sort should always be used. For small inputs, it is unclear which of the four (and many more) algorithms is best.

Week 9: Binary Search Trees & Algorithm Performance

This week we learned about BSTs, another recursively defined data structure. These are basically trees, only with the property that the given value on a node decides what values fall under the its left and right subtrees. Values that are larger than the value on the node are all in the right subtree, and other values in the left. This organization allows for fast traversals, and for us to be able to quickly find the value we are looking for, since each step eliminates approximately half of all remaining places to search.

We were also introduced to runtime efficiencies and big O notation, as well as a review of logarithms. For me, all of this was basically review of concepts already learned in csc240 and high school math.

Week 8: Linked Structures

On monday we learned two different ways to imagine linked lists. Seems like a sufficiently intuitive concept. The idea of the "wrapper" class was something I hadn't thought of before. I like the idea of it, but it makes me wonder if there are other ways we could increase efficiency when dealing with these structures.

Not much else to say about this week. Part 1 of Assignment 2 is now complete. I like how 148 gives a "soft" introduction to regexes, maybe even underselling their importance to computer science. It warms you up to the concept without getting into the more mathematical side of them, so that when they will come up in later courses I think I'll be partially familiar with how they work.

Week 7: Recursion

In computer science, recursion is (loosely) the idea of defining something in terms of itself. It is useful as it allows for flexible, concise code. My experience with recursion in 148 has been entirely in the context of using it for defining functions in Python, but I suspect it can used in other ways/types of definitions.

Usually, these recursive definitions have at least two parts to them, both of which lie behind an if statement. The first is the "exit clause", for cases in which the function is called on the most basic elements. It signifies the end to that particular recursive loop, and is comparable to the "base case" of proofs by induction.

The other half is more interesting, and is where the actual recursion takes place. If the given value does not satisfy the exit clause, the function will call itself again on the object. To prevent infinite loops from occurring, this new call shouldn't be on the exact same object; it should be on a modified version of the object, or a specific part of the object. Continuing the induction analogy, this would be the inductive step.

For example, when calling a function on a list of nested lists, often you will want it to be evaluated on each of the most nested lists. A recursive function would see if the current list contains more lists, and if it does, call itself on each of the smaller lists. Without recursion, this would likely require multiple functions and complicated regular for-or-while-looping.

When writing code, the recursive call should be placed after the exit clause. This is to ensure that the recursive calls don't go on indefinitely, since the exit clause will never be reached if it comes after. One has to be careful not to accidentally create infinite loops. Thorough testing is necessary.

Object oriented programming... First post!

Hello and welcome to my course blog. Here is where I will be documenting my thoughts, questions, and experiences with csc148.

The subject of this week's post is object oriented programming, abbreviated to OOP.

What is OOP?

By necessity, different programming languages are designed in fundamentally different ways. One such classification is by paradigm. Wikipedia tells me that there are five main paradigms: imperative, functional, logic, symbolic, and object oriented. In my limited experience, I am only familiar with Python, which is of the latter category. 

OOP languages are characterized by, as their title implies, a focus on virtual objects, and how they interact. In the case of python, these are called classes. Classes are kind of like containers: they contain both functions and data. They are often based on real world objects, or mathematical concepts. 

For example, someone could use a class to model nxn matrices. Inside this class there might exist functions, such as "invert matrix", as well as data pieces like "the identity matrix" which could be useful for operations that use the class.

Another important feature of classes is interaction between classes. For example, python allows multiplication between integers and floating point numbers, despite their being different classes. This is due to something called inheritance. Classes can take on, or inherit, functionalities present in other classes, allowing for more efficient and better structured code.

That is my basic understanding of OOP as it stands. As I go forward in computer science, I expect that my perspective will be expanded greatly.

Weeks 1-3 of the Course

This section is just some personal thoughts about the course so far. I have really enjoyed both labs, as well as the first homework assignment. The pacing of the course is on point as well, at least so far. I'm excited for the first major assignment. 

-Jesse