Week 12: The End

Today marks the end of this term prior to the exams, it has been a great experience learning new topics and working with fellow classmates. Although all the topics are more or less covered for me in high school, the materials presented in this course have definitely challenged me on a highly intellectual level, especially the later topics, assignments and exercises.

I had a great pleasure of working with the professors, TAs as well as new friends made in this course. It has been fun throughout every single lab, lecture and assignment, they have all been great help in the completion of this course and I cannot wait to work with them on projects together in the future years.

It has been a rewarding semester; to start off, list comprehension and ternary if statements are one of the first things we learned, they became the most important coding methods I used in this course, and I will definitely continue to shortening my codes using these to my advantage. Furthermore, I had practice on bigger topics like recursion and tree structures, I feel a lot more comfortable with them now, in fact, I feel at ease with recursion after everything we learned this term. These knowledge will come in handy for sure for the rest of my life, and I will treasure every moment of this experience.

My next step in computer science is to get accepted into the specialist program, as this is my second year in university, I already have a computer science minor as my subject post, but I will have to apply since I really want to do more in this field. I hope I did well and will do my best on the exam to be accepted, best of luck to everyone else on the same boat.

Thank you guys for reading my SLOG, hope you all learned something new this year, and all the best moving forward.

Week 11: Sorting and Efficiency

Sorting and efficiency is the last topic that is covered in CSC148, we were able to touch on this a little bit in CSC108. However, with the introduction to recursion, we were taught two more sorts that take advantage of this for a faster run time.

The run time of O(n) is the best for most sorting algorithms in existence, although the best ones have O(nlogn) as the worst case. One important take away from the analysis of various sorts is the efficiency, or the complexity of an algorithm, specifically iterative (insertion, selection, and bubble) and recursive (quick and merge) algorithms. This shed a light in the implementation of functional software, as I saw in the lab, although the change of one iterative or recursive step has barely any impact in the running time of an algorithm, it could play a significant part in a larger-scaled project. For instance, as we see in the first three sorts we learned, they were all running at O(n²) as their average and worst case, which is really bad because as the size of the list increase, the algorithms will run quadratic times the amount of increase. Quick and merge sort are much faster in the sense that their average run time is O(nlogn), however, as we see in the class, quick sort is not exactly stable as a terribly organized list could cause it to exceed max recursion depth.

What was interesting to me and my friends are the custom sorting algorithms we were playing around with in the lab, including comb sort and cocktail sort. Their animation was really intriguing, some sorts from the left, others from the right, there are even those that sort from the sides or start at the middle.

Out of the three major sub-topics we discussed this term, big-oh was actually the topic I paid the least attention to in high school, mainly because it was at the end of the term and we did not really get in depth into it. Although we were taught shell sort, heap sort as well as quick3 sort in addition to the basic five, we were never tested or worked on them. I was not very clear why at the time but now that we learn the exact same five sorts in the first year of CS, it seems like the other three common sorts are a little more complex and I hope to learn about them more in future years.

What we did was to implement a user interface in which one could select a sorting algorithm: bubble sort, insertion sort, selection sort, merge sort and quick sort. It was a big give away at the time since the codes for these common types of sorts are all over the internet, and obviously I did not pay much attention to the code itself. But we were instructed to show display for sorting on 10 integers as well as time the sorting process for 10000 randomly generated integers. Even though I did not take away much from this particular project back then, it definitely established a base for me in the field of sorting and efficiency.

Week 10: Assignment 2 Full Report

It is almost the end of the term, with the last assignment finished, and the second midterm approaching. This week I’ll be talking about assignment 2, discussing the choices I made and why.

I have been so focused on the topic of tree structures these few weeks that I haven’t the time to really talk about the assignment. So I’ll start from part one, overall my design is very similar to the instructor’s version but with some differences. First of all, I did not have a class for leaf nodes, I was leaning toward this idea toward the end of my design but decided against it as I would just be using my RegexTree with an empty list as children to denote this anyway, I also clearly stated that in my precondition which I felt was enough. Another thing I found interesting in the instructor’s version of design is the inclusion of unary and binary trees as separate classes, this thought actually hit me during the designing process, but after actually coding it, I just see a large part of the code not being used. This can be seen especially from the unary tree, where the only thing it is affecting is star tree, so I might as well initialize star tree from regex tree. The __repr__ functions are also completely useless as it is never called because you have specialized version of these unary and binary trees. I had a similar case for binary tree as I was able to initialize both dot tree and bar tree with RegexTree as the parent class without the need for an intermediate class. Overall I just felt like my way was more efficient and avoided duplicate code.

Part two of the assignment was very tricky at the beginning; it took forever to draw the tree out in the attempt to derive an algorithm for is_regex. I had the base case and star symbol case already in mind, the only thing left was the dot and bar cases, where I had to find the split point; after about 4 hours of looking for patterns, I found out that if the regular expression begins with ‘(‘ and ends with ‘)’, then after removing these parenthesis, the splitting point would have balanced parenthesis on both sides, what I meant by this is that the left side should have equal amount of left and right parenthesis, same goes for the right side, so I just used the count method in string to find the splitting point, and the rest was easy. After finishing is_regex, permutation and building the tree was a breeze, after all, they are all using the same idea. The last part of the assignment is regex_match, which I felt was the most difficult part, especially the dot and star cases, where the string can be broken down into many different cases and you have to check each one of the cases to find a correct one, if not, return False. What I find really tricky at this part is actually defining the right base case, because once you go into recursion, you could have ambiguous cases where the string can be split into a couple different ways and only one is correct. I kept on getting the wrong results until I see that the base case is not that length of string is one, but rather the whole string matches the tree. What regex_match really did for me is allow me to think of many obscure test cases, where each time I think of something completely out of the box, more likely than not I will find a small error in my code, and I was able to make change to it. This not only helped me but also my friends as they said my test cases helped them find errors in their code as well.

On a last note, it seems that every time I am confident about tree structure, a new one is introduced, just like this week’s lab. Each lab gave us a tree structure but introduced in such a different manner that it really requires a lot of thinking for every single one of them, this makes this topic a very difficult thing to master, and one that I will be focusing on the most in response to the upcoming midterm.

Week 9: Binary Search Tree and Wrapper Functions

It is a busy time right now for us in CSC148, with exercise three and assignment two due soon, as well as the second midterm coming up. Luckily, I was able to race past the first two recently, added the finishing touch to assignment two part two just this afternoon, giving me a cushion to review the various types of tree structure.

First of all I would like to note about this week’s lab session, which had the tedious tasks of creating the same function in four different ways. Although stressful at time, it was a great learning experience. After nine weeks in the course, I am very comfortable with thinking and programming recursively, so the first three parts was a breeze once I have gotten the right idea. For the last part, me and my partner Brian were stuck on it for quite a while, when we realized that we only had 10 minutes left in the lab, he hinted me with an ingenious idea that can be considered as thinking well outside the box. The brief solution can be seen from Brian’s slog here: http://my148slog.blogspot.ca/2014/03/brians-csc148-slog-9.html

This lab also gave us an opportunity to practice with these wrapper functions. I am still not completely comfortable with the concept of a wrapper function at the moment, but I definitely have a greater understanding of it. A fellow classmate also mentioned this on his slog (http://compscislog.wordpress.com/) where he noted that it helps to make calls less prone to error. This I noticed in the lab when calling from _BSTNode and _BSTNone which was convenient at times with self.left and self.right in these wrapper functions but not in the original BST module.

I was able to finish the assignment 2 part 2 today after a considerable amount of theory-crafting along with trial and error. Piazza was very useful in the completion of this as well as other students were able to give me important hints in the breaking up of a function into smaller problems. It was definitely a great challenge, even though I felt more at ease with this assignment than the first, possibly just because I am more adapt at solving these recursive problems now. Anyway, this is a great week for me in terms of accomplishment; I’ll be back next week with a full report on assignment two.

Week 8: Trees, Recursively Defined Structures, and more

After a busy weekend, I finally have the time to sit down and collect my thought for this week. I would like to this opportunity to talk about trees and linked lists, including the assignment, labs and exercise relating to this topic.

Last week’s tutorial on the implementation of a Queue class for LinkedList was disappointing to say the least, with almost everyone in my section dumbfounded at the end with little to nothing accomplished due to the confusion in the instruction. Since then, I have learned a lot more about tree structure and the implementation of these structures in different forms. This week’s lab was a continuation of the last, where we have to write functions for LinkedList class. As I discussed in my earlier posts, recursion was very tricky to handle and implement; after much practice in this course and theory computation, I find recursion to be second nature now, where I would be able to think in terms of recursion pretty quickly given a problem. Some harder ones take a lot longer to think through, but once work through the recursive steps; I find it really easy to put that into python code. This is especially the case in the lab, where I was able to complete all the functions right after another, including copy and filter, which were all recursively defined.

Exercise 3 was very interesting to do as well, it was hard to visualize at first, but once figure out the solution, I was easily able to write out the recursively defined functions. One thing I want to make a note to myself after doing exercise 3 is to be careful in which order I write out my list comprehension. I now make sure to put the base case first because it would produce an error to do something to base case. What I mean is something like this:

[] if this = [] else do_this(this[0])      instead of      do_this(this[0]) if this != [] else []

If I were to put it the other way around, as I did initially in the exercise, it would produce mostly an index error was it is evaluated from left to right. I had a lot more problem in part b, as I wanted both the depth and sum of the path, but it was hard to find max of both and compare. I found it easier to use the max function on a tuple as it compares the first element first, then the second, so the result will be the highest sum of those trees with deepest depth.

I also started part 2 of assignment 2 this week, where I am trying to determine whether a given string is a valid regex. It is very challenging at the moment as I have not yet derived an algorithm to parse a regex, I am pretty sure I will figure it out soon and talk more about this next week.

Furthermore, I was going through some slogs posted by other students, Brian’s slog (http://my148slog.blogspot.ca/2014/03/brians-csc148-slog-8_5.html) this week talks about his challenges in this course which interest me, as I have faced similar problems in the past and still do to this day to a certain extend. I would say I have gotten pretty good at recursion and comprehension lately; this is mainly due to the fact that after given an assignment, if a problem can be solved using recursion and/or list comprehension, I would do that or at least try my hardest to do it that particular way instead of an “easier” method, it really helped me understand a particular method of programming and I hope this tip can be helpful to others as well. Overall, the only problem with computer science at the moment for me is the theory(CSC240), which is what I’ll be focusing on for now, with more understanding in the theory of computation, I’m sure I’ll be more comfortable in this course as well.