Reviewing for Mid-Term 2 (Week of Nov. 11th)

There was no class on Monday and Tuesday, so I spent most of the long weekend studying for the Mid-Term on Wednesday.  First, I made notes based on the lecture slides and the extra-reading posted on the CSC148 website. I believed during the process of making notes, I could memorize the material better. It would also be easier to review before exam because I can just focus on studying the notes instead of going through all the readings and example posted.  I specifically spent most time on the “Binary Search Tree” section, because I found the insert and delete method confusing. Each of them had four cases (if/elif/else clause), though very similar at first glance, they were actually different. I also went through the terminologies used in recursive tree structure, as well as linked structure.

After finishing my notes, I started to look at the labs documents. I tried to re-do the lab question starting from lab 06. Of course I took less time when re-doing the lab question, because I already had the ideas on how to implement each function during lab time. However, after finishing the lab questions, I compared the two codes: they were very similar, but the first one had some redundant lines, which made the code less efficient.  Afterwards, I did the same thing to the exercise, starting from exercise 4. I realized I spent significantly less time completing the exercise and the implementation was more efficient.

On Monday night, I finished all of the labs and exercise questions, so I didn’t know what to do next. I started making up question related to the content. For example, in lab08, we had to present a recursive tree in inorder traversal, in linked list structure. I also tried to do preorder traversal and postorder traversal on my own, and it wasn’t too hard. I also tried to create a function that does selection sort on a linked list structure (assuming the data that the node holds is float). The selection sort method was a bit harder, because I had to write a few helper methods such as a function that find the node that holds the minimum value in a linked list. Nevertheless, when I finished coding, I felt very accomplished.

Running Time Analysis (Week of Nov. 4th)

This week, we learned more about running time analysis, specifically analyzing three different sorting methods. Again, since I do not have a solid background in computer programming, I only knew the concept behind bubble sort. I really appreciate that Professor Heap used cups with different height as visualizer for how each sorting method work. I am pretty sure if I were to look at the code alone; it would take me hours to understand the idea of each sorting method and how it works. The result from the race among the different sorts, including the count sort and the python built-in sort, is also really interesting. For instance, even though both quick sort and merge sort are O(n log n), one still out speed another by a constant.

Speaking of which, I have trouble understand Big-Oh Analysis. When going through the 3 sorting methods in class, it took me a while to understand why each sort corresponds to each function. Selection sort is O(n^2) because during the i^th iteration, the program has to run through (n – i) item in the list. So adding all iteration, selection sort would take n + (n – 1) + (n – 2) + ……. + 2 + 1 number of steps. By Gauss formula, the amount of steps taken is n(n+1)(0.5). Thus selection sort is O(n^2). Similarly, merge sort is O(n log n) because the merge_sort function split the list into two smaller list (ie. It is O(log n)), and the merge function has to go through each item in list 1 and list 2, in which there are n items in list 1 list 2 combined (ie. It is O(n)). Combining the two functions, we will have O(n log n). However, quick sort is the one that I have the most problem. I understand the “log n” part, because quick sort uses the divide and conquer method. Nevertheless, I do not understand where the “n” comes from. I should probably read the background readings again and see if there is any explanation. If I still do not understand, I will probably do some research through Google, and hopefully there will be an explanation on why quick sort is O(n log n).

More on Binary Tree (Week of Oct.28th)

This week, we studied a more advance binary tree structure: the binary search tree. I believe the binary search tree is more efficient when inserting and deleting nodes, just as binary search is more efficient than linear search. In addition, we also learned about running time analysis. I really appreciate how Professor Danny Heap decided to go through the running time analysis section now, because in CSC165, Professor Tom Fairgrieve is also teaching us how to analysis the efficiency of a program by checking the average number of steps, the maximum number of steps (worst case), as well as the minimum number of steps (best case). I found it easier to understand the concept of running time analysis because both professors are teaching closely related material, and I am able to grasp the idea behind better.

As for assignment 2, I found it shorter compare to assignment 1. It also takes less understanding of the program when coding. For instance, in assignment 1, I have to first understand what each class or method does, then proceed to coding the class or method. I remember I took a long time to understand the "add" method in assignment 1 because I did not know what it is supposed to do. However in assignment 2, the instructions are pretty clear and the programming part wasn't that hard. Nevertheless, I did have trouble with matching a string with a regular expression that contains the "*". As stated in the assignment 2 guidelines, "A regex of the form r + '*' matches string s if.....s has the form s1 + s2 +......+ sk where k > 0 and r matches every si". I had problem determining where to cut the string s such that each components will match the regular expression. My friend and I are stilling working on regex_match star node part. Hopefully we will manage to figure it out!

Mid-Term Review (Week of Oct.21st)

We finally got our mid-term back! Overall, I did pretty well on the mid-term, but I cannot believe I misread the first question and did max of the tuple instead of min. I only got the part (a) and (b) right in the first question. For the second question, we are supposed to write a function that join string in list (potentially nested) together. I did question 2 in the last 10 minutes of the test, so instead of writing one single function, I first wrote a helper function that flattens a nested list, then a function that joins a (normal) list together. However, I did try to do question 2 at home, without writing any helper method. Even though it took me more than 10 minutes, I am glad that it worked. For question 3, we are supposed to write two methods for a class: function_append: a function that returns a copy of the list with an item appended, and function_sort: a function that returns a copy of the list, sorted. At first, I just create a copy of the list and finished the rest of the definition. However, I noticed that the two functions are supposed to return an instance of FunctionalList. So I rewrote the code to return a FunctionalList. As for part (b), I forgot to include the empty case into the test case. Consequently, I got couple marks off on part (b). Overall, I think I did pretty well in this mid-term, but it could have been better.

As for class, this week we learned about linked structure. We used linked list to implement stack ADT and we also created a tree using a node class and a tree class. However, I still find the concept behind linked structure confusing, especially when you have to insert or delete a node from the structure. For instance, during lab, it took me a long time to figure out how write the method dequeue. It still takes me some time to think through how "self.top" and "self.last" change when a node is added or deleted from the linked structure. However, I do find diagrams really helpful when coding for linked structure. I think I will get better at linked structure once I practice more or read more examples on linked structure.