Joe's CSUMB Computer Science Blog

Service Learning Summary During my time with Nyamboyo Technical School (NTS) I worked on the new attendance and calendar applications for NTS admin to use on their website. I enjoyed the entire process from developing my ideas to testing new features I created. What I found meaningful about this experience was seeing how the apps I worked on would improve the work process for NTS admin. I am glad I could contribute to NTS and I hope that these features may allow NTS to shift their focus into other areas that support students. There were some challenges though in the beginning like familiarizing myself with the code base and learning about new frameworks and libraries. Thankfully, our lead developer afforded us the time at the beginning of the term to review and study anything we needed so we could start working on once we were confident. Overcoming these challenges in the beginning was rewarding and contributed to the overall positive experience I had with NTS. If I could offer any adv...

The topic I focused on the most this week was dynamic programming. I have not used this technique to solve coding problems yet but I have used a dynamic approach to solve written problems on quizzes. Throughout quizzes in this class, I have written out the pseudocode for a given problem to calculate the output by hand. In some instances, it is time consuming to draw out every operation of a function especially for a recursive function. Instead of drawing out every iteration of the recursive function, I would plug in the return value of the function if I had calculated it already for a given input. The idea of solving problems with the values of sub problems was a main focus of the dynamic programming lecture material. This approach to problem solving was applied to the coin board problem, coin row problem, and finding the nth number in the fibonacci sequence.

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. 

 This week, I continued to learn about the divide and conquer approach to solving problems. The class lessons used merge sorting as example to demonstrate how divide and conquer algorithms can be implemented. An unsorted array is repeatedly split in half into sub arrays until the sub arrays are one element in size. At this point, the sub arrays are considered to be sorted and can be merged back together in a sorted order. This is repeated until all the sorted sub arrays are merged in order. Using the master theorem, I was shown how this sorting method results in n*log n order of growth. In community college, I had to show how many operations had to occur for sorting an array of n size by counting operations at each step of the algorithm. Learning how to apply the master theorem to merge sorting has made understanding time complexities much simpler.

 My studies this week revolved around different search algorithms. The exhaustive search algorithm for graphs is fairly straightforward as it involves finding solutions by testing all possible combinations of paths. Although simple in concept, this approach can be extremely inefficient since the number of possible paths grows rapidly as the number of nodes in a graph increases. I also learned how to perform a DFS to traverse a graph, which finds the furthest unvisited node before back tracking. This strategy adds nodes to a stack and ensures the deepest nodes are visited first. The material this week also covered performing BFS, which involves exploring the nodes adjacent to the current node first. This strategy uses a queue to ensure the closest nodes are visited first.