Sorting and Efficiency

    Sorting is an important topic in computer science that deals with sorting elements in an array so that they are in some particular order. For example, we could sort an array containing numbers by their sizes, smallest on the left and largest on the right. In order to achieve this, we need to follow some kind of a plan, an algorithm. Depending on the algorithm, the amount of steps we have to take would differ, especially when the number of elements in an array are really large. 

    In order to compare the steps that an algorithm takes, the big-Oh notation is used, which tells us the upper bound of how the number of steps grows as the number elements, n, are increasing. This is expressed as a mathematical function. Because the notation only concerns with how the steps grows, we do not have to care about the constant of the function.

    There are some important sorting algorithms thought for educational purposes. The bubble sort is O(n^2) because in the worst case, for each pass, we need to compare the n - k times, for some integer k greater than 0, which are done n - 1 times. The selection sort, which is a bit different from the Bubble Sort in terms of how the comparison done, the way we iterate through the array is similar. So, the amount of comparison is also similar and it is O(n^2). The same goes for the insertion sort. The merge sort, however, is different and is O(n lg n). This algorithm uses recursion and like the binary search, it divides the an array into halves and then the comparison is done. The comparison takes n times and the division takes lg n times. 

Week 10: Sorting Algorithms and Assignment 2

    More talk about performance, efficiency, and sorting algorithms were present in this week's lectures. This time, new O(n lg n) algorithms were introduced: the quick sort and merge sort. The quick sort, uses a pivot and partitions the array into two, one less than the pivot and one greater. This process is done recursively to the partitions and eventually, the array becomes sorted. The merge sort first splits an array so that the new arrays only has one of each elements. Then a pair of the new arrays are merged while sorted. This process is repeated until the partitions of the arrays become one again, which would be sorted.

    The labs are becoming not so easy these days. I now am worried the upcoming test would be quite challenging, especially since only 50 minutes are allowed to write it. Part 2 of the Assignment was due on Thursday. The functions, is_regex, all_regex_permutations, and build_regex_tree, were pretty straight forward I though and hopefully, my partner and I coded correctly. However, regex_match was difficult. The algorithm for matching star trees was the hardest. Although we created what seems to be a possible algorithm, our code did not work properly for matching them so perhaps the idea was wrong or maybe its just that we did not implement them correctly. I hope all goes okay for this assignment, which was not easy.

Week 9: Performance and Notations

    This week, the lecture covered materials about measuring performance of an algorithm. Usually, the measurement depends on the size of an input, especially when talking about search algorithms. So, computer scientists classify an algorithm depending on how many "steps" it takes when the input, n, is large. The big-O notation tells us at most how long an algorithm takes, i.e. O(n), O(log n), O(n^2), etc. The slower the equation inside O grows, the better the algorithm is compared to another one that grows faster. Binary Search algorithm's complexity is O(log n), which is apparently is very good. When talking about complexity, it is assumed that log has a base of 2.

    The exercises were pretty challenging for me. This time, I had to think about the problem before I could even start to code. Part B gave me the most trouble. I am not too certain if my algorithm is correct. It has passed my test cases but I may have missed some case that would cause a fault. If my program turn out to be fine, then I would feel relieved and be confident when approaching similar type of problems.

Week 8: Linked Lists and Assignment

    From week 7 to this week, I learned about linked lists. This could be seen as a unary tree, meaning it has a branching factor of one. Basically, a node, which contains a value,  "points" to another node. We can also view linked lists differently and call the value "head" and every else that is linked to it as "rest". Danny also showed two different pictorial representation of linked lists.

    The lab was somewhat confusing to me. I first thought I had done the labs correctly but when he TA showed his solution, it was somewhat different. To be honest, I am still very skeptical of his solution as well as mine. I should spend extra time to do the lab again and really try to understand it.

    My partner and I were very confused at the assignment. We thought there was no to make multiple classes to represent regex; we thought just making a class of tree was enough, since every such as bar, star, dot, and alphabets are just trees. However, the handout seemed to suggest otherwise, so we created classes are each of the operators and alphabet which inherited from a more general class, Regex.

Recursion: A Cool Concept

    This term, I was introduced to recursion: an action where a function calls on itself. Every recursive function needs at least one base case. It needs to return something or else, the function will be calling on itself forever, causing runtime error. With the use of recursion, one can take a hard task which takes lots of repetition, and solve it quite easily.

   When I first saw a recursive function, I was very interested. I had no idea this was possible and that a computer could recognize it. Although very exciting, some complicated recursive functions are hard to identify its behaviour. Also, when given a problem, I find noticing if the problem is easily solvable by using recursion, challenging. I hope to overcome this challenge by going online and searching for problems which require a recursive solution and creating function on my own. As with many things, I think practice makes perfect. That being said, by doing the assignment, although no marks were given yet, I feel much more comfortable with writing a recursive function. 

    One question arises, however, when I use recursion. Although I am not quite sure, when a function uses a lot of recursion, there seems to be a lot of usage of memory. For example, during the assignment, I have tested Tour.py with 999 cheeses and felt that perhaps I was using a large portion of my RAM, if not all. So, perhaps when given a problem, I should first find if there is an easy solution not requiring a recursion. If there is no easy solution then I should use a recursive solution. I feel using unnecessary recursive calls is not efficient.

Week 6: Trees and Finishing Up the Assignment

    The course material cover for week 6 was about a new type of data structure: binary trees. From what I remember, I have seen this during last week's lab. Binary trees are consisted of nodes and edges. When there are many nodes, those nodes become special. Each node can be seen as a root and some of them have children (maximum of two) and each child could also have children too. A node with no children is called a leaf. Some more definitions were covered in class.

    During the lectures, I was shown two implementations of binary trees. One used nested list, just like from the past lab. the 0-th element in the list is the node and the next two were the children. If there were no children, NoneType was in those places, otherwise it was another list. The second was basically the same except it was just a tree, meaning there could be any number of children, and we created trees objects.

    Because my partner and I were tired from mid-terms of other classes, we did not try much on the lab exercises. However, I though this weeks lab was quite easy. We had not much of a problem changing list comprehension to creating lists in the old/traditional way.

Week 5: Start of the First Assignment

    This week, Danny showed the class his code for solving the original Tower of Hanoi problem. After seeing this, even though I did not start on the assignment, I had somewhat of an idea what to do for the assignment. Later this week, I started on the assignment and was able to pretty much finish the whole thing. However, knowing that I had a few mid-term exams coming up next week, I did not take much time making sure I did everything perfectly, without any bugs. I guess I have to do the nasty works later.

    Also in the lecture, scopes and namespaces were introduced. To be honest, I was late for class and missed most of the talks. The lecture slides did not really help me because there does not seem to have much explanations. Over the weekends, or maybe during the reading week, I should definitely find some online materials to read and study.

    The lab was focused on recursion. My partner and I had to traced some codes given certain inputs. Also, we had to write a recursive function, having to do with nested lists. The function that we made failed the test case that we created and a lot of time was spent trying to find what was wrong. We knew that our idea/approach was correct but something must have been faulty because computers don't lie. It turns out we had to put 'return' on the recursive call. Other than that, this week was an easy going one.