Sorting Algorithms

Selection sort always has O(n^2) performance, quick sort has an extremely rare worst case performance of O(n^2) and usually has O(n*logn) performance, and merge sort always has O(n*logn) performance.

Merge sort will usually have efficiency comparable to quick sort, however merge sort on an average of all cases will perform better than quick sort. This is because quick sort has a rare worst case in which a terrible pivot is chosen each time the list is partitioned. In this worst case, quick sort has to check every single element in the list n times. Selection sort however will always check every element n times, even if the list is already sorted. For these reasons, selection sort is almost always less efficient than quick sort, and definitely less efficient than merge sort.

Therefor, merge sort is the best of these three options to use on large random lists.

Passing a function as an argument

In class yesterday we learned about the reduce function. This function is a bit different from others that we've learned about because it takes a function as an argument. This is new, but I don't find it as intimidating as Danny said we might feel. I think it's actually pretty cool and it makes a lot of sense to me intuitively that a function name could be used as an argument. I think the reduce method is useful and after I use it a few times I'll be used to sending it a function.

Test #2

My approach for this test is going to be different from the first. My major weakness with the first test was that I focused too much on memorizing definitions that I already had a good handle on, and not focusing on practicing. I focused too much on the page of notes.

This time I will spend more time practicing the code by writing it out on paper and then typing it out. I will redo the lab questions and exercises by hand off memory to see where I am in terms of correctness and speed and then put work into areas that I don't perform well in.

However I do need to focus on the definitions and note taking when it comes to big O notation and sorting.

Assigment #2

I got the second assignment up and working yesterday. Personally I found it much easier than the first (well I'll see when I get my mark back for it).
Most of my time spent on the assignment came from me not understanding what I should be doing or what the problem was. If I had slowed down to fully plan out what was asked and how I should approach the problem with what I was given, I would've been much easier off. For example, I spend around half an hour trying to write the regex_match method by creating a tree instead of just using the tree that was given to me. That was a very silly mistake and I should've been more focused while I worked and before I started coding.

Today I was doing lab #6 about linked lists and I created a linked list class. When searching the linked list I had created for a specific item in the list, I used a loop instead of recursion. I should've used a helper method that took two parameters: a node and the item that was being searched. The helper method would look to see if that node held the item that was being searched, and if not then the helper would be called with the next node.

My linked list was functional but not optimal, I needed to think recursively and not loopy.

Object Oriented Programming:
Object oriented programming is using code to represent entities with attributes and methods that can work with these attributes. This is important for creating data structures that can represent real life entities for solving real life problems. Another important aspect of OOP is that the objects can have different attributes based on the class they are created from. Creating different object from the class's blueprint is a major reason why OOP is used as it means that many different but similar situations can reuse the same code. All this is important for creating solutions to real world problems effectively and efficiently.

Recursion:
Recursion is the process of solving a big problem by breaking it down into smaller and smaller cases until it is the smallest case. This is very efficient in that it requires less lines of code a solution that would not use recursion. Also, it can be used to solve any size of a type of problem. Recursion is important because it is often times the only way to solve large problems without wasting large amounts of time.

Tonight my partner and I worked on the first assignment. Eventually we reached a point in which we could get the graphic display to work, however we're having some glitches with moving the cheeses. When it was assigned we were told there was a small amount of code to be written, and that the largest amount of work we had to do for it was understanding. I understand that now, considering we have some very unusual errors and it means we need to look at the code we were given in order to solve the issues. Understanding someone else's code is much harder than writing my own (even though sea slugs don't have fingers)