Week 11 - Sorting Algorithms

It takes more to put a list in order than it may seem. This week we spent time covering different kinds of sorts, their implementations and strategies and how efficient they are. I suppose you can say sorting was the key topic, but I think it is more of an example of the more general concept of algorithm efficiency. By analyzing the steps involved in each search algorithm, particularly the number of times the algorithm had to look over or modify the list, a comparison could be made between them. Abstracted to a n-element long list, the comparisons could be read out as complexities for each algorithm, to show why a particular one worked better than another.

Abstraction aside, generally merge and quick sorts followed by insertion sort were the preferred ones as they executed the fastest, and typically bubble sort was the worst. In some cases, such as the list being reversed, this did not hold true. Though we did not go over it in detail, I looked into Python's built-in list sort, timsort. It appears to be a combination of merge sort and insertion sort, calling the merge sort initially to break up the list into smaller ones at which point calling insertion sort on them is quick and easy. It then reconstructs the sorted list using the merge sort functionality.

Lab this week was also focused on this, timing the various sorts for various cases and coming to the conclusions above. It also went into looking at ways of making functions more efficient, by storing repeated calls of length, for example, as variables and just using the variables as needed cutting down on execution time by the number of lowering calls.

Week 10 - A2

So this week's slog is late. My fault? Yes, but in my defense, A2 made it difficult to work on anything else. The trouble I had with A2 was mostly that I could not think of an easy way to recursively deal with parentheses in the given regexes. It was hard to come up with a way to deal with them which also took into account the presence of the * character. In the end, I had an algorithm which basically made sure that the number of left parentheses was the same as the number of right parentheses, and which featured a decrement counter. Each time it came across a right parenthesis, it would decrement and deal with the string slice from the last left parenthesis, and check if it was a regex. Ultimately, my group did not end up using this, mostly because it tended to fail when *'s were introduced.

I feel that in this case, the recursive logic came easily, but it was difficult to properly implement into code, due to the amount of cases to consider, as well as the special characters which added complexity.

Week 9 - Working with Binary Search Trees

This week has been all about binary search trees, from lecture to the lab and even the exercise. Binary trees, as mention earlier, have up to two children per node, and the child to the left of the node has a value less than the node, whereas the child to the right of the node has a value that is greater than the node. Of course, the children can also be other binary search trees.

The key point I want to mention is something that came up over the course of doing the exercise. I will not say too much, as the deadline has been extended, but it is about the recursive logic. For the first part, I reached the point of understanding that the preorder traversal will give the nodes of the tree while the inorder traversal would help me identify the subtrees. Initially I thought that the node from the preorder tree should be removed from the inorder traversal, and doing so recursively worked in certain situations, but created a mess later on. After some thinking I realized that I would have to create new lists at every point to ensure that there was no mismatch. As for part B, all I can say for that is that it has taught me to thoroughly count brackets...

The lab went really well so not much to mention here, other than abut the iterative method that we were supposed to come up with. I know the point of this was to teach us to represent the tree as a ADT which we could work with at various points of execution but I came up with a method to solving this which I believe works well or even better than the solution mentioned, at least for small trees. Seeing as this part did not mention that we could not edit any other functions, all I did was add a line to the __init__ method, where I copied the list into a variable and then in the method i just iterated over that list using a for loop and a counter, incrementing the counter every time my condition was met. I liked that this approach made use of the list of nodes (which can be easily created, if not explicitly given) and just basic iterative logic; looping over a list with a for loop, checking for a condition to be met. While it was not the method that was desired, it is at least worth considering.

Week 8 - Linked Lists and Binary Search Trees

The best part of this week: the lab. After the failure of my partner and I to properly delete elements from a linked list, (we reversed it, decapitated it and re-reversed it) we felt that we had little to no understanding of them. Turns out we were wrong, as in this lab we were able to do pretty much every exercise on the lab sheet with little to no problems. The recursive logic came easily and quickley.

As for lecture this week, the topic was binary trees, essentially just a type of tree consisting of nodes which have up to two children. The logic for this is that they can be parsed through easier to find a specific value, which could be useful in some applications. The problem is, I do not really see an easy way of creating such a tree for a given set of data, other than inserting the values in one at a time, which is not efficient at all. Without that it seems pointless as it may just be easier to put it all inot a list and search for something that way.

Recursion

Recursion is a method of problem solving in which you break apart a problem into less complex instances of itself in an attempt to find solution. This will hopefully break down into a simple base case which once solved can solved a more complex iteration of the problem, eventually leading up to the solution of the original problem.

In my experiences, recursion has been more like... trying to break down a problem into a simpler form and ending up confused for a few hours. Lately this has become easier as struggling with it during the assignment forced me to think about it in different ways, leading me to a way of breaking down the original problem that seems to work better for me. Instead of thinking of a slightly simpler instance of it, I try and imagine what steps are involved and how they link together.

As for the power of recursion, it does indeed simplify problems once you obtain a recursive formula or algorithm as it automates the process of solving the problem and you can simply extend the formula for specific cases.

Week 6 - Trees and the Linear Algebra Lab

So this week's lectures were on trees, a topic I found to be confusing mostly because I cannot think of any reason that one would use such a datatype... that is if it is a datatype. My biggest issue with them is that they can only have sub-elements which are also trees or None. The way we analyzed them, traced through them and defined properties and methods for them were fairly straight forward and really the main point was to realize what the appropriate base case should be. The recursive algorithm to trace though all nodes was simple as well. Trees, what are they good for?

The lab this week was the first time material I've already learned came up in computer science. Having completed linear algebra last semester made this lab easier as both me and my partner had previous knowledge of how vector multiplication worked and how matrix-vector multiplication worked. This lab also gave me some insight on how computers view matrices and vectors, as list objects. The lab also gave me some ideas on how I can apply what I have learned so far, for example try to come up with recursive and non-recursive functions that preform other matrix and vector operations that we learned in linear algebra.

Oh yeah... Assignment 1 was due this week. For me, most of it was easy and straightforward except part 5, which took me 2 days to do. I just kept getting a maximum recursion depth exceeded error, and eventually I figured it out. I was doing the silly thing of calling my function to move cheeses using four stools in my function to move cheeses using three stools, instead of having it call itself. After that was cleared up the rest came quickly. So how did you do, as in did you finish and attempt the bonus? Or were you too lazy to do it and just submitted it without it?

Week 5 - Well What Did You Learn?

Not much new this week, with more tracing recursive algorithms. Well, we did learn about scope, basically where Python looks for pieces of code depending on how "accessible" they are. Code can either be restricted to a certain method or function, available locally or made global so that it is defined for the entire file. I suppose that's good to know, for whenever it comes up as well as for tracing code which has this hierarchy.

The lab this week was really useful, practicing coding recursively and going through the process of getting to the recursive insight. Once you understand it and struggle with it, you realize what to do and after that, it seems much easier. For instance, my partner and I spent the majority of the lab trying to do the first recursive code that we were supposed to come up with, tracing out test cases multiple times. After almost an hour, we figured out what we needed to do and got it working. We moved on to the second problem and solved it in under five minutes because it seemed so easy after having spent so much time thoroughly analyzing the code for the previous question.

As for Assignment 1, progress has been... slow. I find it hard to figure out how to implement some of the methods required and because of that I keep stopping after an hour, giving up. I know that the Towers of Hanoi code we analyzed will help sooner or later, but now it seems pointless. Well, how about you? What did you learn from this week's lectures and has it helped you at all?