Finding the root of a RegexTree was important, since I used the algorithm for locating the root of a RegexTree 3 times in my regex_functions module. The root is either a dot or a bar (assuming the tree is not a leaf or a star tree). Locating the root is useful because it allows you to accurately split the tree into a left and right component. This allows you to use recursion on the left subtree and right subtree of the given root.
Regex match was also somewhat difficult. For star trees, you have to split the string s as:
s = s1 + s2 + ... + sk and check that all parts of s match the RegexTree r. However, there are so many ways to split a given string that this task seems almost impossible.
Thanks to Danny Heap's week 10 slides, an equivalent way to match star trees is to use the following algorithm: split s = s1 + s2. Then check that both s1 matches r, and s2 matches r*. s2 has to be a shorter string than the original string s (or else you will have infinitely many recursive calls). The base case here is the empty string, which should return True if the string s is empty. Now, you only have to check '2' possible ways to split the string s.
In other news, we have been looking at various sorting algorithms in lectures recently. Specifically, we have talked a bit about merge sort and quick sort. These are 'divide and conquer' algorithms since they involve dividing a list into half on each pass, making them more efficient than the sorting methods we learned in CSC108, like bubble sort and insertion sort.
One thing that surprises me is how many sorting algorithms actually exist. It is weird to think that there actually exist around 20+ ways to sort things...
http://en.wikipedia.org/wiki/Sorting_algorithm
Thanks to Danny Heap's week 10 slides, an equivalent way to match star trees is to use the following algorithm: split s = s1 + s2. Then check that both s1 matches r, and s2 matches r*. s2 has to be a shorter string than the original string s (or else you will have infinitely many recursive calls). The base case here is the empty string, which should return True if the string s is empty. Now, you only have to check '2' possible ways to split the string s.
In other news, we have been looking at various sorting algorithms in lectures recently. Specifically, we have talked a bit about merge sort and quick sort. These are 'divide and conquer' algorithms since they involve dividing a list into half on each pass, making them more efficient than the sorting methods we learned in CSC108, like bubble sort and insertion sort.
One thing that surprises me is how many sorting algorithms actually exist. It is weird to think that there actually exist around 20+ ways to sort things...
http://en.wikipedia.org/wiki/Sorting_algorithm
No comments:
Post a Comment