Today we focused on sorting algorithms and re-creating Conway's Game of Life!
We analyzed different sorting algorithms to see why they had their notations. So when we traversed our binary search tree, that would have an O(N) because we traversed by splitting the tree in half, and I guess that's a linear operation, because when you add more nodes to the tree, you're still just splitting it in half. LOL, sorry I'm still working out the more complex cases of this concept, but if I keep analyzing functions I'm sure I'll get it.
Important Update Amendment: I wasn't being clear at all. :'( Searching through a BST is O(log n) because you eliminate half. (Like, the number you're searching for has to be bigger or smaller than the root) Traversing is O(n), because you have to touch every node. Ugh, clearly this is something I should go over again, lol.
So after we had that lecture, we started to write two sorting algorithms: bubble sort and merge sort. Oh- and we had to write our own test cases! That was pretty exciting. For bubble sort, we used a nested for loop to swap items in the array while simultaneously shifting our start point.
Then, for merge sort, we created three functions. One split the list in half, one sorted the array, and the other one merged the left and right sides. The recursion aspect of this was tricky. It's just difficult to intuitively visualize the call stack!
What we did was, split our original array into an array of two arrays, left and right. Then we called the merge function (the one that actually sorts) on the recursively split arrays. Our base case was when the array was one element, which meant we had to go back into the call stack and sort the longer arrays.
That all makes sense now, but it was very difficult to come up with, and we needed help from one of the fellows! Something that is useful for me, and some other students, is adding a debugger to recursive calls so you can see what exactly is being called. Aria suggested this website as well!
The day wasn't over after that! Honestly, I think that time is an illusion. I don't understand how it's only been four days in the program.
After our sorting algorithm workshop, we learned about Conway's Game of Life. I had played it and learned about it before, but I've always been too nervous to try to recreate it myself.
We got started, but we have time to finish on Friday. So far, we created a function that takes an iterator function and applies it to all of the playable elements, and created a random reset function. We also styled the page. This is definitely my favorite workshop so far!
Funnest Fact of the Day: You can have two functions that have the same O(N) notation but differing run-times, because they both scale at the same rate. That's not a fact or anything, I just thought it was interesting to think about.