Week 11 - Sorting and Efficiency

Sorting algorithms seem to be the go-to example when doing runtime analysis, and talking about a program's efficiency. It makes sense, I suppose, since it gives examples of runtime ranging from nlog(n) to n^2, where n is the length of the list. Of course, there are other types of algorithms that can have all sorts of runtimes, but those are not important.

The most basic sorting algorithms are bubblesort, insertion sort, and selection sort. All three of these algorithms have double-nested lists both of which have a maximum runtime of n steps. This results in a worst-case runtime of approximately n^2 steps. As such, when working with large lists, these encounter issues, but are simple to code and work decently well for (very) small inputs.

Far better sorting algorithms are mergesort and quicksort, which are both recursive algorithms with a worst case performance of nlogn. Well, actually, quicksort can possibly have far worse runtime, but this can be largely solved by randomly selecting pivot points, unless RNG hates you.

Week 10 - Near the end

One of the more difficult things in programing appears to be finding good test cases for one's functions. Good testing is, of course, essential for ensuring that one's program functions properly and behaves the way that it should. The issue then, deciding how to test it. The basic ideas are rather simple. Test cases should cover all the different types of inputs or situations. Yet like many things, this is far easier said than done. There are situations and inputs that one may not have thought of, or it may be such that a certain case may be difficult to actually test. All of this makes testing sound far easier than it actually is.

Also, couldn't quite figure out the lab this week. Need to think more about this.

Week 9

Exercise 3 went by rather easily as long as one thinks recursively, although it took a bit of thinking, particularly in the case of a two-element tree. In such a situation, I chose to resort to a rather a bit convoluted, semi-manual strategy.

Assignment 2 part 2 also ended up a little convoluted when it came to working with bar and dot regexs (is that the proper plural?), although it was also not too complicated. It helps that two totally separate functions have essentially the same structure however. In total, I spent about 5 hours on it.

Week 8 - No Longer Considered Late (by definition)

From now one, works posted on Monday of the week after will no longer be considered late, by my new definition of the term.

The focus of the past week has been an part of an assignment based around the creation of a tree structure, and an exercise to create and analyze trees. Both went on without considerable difficulty. The tree exercises did however, emphasize the importance of thinking about recursive problems recursively, rather they trying to get a closed solution for them.

Week 7 - Recursion (Slightly late again)

The topic of this week is recursion. To sum it up simply, recursion is the process of calling a function within itself, although it can more accurately be described as repeatedly performing the same action on a certain object. In computer science recursion and loops are generally seen as two ways of doing the same job in most cases. Unlike with loops however (unless somebody uses "while True"), one must be careful with recursion to make sure there is a stop condition in the function. If one doesn't, they run the risk of running out of memory space, which, suffice to say, may cause issues. For some situations, such as when, one is going over a nested list of unknown depth, recursively going over the list is far simpler and more efficient than using loops.

To recursion, if I need to find out the minimum number of moves needed to complete a Tower of Hanoi game with x number of blocks and 4 pegs,

def best_split(n: int) -> int:
    """Determine the optimal value to split at."""
    choices = [i for i in range(1, n)]
    num_moves = []
    if n == 1:
        return (1,1)
    else:
        num_moves = [(2 * best_split(n - i)[0] + 2 ** i - 1) for i in choices]
        optimal_i = choices[num_moves.index(min(num_moves))]
        return (min(num_moves), optimal_i)

Note that this function also returns the best value to split the tower at, but that is largely irrelevant to the current discussion. As can be seen, I call the function within itself at line 8. I also have an appropriate stop condition where the function will stop running at line 5. Both are necessary for a recursive function.

Recursion has, at this point, permeated so much into my life that I think about iterative problems recursively.

Week 7 - Nothing to report

Reading week. Have a test and assignment coming up, but that can wait. All quiet on the western front. Got an interesting question from a younger friend regarding breadth-first searching though. Searching it up, it seems rather pointless. Will need to investigate further.

Week 6 (apparently)

The topic once again falls back to recursion. More specifically, Assignment 1. After experimenting with a few different ways to solve the Tower of Hanoi with four stools in the fewest moves possible (with varying levels of success), I managed to find, with great difficulty, the minimal number of moves and the optimal split value i recursively. Unfortunately however, in this configuration, I was not able to actually move the cheeses in any stacks totalling more than ten blocks without attempting an illegal move, something I was able to accomplish with more basic splitting methods. It certainly did not help that my computer decided to die on the due date, but fortunately I had already submitted the files beforehand. And people wonder why I hate computers....

Week 5 - A bit late

As mentioned, this update is slightly behind schedule thanks to a preoccupation with the Tour of HanoiAnne Hoy assignment. While not complete yet, this assignment has been the object of particular annoyance for the past week or more, and I have not yet even worked on the recursion part, which will probably actually be easier, interestingly. One positive product of this however is that I finally decided to make use of doctest, and to good effect. On the other hand, I really wish instructors gave better descriptions on how to use code that's provided. I spent about an hour messing around with the GUIController and trying to debug my own code, not realizing that I was supposed to click on the "stool" rather than the space above it in the interface.

Week 4

Recursion is the hot topic this week, but for the large part, that's a topic for another time. I already know the basics from beforehand, and I would say it is fair to say that recursion is surprisingly easier to understand than it is to explain without the use of aids.

So, without further delay, rather sure than talk about recursion, I will talk about errors and exceptions. The basic concept is rather simple, plan ahead for errors that might occur, and deal with them. That said, it took me quite a while to figure out what Exercise 2 meant when it said to raise an exception implicitly, even though, as it turned out, I had done it that way all along. Using unittest to check if an exception is properly raised was also an annoyance during the lab, thanks to the not entirely intuitive way that assertRaises works, and the Library not being entirely clear on that.

Object Orientated Programming

Object orientated programming refers to the programming paradigm involving "objects" that have their own data and functionalities, and interact with one another. It has been stated before that to learn OOP, one has to unlearn any programming that they had learned before. While this exaggerates the learning curve and degree of difference from procedural or "regular" programming, it does indeed capture the fact that OOP requires a different type of thinking, largely based upon how different objects interact with each other.

At first, it can be difficult for one to wrap their head around the notion of separate objects interacting with each other, or than in a program, one works with an instance of an object rather than the object itself. This type of programming becomes particularly useful when designing large programs, with the most immediately obvious reason being a more efficient organization of more readable code. More importantly however, in using instances of objects, OOP allows for multiple "objects" (as opposed to proper objects, ie classes), with the same behaviour without repeating code, as well as allowing them to interact with each other. Inheritance also allows for building objects off of existing, similar objects. For smaller, simpler programs however, OOP often presents itself as an unnecessary complication, resulting in extra work and code.