Week 11: Sorting and Efficiency

This week's assigned topic is about sorting and their efficiency and performance. To start off this post: How do we measure the efficiency of a sorting algorithm?

From what I learned, in order to measure the efficiency of a sorting algorithm, we need analyze the running time (or the number of steps) it takes for the algorithm to sort an input relative to the input's size. We do not measure the actual speed or amount of time it takes, as this can vary greatly for different computers, and instead we use Big Oh notation. This allows us to describe the performance of an algorithm in terms of the input size and allows us to know how the algorithm's performance changes as the input size changes.

There are many different complexities for Big Oh notation which can range from constant time O(1), to linear O(n), to quadratic O(n^2), to exponential O(2^n), or even factorial O(n!). In order to find the complexity for different sorting algorithm, we have to consider the number of comparisons, swaps, insertions, splits, etc. that the sorting algorithm performs on the list of elements relative to its size.

For sorting algorithms, we learned that a sort can have varying running times for the best, average and worst cases of the sort. For example, an insertion sort can have a linear running time O(n) in the best case, when used on an input that is already sorted, however it will have a quadratic running time O(n^2) in the worst case, when used on an input that is sorted in reverse.

In this course, we mostly focused on the worst case running times for sorts because this gives us an upper bound to the performance of a sorting algorithm and also allows us to compare sorting algorithms to one another.

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

Week 5: Scopes and Recursion

For this week, I will be writing about what I learned during this week's lectures and labs: scope and more recursion.

During lectures, our professor gave us hints and tips for the assignment given to us, which involves the Towers of Hanoi. It really helped me and I'm sure others to find a starting point for the assignment. I haven't quite finished the assignment yet and so, I will save it for next week's post.

Another interesting topic which was covered during the lectures was scopes and namespaces. This is the first time I had ever heard of the terms and the examples given in class helped me greatly in understanding what local, nonlocal, and global scopes are, how python searches for similar variable names within a program, and also how python searches for similar methods within different classes and subclasses.

Finally onto the last topic, recursion. Again. During this week's lab, my partner and I worked through several exercises which involved recursion and we had a little trouble with coding the searchLists program. At first we tried recursively searching through every element in the list and nested lists and checking whether it was the number we wanted. The program worked, however we knew this was an inefficient method. What helped us find a better method was to try and trace the problem on paper. This allowed us to find the base case as well as modify the code, which reduced the amount of lines and worked more efficiently.

Week 4: Exceptions, Unit Tests, and Recursion

Hello again! This week on I will be writing about my experiences this past week, learning about and implementing exceptions, unit tests and recursion.

I never really understood why exceptions were important. During lectures when I first learned about them, they just seemed like empty classes in Python that did nothing. However, during the exercise I found out that they can be used for some exceptional situations. The exercise was simple for me and I finished it quickly, however it made me realize that exceptions, in addition with a try block, can be used to stop your program from causing errors and run normally. Additionally, I figured this can be useful when debugging your code to fix the bugs and errors in your program 

Moving onto unit tests, last Tuesday, I had a lab which involved the making a Vehicle class and using unit tests to test the code. At first, my partner and I found it difficult to implement a unit test with a variety of test cases. What we found helped us were looking at previous week's lectures and documentation for unit test as well as brainstorming test cases.

Finally onto the last topic,  recursion. This past week, we learned about recursion through the use of nested lists and a class called Turtle. I thought that the Turtle class was really cool because it helped me (and I'm sure many others) visually see how recursion works which helped further my understanding of recursion and the levels of recursion.