Sorting Algorithms

Selection sort is an algorithm that iterates through the list, finds the smallest value and moves it to the front of the list. It repeats this process for the rest of the values until the list is sorted. In this algorithm there is a nested for loop the outer iterates n-1 times and the inner (n-1), (n-2), ... , 2, 1 times which gives this an efficiency of O(n²) for its best, average and worst case scenarios. This is an inefficient method for sorting lists with a large number of elements.

Quick sort is a recursive sorting algorithm and is more efficient on average than selection sort. It starts by picking an element in the list to be a pivot. It then reorders all elements in the list that are lower than the pivot to come before and the greater elements to come after. Then the list is partitioned into two sublists, elements greater than and elements less than the pivot. Then the algorithm recursively sorts the two sublists and concatenates quicksort(lower) + pivot + quicksort(greater). This algorithm has an average and best case efficiency of O(nlog(n)) which makes it much more effective for sorting larger lists than selection sort was but its worst case is O(n²) which means its efficiency is unreliable and at times can be as slow as selection sort.

Merge sort breaks the list of elements into sublists of length 1. Then it uses an algorithm which merges two sublists to create a larger and still sorted sublist. It continues on this process of merging sublists until one final sorted list is formed. The merging algorithm compares the first two values of the sublists and takes the smaller one and appends it to the resultant list. It continually compares the first to values and appends until all elements are placed into the resultant list. Merge sort has an best, average and worst case efficiency of O(nlog(n)) making it very effective when sorting large lists and more reliable than quicksort.

More Binary Trees

Today in the lab we worked on an interesting new approach to binary trees. Rather than using a separate class for each node in the tree we kept track of every item using the built-in Python list class. There's one condition with using this technique and that is the tree must be fully complete, the items fill up the levels one by one from left to right. For example if your tree contained these items [1, 2, 3, 4, 5, 6] the tree would always look like this:

But it could never look like this:

Every level must be filled left to right no matter what. This implementation is interesting because the only information you have about each node is it's index in the list. This means that in order to find its parent or child nodes you need a formula that takes the nodes index and outputs the index of the parent/child. I was able to find this formula by writing out the the first 4 or 5 cases and looking for a pattern. For example, the index of the left child 'j' of a node at index 'i':

 i      j 

0 -> 1

1 -> 3

2 -> 5

3 -> 7

Then using this data I tried to find a pattern. In this case j = (2*i)+1, so the index of every left child of a node at index 'i' is equal to (2*i)+1. After finding the patterns for navigating the index's for parent and child nodes you could put them into methods and basically use the same techniques for solving inorder, max_sum, etc. 

Term Test 2

So yesterday we had our second and last term test. I think I did alright, I have a feeling I messed up the first question but I know I did the other two correctly. Two of the questions were on binary trees and one was on binary search trees and linked lists. I was expecting to see some Big O questions on it but there weren't any. Hopefully when I get this test back I can also pick up my first test because I still haven't gotten around to it. I don't even know if they would keep it for this long, at minimum I'll find out what mark I got on it.

No classes or labs this week because of the fall break in combination with the midterm.

Term Test 2 Coming Up

This week we got today and yesterday off for fall break and remembrance day. Tomorrow is our second term test, time to get studying! I feeling slightly less confident about this one because its not completely review for me, a few things are new concepts. I'll probably read over all the lecture slides then finish the labs I missed or didn't complete and hopefully I should be ready after that.

Assignment 2

So I didn't go to any lectures the last two weeks. Probably wasn't the best choice but I'm finding it no problem keeping up with the material being covered. I went to the lab today but unfortunately missed the one last week. Today we had to implement certain methods that worked around binary trees and linked lists which I found to be challenging at first because of how new I am to linked lists.

Our second assignment was due a couple days ago, we had to implement regex and match them to strings. Regex are completely new to me but after reading over the outline a few times then checking piazza for how hints I was able to quickly throw together something that ended up working. There were a couple bugs in my code that I took some time to work out. For example, when a DotNode is in a StarNode my code would return false when matching the regex to a string. The error was the way my code checked to see if a StarNode matched the string, it iterated through every single character and matched it to the StarNodes child. I realized the reason this was giving me errors was because with a DotNode the string is more than just one character long, I had to find a new way to match StarNodes. I was able to solve this issue and then used all the test cases posted on piazza to make sure that everything worked properly.

Midterms and class this week

Last week on Wednesday we had our midterm for the course which proved to be not as easy as I had expected. I was pretty confident going into the midterm since I have a lot of experience in computer science and most of the content we cover is review for me. I made a page long aid sheet with just the names of the python methods for basic classes like List, String, etc. since I'm completely new to Python as of taking this course. I ended up not even using it once during the test because I didn't really need to use anything that I put on it. One thing I didn't know was what the how min() method determined which tuple was the smallest. I guessed how it worked and then I checked when I got home and it looks like I got it right. One thing I forgot about on the test was how to create a copy of a list. I was able to find a workaround that still ended up working when I checked so hopefully I don't lose any marks for having a "less correct" way of implementing it. Other than those two issues above I pretty much found the rest of it fairly easy. I'll have to wait to see what mark I get next time I got to class.

This week I didn't go to any of the lectures mostly due to staying up too late and sleeping in. This was fine by me because I'm mostly self-taught when it comes to computer science and I figured I'd be able to catch up just fine. It surprised me when I went to the lab today and I for once didn't know something that we were working on! We had to implement a Linked List which I had never heard of before and since I didn't go to the lectures I had no idea what was going on. Luckily the slides from this week were posted online so I was able to quickly read through those and check online to figure out how they worked. After that I found linked lists to actually be quite interesting and learning something new was also quite fun. I was still able to finish the lab without much difficulty and was able to leave 15 minutes early too!

Object-Orientation and Recursion

Object-oriented programming and recursion are both key concepts in computer science. They allow for the programmer to simplify and efficiently solve both theoretical and real-world problems.

Object-oriented programming essentially means that a program is being broken down from something general into multiple simpler and smaller parts which are known as "objects". These objects can have attributes which store the properties or state of the object and they can also have procedures or methods which execute certain tasks or perform a certain calculation and allows the objects to interact with each other. Object-oriented programming is the most popular form of computing nowadays because of how well it breaks down large complicated problems into small and manageable tasks.

Recursion is a way of solving a problem which involves repeatedly using a recursive method or procedure. Commonly a method that solves something recursively will break the problem down into its simpler or smaller repetitive parts and apply itself to them. Any recursive method can also be accomplished iteratively but for some cases recursion is more efficient than iteration. For example, when navigating binary trees or solving the Towers of Hanoi problem.