Sorting and Efficiency

In the past week, I have learned two new sorting functions, quick sort and merge sort. The labs also refreshed my knowledge on selection sort, insertion sort, and bubble sort. Different functions have different efficiency and it's always better for the function to have a faster run time. The efficiency of a function can be represented as big-oh, such as O(lg n). In this blog, I'll be writing about selection sort and merge sort.

For selection sort, insertion sort, and bubble sort, they all have a running time of O(n^2). Selection sort compares each item in the list roughly n times to every other item in order to sort the list. The exact running time for selection_sort(n) is (0.5 n^2 + 1.5 n + 1), but we only look at the highest order, which is n^2. The reason for doing this is because as n becomes too large, the highest order of n is what matters mostly. Therefore, selection sort has a running time of O(n^2).

For merge sort, it has a running time of O(n log n). Merge sort splits the list in half repeatedly until there is only one element, then it starts merging it back together from the ground level. The process of breaking a list in half repeatedly requires a running time of log n for n items. However, this is not the only process that merge sort does. The process of merging the items back together also needs to be taken into account. For n items, it also requires a running time of n for this process. Therefore to sum it up, merge sort requires a running time of O(n log n).

By examining different sorting functions and their running time, I have gained a deeper understanding on how different coding approach can result in a faster and more efficient function.

Assignment 2 Part 2: Regex Tree

For assignment 2 part 2, we were instructed to design four functions for the RegexTree class, which includes is_regex, all_regex_permutations, regex_match, and build_regex_tree. By working through this assignment, I have gained a better understanding of the RegexTree structure and recursion. For this post, I'll be writing about is_regex which is the function I had the most difficulty with.

In the beginning, I was coding in each individual invalid regex cases one by one. Even though I was making progress but after awhile it just seem off since I had too many lines of code. It was then I went on Piazza and took the advice of a fellow student and approached the function in a different way. First of all, I developed a base case for the Leaf. After that, I used recursion to solve the next level Regex, which is the StarTree. The tricky part is to figure out how to break the string down for the function to solve itself recursively. But once I got that, the code was simple to implement. This logic and approach enabled me to solve the BarTree and DotTree in a relatively short amount of time, since the approach is really identical.

This assignment has reinforced me on the importance of planning prior to writing up a recursion function.

Weekly Summary: 3/18 - Binary Search Tree + Sorting Intro

For the past week, we went over binary search tree and briefly talked about the different types of sorting menthods. The most challenging topic that I find is the deletion of nodes from the binary search tree. Binary search tree is really efficient as it allows us to find our node through the elimination of one side of the tree by checking whether or not the desired node is bigger or smaller than the root of the tree. Thus, the challenging part for the deletion fo nodes is to maintain this attribute or functionality by taking out an exisitng node. I was able to clearly understand this topic through the lectures by considering different scenarios such as when the desired node is greater/smaller than the root. I find it really helpful to break down complex situations and tackle each subproblem individually.
For sorting, we were introduced to some basic sorting methods mentioned in CSC 108, which includes bubble sort, insertion sort, and selection sort. The sorting method is more efficient if it produces the shortest running time. Running time can vary a lot depending on the number of items or parameters being used. Therefore, it is important to figure out the relation between the running time and the number of items. Although a constatnt relation might require a longer running time than an exponential one with small number of items, but as the number of item increases, a constant relation usually requires a shorter running time.

Weekly Summary: LinkedList - 3/9

For the past few weeks, we have been learning about Linked List.
Here's a brief definition of Linked List:
 "Linked lists are made up of nodes, where each node contains a reference to the next node in the list. In addition, each node contains a unit of data called the cargo."
Linked List contains a recursive definition and you can initialize it in different ways. Through the labs, I have learned how to prepend an item to the front of a Linked List. I find it easier to understand how to initialize a Linked List by setting a "head" and "rest" which is mentioned in the earlier lecture. However, I still have difficulties in initializing a Linked List through the "wrapper" approach. I'm planning to go over the reading materials listed for Linked List to make sure I understand it before the upcoming lecture.

Weekly Summary 3/1 - Recursion

For the past few weeks, we have been doing a lot of recursion exercises in class. Recursion is a function that calls itself to solve a problem more efficiently. Although recursion is a really great skill and tool to have, it requires a really clear thought process to implement. A recursion function calls itself until it exits through a base case outlined in the function. If a base case is not implemented, the recursion function will not be able to provide a valid output.

One of the key insight that I have learned from implementing recursions is that you often have to take a leap of faith. I usually think of what the function should look like under the base case. After that, I just simply fill in the codes to describe the situation recursion should occur in. Recursion functions are usually really complex to understand so it is really important to just implement it rather than making sure everything goes right in the planning process. Once a recursion function is written out, tracing it under different test cases can shed insights to any problems that the function might have.

In Assignment 1, we were given a harder recursion problem to solve, the four stool variation of tower of Hanoi. I was having a lot of trouble tackling this function at first, since I only had experience solving the simpler recursion functions such as the nested_depth in class. Although it took me some time, but I was finally able to implement the recursion function and reduce the number of moves required in comparison to the three stool tower of Hanoi. The key takeaway for me is that it is really important to break down the problem into smaller parts and solve it from there. Although I faced a lot of difficulties regarding recursion at first, but now I feel a lot more comfortable through all the exercises presented in class and lab sessions.

CSC148 - Weekly Summary 2/17

Reading week is finally here! Before that, I was spending a lot of time on Assignment 1, the recursion tower of hanoi problem.

We were given an equation to determine the minimum number of moves for moving N number of cheeses from one stool to another. The equation was really hard to solve since there are  more than one variable. We also need to determine what the optimal value for 'i' is for different N values. I wasn't able to find a way to come up with the optimal 'i' value when the assignment is due, however I was able to finish the rest of the assignment.

My solution for the four stools method was able to significantly decrease the number of moves required in comparison to that of the three stools method. My insight was that as long as all four stools were utilized, the number of moves required should decrease. Therefore, I set "i" as (n // 2). The result was as expected and the number of moves required was drastically decreased. However, I realized that it is not the optimal solution and I'm looking forward to hear how my colleagues was able to solve it.

Overall, it was a great learning experience for me, especially from working through the problems alone.

CSC148 - Weekly Summary 2/8

Another week of computer science has gone by... here comes one more post to summarize the week!

In the lectures, we continued to learn more about recursions with the professor asking us to trace different recursions to increase our understanding. I noticed my improvements in the understanding of recursion with every exercise and lab that I had done.
In class, the professor also talked about the assignment that is due the coming week.

Although I clearly understand how the towers of hanoi recursion work in class, but I'm having trouble understanding what the assignment wants us to do. There are a lot of files with a vague instruction of the objects that we need to include under each class. I'll be utilizing Piazza more and see if I can get better at designing a program without clear cut instructions.

Hopefully I can get everything figured out before the due date!