week 10

In this week's lecture, professor first talked about something about the assignment2. He gave some hints for the four functions we should write in the assignment. Four function is is_regex(s), all_regex_permutations(s), regex_match(r, s) and bulit_regex_tree(r). After taking about assignment2, professor some sort method which is different from the sort in CSC108. In CSC108, I have learned Bubble sort, selection sort and insertion sort. Now, professor introduce a new sort, which is quick sort. The idea of quick sort is choosing a pivot, then decide where the pivot goes with respect to the rest of the list, repeat on the partitions. After quick sort, I learned the merge sort. The idea of merge sort is dividing the list in half, then merge the sorted results.
This week's lab is very interesting. In the lab, we only need to complete two functions. One is inorder traversal and the longest path. At first, I use a intermediate list to solve the problem. But TA told us that we cannot use the intermediate list. Then this lab becomes challenges for me. In the end, we wrote a very long function to finish this lab.
In short, I have learned two sort method in this week.