Brian's CSC148 SLOG # 10

Hello! Welcome to my 10th SLOG post!

Has everyone been having a good week?

The winter term is slowly coming to an end and the assignments are ramping up in difficulty as we approach the end of the term. This week's lecture was crammed with new course concepts and also, Assignment 2 Part 2 is due tomorrow. Both the lecture and assignment 2 has taught me very interesting concepts and helped me think in a new way for solving new problems.

This week's SLOG focus will be on:

• Assignment 2 Part 2
• Sorting Algorithms
• and my current situation in 148

Assignment 2 Part 2

Although I cant reveal too much as it isn't due yet, I will discuss my experience with Part 2. The assignment overall was not too difficult with one exception: regex_match. I began assignment 2 on Thursday night and finished 3 of the functions: is_regex, all_regex_permutations and build_regex_tree by Saturday night. These functions were not too hard because we didn't have to worry too much about how each of StarTree, DotTree, BarTree and Leaf would affect each other.

The way I handled is_regex, was to find valid regexes within the string and recursively call is_regex while simplifying the string until it eventually returned True. If my function found a single false regex during it's recursive calls, it would immediately return False.

For all_regex_permutations, we were basically given the answer as we had permission to use a code provided on the 148 website that would return all the permutations of a string! 

and for build_regex_tree, the idea is similar to is_regex in using recursion to simplify each call further and further until we reach the final answer and return a RegexTree object.

So what made regex_match so difficult?

We had to worry about how each subclass of RegexTree would interact with each other and this was incredibly difficult for me because I couldn't figure out how to get StarTree objects to properly interact with other the other sub-classes. After two days, I had finally finished some code that returned the correct bool for most cases. However, some complex cases were returning the incorrect bool and there was even infinite recursion in another case. Unable to solve my function for all test cases, I went to office hours and recieved some hints from Danny in approaching StarTree cases and Dustin helped me figure out the why my function was infinitely recursing. At last, I put the two helpful hints together and finished my function on the third day! Well, okay.. maybe three and a half days!

This is one of those moments where once you find out what the answer is, the next time you come across it, it will only take a minute to solve. I believe this is somewhat like the beginnings of thinking like a computer scientist! Spending lots of time at office hours, coding, tracing your program with pencil and paper until you get closer and closer to the answer. I don't feel good about having needed 3.5 days to solve a single function whereas a few of my classmates managed to solve it in a day. Nonetheless, I am happy it is finished and confident as it seems to work for very complex cases!

Sorting Algorithms

Sorting algorithms are incredibly interesting as they can greatly impact the performance of a program depending on the number of items we are sorting. Generally, we have touched on a couple sorting algorithms which are: 

Insertion Sort

Selection Sort

Quick Sort

Merge Sort

Built-In Python Sort

and Customized sorting algorithms

By randomizing the items in a list, we were able to see how long it took each different sorting algorithm to sort for lists with a very small amount of items (10 items) and lists with a VERY VERY VERY large amount of items! (160,000 items!). This comparison is priceless because we are able to figure out how much longer it takes a sorting algorithm to run depending on the size of the list. I believe the most interesting thing in understanding this is that we can deduce which sorting algorithms are better for our programs depending on the number of items that our program will be dealing with.

CSC148 so far..

Lately I've been feeling more confident in using recursion as it showed in my ability to solve the functions in Assignment 2 Part 2. I also used some comprehensions in the assignment which I mentioned I was struggling with a few weeks ago. So I am definitely feeling more confident as I think I reached a higher level of understanding in CSC148. However, the remaining weeks will definitely be more of a challenge as we will need to analyze algorithm running times which I have very little experience with. Hopefully this won't be a tough concept for me to grasp but I will definitely be vocal with my friends in 148 and discuss algorithm running times to get a better handle on it. Being vocal and discussing problems with friends and professors have helped me learn so much more than I would have had I not said anything!

With that said, I think I have covered everything I wanted to this week's post.

Thanks for checking out my 10th SLOG installment and check back soon as next week's topic will be in-depth about sorting algorithms and efficiency!

See you soon!