Joe's CSUMB Computer Science Blog

This week in class, I learned about heaps, AVL trees, and 2-3 trees. For each of these trees, I focused on better understanding the algorithms needed to insert values, delete values, and search for values. I found that even when I studied materials provided in class this week, these concepts were more difficult to understand than the concepts from previous weeks. What helped me the most in retaining any of the material covered this week was the programming assignment.  Actually applying what I learned from pseudocode in the text book to creating functions helped better my understanding of how these algorithms work. Since our programming assignment focused on heaps, I have a better understanding of heaps work compared to the other trees discussed. When I have the chance, I will try to implement my own AVL tree and 2-3 tree data structures to help myself in the future.

This week I developed a better understanding about how quick-sort algorithms can out perform merge-sort algorithms. Previously, I thought that since quick sort's worst case is O(n2) and that merge sort's worst is O(n log n), merge-sort would always be more practical for sorting. I have learned though that the worst input cases for quick-sort, such as an already sorted array or using the min or max element as a pivot, are not common. So by only comparing the results from the average/best cases, both merge-sort and quick-sort both yield O(n log n) time complexities. According to the text book, the efficiency of the innermost loop of the quick-sort algorithm is what allows it to perform more efficiently than merge sort algorithm in most situations. I have learned from additional online resources that other factors such as memory allow quick sorting to occur faster than merge sorting since quick-sort sorts arrays in place.