Week 11/12: Sorting Efficiency

It started in CSC108 with Bubble Sort. A rather simple algorithm that takes a list at index i and j = i + 1. If list[i] > list[j], i is switched with j.Then compare list[i + 1] and list[j + 1]. Very similarly, we have Selection Sort, which instead makes one exchange on the largest number in the unsorted part of the list for every pass through. These are O(n^2).

Insertion Sort is O(n^2), but it keeps the sorted part at the beginning of the list. It assumes that the first number is sorted (which it is, because one number is always sorted). The next number is checked against the sorted list starting at the right, and inserted to the left once it is less than the number it is being checked against.

Then we get to CSC148 and get hard-to-read algorithms like Merge Sort and Quick Sort. Merge Sort and Quick Sort both deal recursively with lists. Merge Sort takes a list and divides it by two and then divides those by two until it has length 1 lists. They are then pieced back together. Whenever two lists are compared, they are compared at index 0. So, if one list is completely read before the other, the other can just be appended to the end of the new one because it is sorted and its number at index 0 > all the numbers in the other half of the list. Quick Sort takes a pivot point (usually random to get an average runtime of O(nlogn) and a worst case of O(n^2)). This involves a leftmark and rightmark. They are moved toward each other, sorting on the way, and once they pass each other, a split point is found. Then it recursively quick sorts the left half and right half based on the split point.

Overall, large lists become too much to handle for the first 3 sorting methods, despite Quick Sort being unstable at times.

Week 10

Well, A2 is officially over. I actually turned it in 2 hours early.
It definitely helped me understand recursion more than A1 did. Actually A1 didn't really help me at all, since I never got the recursive function to work well.

In the function is_regex, you have to recursively check a string to see if it passes as a regex or not. If it has a bar or a dot, you check that is_regex of the left side and is_regex of the right side return True. Since it's recursive, the function does all that for you, given that you have the right basecases.
I personally found regex_match to be the hardest. I had to read every single Piazza post pertaining to it and talk it out with a friend before I even vaguely understood what I had to do. Then it clicked, and the feeling I got when all the functions came together and worked is probably the reason why I'm still even in Computer Science.

I just wanted to say, A2 is a great assignment. No sarcasm intended.

Week 9

A2 part 2 is. Really. Hard. I've been staring at it for about 2 days. I drew out a few examples; from string representation to tree representation and the other way. It's easy that way, but I can't wrap my head around the recursive aspect of finding subtrees in the parenthesis of more complex regular expressions. I first thought, "I could separate the regex at indexes of certain symbols", but then I realized there could be more than one of the same type of symbol in a regex. Then I thought, "maybe I should take out all the parenthesis", and then I realized that was an even dumber idea.

I've been trying to roll with the idea of having a helper function that checks simple regexes, like (0.1) and 2*, and then the overall function is_regex() check the larger regexes using the helper function recursively. The problem is that I don't know how to separate a complex regex without completely screwing up the order of the original regex.

The forums are usually pretty helpful to me, but they haven't been quite as useful this time around. I would have included more solid code/work in my SLOG this week if I actually had some code, but I don't have any. All I have is this rant about my struggles in CSC148.

Week 8

Since A2 part 1 was extended, I had a few days to think about the code I had pretty much finished and was about to turn in before I realized I could possibly improve it. Something I realized was that I could have my subclasses inherit __repr__ if I just initialized a name and had __repr__ use the name unique to the subclass. Since part 1 is mostly about inheritance, I'm thankful for the extension. (I also completely forgot about docstrings, so there's that. . .)
There was a question/answer posted in FAQ for A2 about using __repr__ to write __eq__. It said it depended on the quality of __repr__, but I'm not sure why that would be so, since __repr__ should be giving the name of the classes in addition to their children. Am I missing something?

I was a little confused on making attributes read-only after initialization. I understand its purpose and the general idea of it, but the actual implementation of it seemed foreign. Unless I really spaced out in class, I don't remember ever seeing property(get_x, set_y). I had to copy the code Professor Heap posted from the class and play around with it until it worked with my code. Either way, I'm feeling pretty confident about A2.

Week 7 - Recursion

We've had a whole assignment and a term test on recursion, and this week's Slog topic is recursion, so here goes nothing:
Recursion is, put very simply, when a function calls itself within itself. In more detail, a recursive function has a base case and one or more else/elifs. A base case is what the function would return if the input given to it is already in the form it needs to be in or if it's already what should be returned. For example, if I wanted to find the sum of all the numbers of a list, I would need to make sure I were only adding ints or floats because I can't sum lists.
Consider:
def sum_list(L: list):
      return sum([sum_list(x) if isinstance(x, list) else x for x in L])
If I did sum_list([1, [2, [3, 4], 5]]), it would add 1, but [2, [3, 4], 5] is a list, so it would then do sum_list([2, [3, 4], 5]. It would then add 2, but [3, 4] is a list, so it would do sum_list([3, 4]) and add 3 and 4. 5 is not a list, so it would add 5 instead of calling itself again. The grand total: 15.

Apparently I don't understand recursion at all because I didn't do very well on the midterm. I'm not too worried, though, because I can't honestly say I studied enough. I put way more effort into the MAT136 exam I had on the same day, worth 3 times as much as the CSC148 test. Hopefully with the help of more assignments and labs, I'll finally wrap my head around more complicated recursive functions.

Week 6 -- February 15th

After a hectic week of scrambling to finish A1 and studying for a CSC165 midterm, Danny left us pondering the tree data structure. The writer at http://gr148slog.blogspot.ca/ described it really well -- in a way that I didn't think about, but I think it will help me in long run. He describes the roots and children as the way we drew them when we were young. We started with a base tree, and drew two branches leading out of each leaf part.

I must confess, I did not finish A1. I completed all the steps, but I just could not figure out the 4-stool move algorithm. I knew that finding "i" would be a lot harder than just integer-dividing it by 2, but I did not even understand the recursive part of it. In the end, I had a function using the 3-stool cheese function Danny wrote in class that moved the cheeses in fewer moves than the Hanoi method, but more moves than the best-known TOAH method. I realize that assignments require students to just sit and THINK. I would not say that I spent enough time thinking about the assignment in general. It was pretty interesting how everything came together, and I think it showed me how useful object-oriented programming can be on a grand scale.

All in all, I think I did pretty well for having worked alone. Note to self: look for a partner sooner.

Who actually puts cheese on stools? I couldn't even find an image of one.

Week 5 - Feb 8th: Midnight Blogging -- Recursion

The week before an assignment is always crazy. I never seem to learn my lesson. This was the first assignment for Computer Science that I have attempted without a partner, and I realize just how much "two heads are better than one" holds true.
Recursion is something we must understand at this point. It's a shame I still don't understand it. I thought I did, because seeing Danny do it in class made it seem easy. We also did it in lab, where I got a better understanding of it but I still fail to wrap my head around it all.
What I do understand is that there must be a base case -- a base case is a conditional statement that will stop a recursive function from running and causing errors.Otherwise, the function will run, calling itself within itself, and return something each time so that the function can be called again, using the returned item as a parameter. This goes until the base case is fulfilled.
What I do not understand is how a function calls itself. To me, recursive functions look like undefined variables, where they are referenced before they are defined. Perhaps I should trace functions in my free time, especially since there is an important recursive function to be written at the end of A1.

Week 4, Jan 30th

Seeing Professor Heap use an Orca doll to represent artistic turtles was something I appreciated this week in class. I also really appreciate Professor Heap in general.

After glancing at classes I will be taking in the future, I set a goal for myself: between now and the beginning of our 2014-2015 year, I will start learning Java on my own. I hope that writing (typing) this out and having at least one other person read it will be some motivation for me to act on my words. One of my greatest worries in life is that I am not good enough at anything to succeed in life. In regards to computer science, I worry that I will slowly fall behind those that remain.

Something reassuring, however, is doing the labs in tutorial with my partner. We faced the same struggles but overcame our problems by just sitting and thinking hard for a bit. Even though I know I'm not the only one with these worries, it's nice to come face-to-face with the others.

I also learned super().__init__() in tutorial this week. Even though it isn't life changing, it's always good to know little tricks to shorten code and reduce hassle. A little effort can go a long way.

Week 3: Object Oriented Programming

      Walking into class not knowing what to expect on Day 1, I prepared myself to embrace the barrage of new information I was about to face. I clearly did not pay enough attention in CSC108, because I had no idea what object-oriented programming (OOP) was.
      Now it's Week 3 and I understand that OOP is a way of programming using mainly objects/ideas represented as classes. The best analogy for a class and its attributes is a phone and its functions, the phone being a class and its functions being the attributes. OOP gives computer scientists a way to define and organize what they want in a blueprint while utilizing the built-ins of programming languages. This "blueprint" is helpful because it allows computer scientists to modify data structures more easily to accommodate the rapid progression of technology. Compared to procedural programming, OOP is advantageous because it allows us to manipulate data and its behavior at the same time.
      We also got a glimpse of recursion in one of the lessons, which is something new to me. Recursion is generally when a function is called within itself. For example, in the sum_list example in class, the sum of a list was the sum of all the nested lists; sum_list was called on the smaller lists before being called on the list as a whole. After writing so many horrendous-looking for-loops in CSC108, I was thankful for this new information.
      I did not finish the first lab assignment, but I still found it helpful because seeing someone do it and having to type the code out with my own fingers are two completely different lessons. I did not finish the efficiency section of the second lab either, although I am confident I understood the idea behind it. If I did not have to pop anything from the stack/queue, I could just move the head of the list to the next index for each iteration. That way, every object does not have to be shifted over one index. I don't feel entirely confident in my OOP abilities, but I am excited to see what sorts of problems I can solve just by writing some code.