Redundant Programming

I cannot believe that it is already week 12! Next week is the last few days of the semester, which will be mostly review. This week in class we learned about efficient code writing and how to avoid redundant recursive programming. Basically, unnecessary recursive calls can slow down your code a lot, which will result with a very long wait before the function fully executes. The case that we looked at in lecture used automatic memoization to speed up the computer program. It stored all of its calculations in a dictionary and avoided any repetitive calls by referring to its dictionary to make sure that the code will not repeat the same recursion. This method greatly enhances code by cutting down its run time.

Lastly, next week will be my final SLOG entry. I am proud of myself for actually writing weekly on this blog page, as I can be very forgetful sometimes! 

More Talk About Algorithms!

This week’s topics are sorting algorithms and efficiency. I have already talked a bit about quick and merge sort, but I will further expand on my previous thoughts.

The first sorting algorithm we learned about is selection sort. It has an average case performance of O(n²), which can make it very inefficient while sorting very large lists. Selection sort divides the given list into two: an unsorted list and a sorted list. It begins by finding the smallest item in the unsorted list, and swaps its place with the item at the beginning of the unsorted list (the leftmost item). Then, this sorted item becomes part of the sorted list. This process continues until every item in the unsorted list is sorted and the unsorted list is empty.

Even though selection sort is more efficient than some other O(n²) algorithms such as bubble sort, it is very inefficient in terms of large lists. For large lists, some more efficient algorithms are ones that have average case performances of O(nlog₂n). Some examples are quick sort and merge sort.

If you are looking for explanations of how quick sort and merge sort work, simply scroll down to read the past blog post that I wrote called ‘Some Algorithms…’. Now, merge sort and quick sort have the same best case and average case performances of O(nlog₂n). However, merge sort’s worst case performance is O(nlog₂n), while quick sort has a worst case of O(n²). This means that in terms of efficiency, merge sort is more efficient during the worst case and is more of a consistent algorithm. 

End of semester preparations!

This week we got back the results from assignment 2. I did much better on the second assignment than on the first, even though I was not able to fully complete regex_match.

On another note, this semester is almost finished! I cannot believe that there are only two more weeks left until exams. It’s kind of scary knowing that finals are just around the corner. I have four finals this semester and I have three of them in just one week. I’m going to start planning and making notes now, so that I have plenty of time before December 10^th rolls around. I feel that one of the best ways to study for a course like computer science is to go back and re-code old exercises and labs, which is exactly what I am going to do.

Wish me luck with my studies!

Test #2!

I wrote test 2 this week and I don’t think that it went as well as the first test did. Question 3 really stumped me. I ended up writing a very lengthy code, when I’m sure it wasn’t necessary. The question asked us to write code for the function min_path that takes a BSTNode, and builds a linked list of the path from the root to the minimum element. Then, the function returns the first node in the linked list. I feel that I overthought this question and made it seem more difficult than it actually was. After I saw the posted answers to test 2 on the CSC148 website, I saw that the answer to number 3 was:

return LLNode(n.value, min_path(n.left)) if n else None

Hopefully I did better on the other two questions on the test!

Some Algorithms...

This week in lecture we learned about a few sorting algorithms. Three of the ones we learned are selection sort, quick sort and merge sort. I already learned about selection sort from CSC108, and I am very familiar with it. However, quick and merge sort were new to me. It’s interesting how many different ways there are to sort and produce the same product.

From what I learned in class, quick sort takes a value or pivot and uses this pivot  to divide the list into two separate lists. Basically, it compares each value to its pivot and either places each value into a greater than, or less than list. The pivot is sorted since it is placed between the two sub lists. Then, using recursion, quick sort will completely sort the list by picking new pivots until each value is in its proper place.

The merge sort algorithm is much different. It divides the list into several sub lists that contain only one element in each. Then, the algorithm gradually merges sub lists and sorts each new list. This step continues to happen recursively until there is one sorted list left. 

I can’t decide which of the two is faster and more efficient: merge or quick sort. I guess that it depends on the case. For example, if you have a large list, and for each new pivot in quick sort your algorithm happens to choose the smallest value, your quick sort will be vary slow. However, if your code selects the median value every time, your quick sort will be much more efficient. Since it chooses a value at random, the efficiency of your algorithm may vary.

Binary Search Trees

This week in lecture we learned about binary search trees. Basically, they are binary trees whose left sub trees have values less than the node, and whose right sub trees have values greater than the node. I think that binary search trees are more efficient than binary trees because the tree is partially sorted. For example, in exercise 6, which is due tonight, we are required to create a function max_node, which returns the node with the greatest value. Instead of creating a function that iterates through the entire binary search tree, I can simply leave out the left sub trees, since I know that they all have values less than the root. So if I had to create a function min_node that found the smallest node value, I could disregard the right sub trees, since they all have values greater than the root.

On another note, I finally finished e6! I found implementing __contains__ and max_node without recursion to be quite difficult. My original code consisted of using __str__() on the given BST, then checking if the item was in the given string. I later found out a way to write my code without recursions. However, since the Auto-marker was not running normally, I was not able to test my code as often as I normally do. Hopefully I do well!