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.