Week 10: Sorts and Regular Expressions

Another week has gone by and we are almost at the end of the course. For this week, I will write about the two new types of sorting algorithms we learned, and the second assignment, which involved regular expressions.

The two new sorting algorithms we learned during lecture this week were called the Quick Sort and the Merge Sort. The Quick Sort involves repeatedly choosing a pivot and sorting elements in relation to that pivot. While on the other hand, the Merge Sort involves splitting the list in half, recursively Merge Sorting both of the lists and finally combining (merging) the two halves together.

We also learned about the performance and efficiency of each of the algorithms which involved calculations like the number of steps  to choose a pivot, the number of comparisons, as well as the number of times to split a list in half, etc.

Moving onto the second assignment, it involved Regular Expressions, which are similar to Trees and Recursion. My partners and I found the assignment to be not too difficult because of the various hints and tips given in the handout as well as in class. We had the most hardest time with the is_regex() and match_regex() functions.

My advice for this would be to really think about the base case(s) and recursive steps, and tracing the output. If you do not really understand how recursion works, then you should practice with simpler recursive problems which will help you gain a better understanding.

Week 9: Binary Search Tree and Running Time Analysis

Hello! Another week for the course blog and some new topics for this week, which include: Binary Search Trees and Running Time Analysis.

This week in lectures, we learned about Binary Search Trees, which are a special type of Tree with the condition that the data in the left sub-tree is less than the data at the root which is less than the data in the right sub-tree. We also learned about was running time analysis, which is how we measure the performance and efficiency of an algorithm by its input size, in order to compare it to others.

The BST data structure allows searches to be more quick and efficient compared to a regular Tree and this is because of how the data is organized. Similar to the Binary Search algorithm, which we learned earlier in the year, the amount steps required in the worst case for a Tree/List would be to search the entire Tree/List, however with the BST/Binary Search algorithm, it is much more efficient and would reduce the number of steps to log(n) where n is the number of elements in the Tree/List.

For this week's lab, it was about BST and my partner and I worked on the method count_less which takes a Tree and value and returns the number of nodes in the Tree that are less than the given value. At first we confused about the different object types and methods. However we were able to finish once we were able to understand the interaction between the BST and BSTNode.

Week 8: Linked Lists

For this week, I'll be writing about Linked Lists and part one of the second assignment.

During lectures this week, we learned about Linked Lists, which are similar to Lists and Trees. A Linked List can be thought of as a Tree with an arity of one, which means each node can only have a child node. Also a Linked List contains a value and a reference to another Linked List.

For the lab exercise, my partner and I got to experiment and write code for creating a Linked List class. We got write several methods, such as setting, deleting and inserting an item into the list. We found it difficult however, overall this lab combined with the previous concepts of recursion were really useful and helped me to understand how Linked Lists work.

Also during the week, part one of the second assignment was due. My partners and I worked on it and found that the code which was used for the Regex classes was very similar in structure to code used for the Tree class - that is a Regex contains a value/symbol and has children nodes which can be other Regexes. We also incorporated class hierarchy and used inherited methods in order to reduce duplicate code.

Week 7: Recursion

This week's assigned topic is recursion! To start off: what is recursion?

From my understanding, recursion is a using method, which calls itself, to solve a particular problem by dividing the problem into smaller, simpler pieces. A recursive method includes a base case, which is the most simplest case of the problem, and the recursive part, which takes the input and calls itself on a smaller piece of the input.

Recursion can be very useful for problems that can be easily divided into smaller sub problems or simpler cases. The advantages of recursion are that it would take less lines of code to write and are sometimes easier to understand and implement. 

However, recursion isn't always the best method to solve a problem because in some cases it may be possible to use explicit formulas or loops. For example, when calculating factorials, it is possible to use recursion, however it would be more efficient to use a loop. The disadvantages are that it could take more time and memory to solve certain problems, and initially understanding how the recursion works.

From my own personal experience, while working on the Towers of Anne Hoy assignment, my partners and I encountered some difficulties such as finding the best "i" to use for a certain number of cheeses, and also encountered many bugs and errors such as the max recursion depth error. What we did which helped us throughout the assignment was to trace the recursive problems on paper as well as play around with the given gui controller to figure out the simpler cases of the problem. 

In conclusion, recursion has its advantages, such as taking less lines of code to write and being simple, and disadvantages, such as taking more time and memory for certain problems, and can be useful in cases where the problem can be divided into smaller sub problems