Sorting Algorithm

“A sorting algorithm is an algorithm that puts elements of a list in a certain order” (Wikipedia). There are different sorting algorithms such as insertion, selection and bubble sort. Some of them are more efficient and some are less. The efficiency of these sorting algorithms is usually based on its runtime, but what are the elements that affect runtime? One element is the number of steps, and the other one is the length of the list that we want to sort. To calculate the number of steps we can look at the code and analyze it.in each sorting we need to go through the list in order to compare values to each other and then do the exchange if needed. If we calculate the number of steps we can have an estimation of the complexity of the algorithm and somehow the runtime. Usually we demonstrate the complexity of the algorithm by big O. using this notation we show the greatest power of the result as it has the greatest impact in the complexity.

For example for bubble sort, each pass starts with comparing the first two elements and swap them if the first one is greater than the other and then do this for each two pair until the end of the list. Then the next pass starts until the list becomes sorted. For analyzing the complexity of this algorithm we should pay attention to the number of comparisons that happen each time. As in each pass the n-1 comparisons happen, and each time we have 1 item less than the last pass, the overall steps would be the summation of (n-1) + (n-2) + (n-3) +… +1 which is ½ n² – ½ n.  As the largest power is n² we can show the complexity of this algorithm as O(n²).

Assignment 2: Regex, classes and recursion.   

For this assignment we needed to write functions that check if a string is a regex, compare two strings, and build trees. For the is_regex function we had to write the recursive code which was a good practice. The hard problem for me to write a recursive function is to write a base case. Usually, I wrote my base case wrong which lead to the program to trap in an infinite loop. A2 was a good practice for me to learn how to write a base case for a recursive function. 

Assignment 2 is about regular expression : "a sequence of characters that form a search pattern, mainly for use in pattern matching with strings" (Wikipedia). It consists two parts. In part one we are supposed to write classes and sub classes. Writing code for this part helped me to understand the inheritance concept better. Also it led to a better understanding of Trees. For part two we should write the matching part. I guess this part would be a bit tricky!

Recursion:
What is recursion? Wikipedia define recursion as “the process of repeating items in a self-similar way” but how recursion is related to a computer scientist? 

Computer scientists can use recursion when they encounter a problem that could be broken down into sub-problems and the function can call itself to solve those sub problems that will lead to solving the main problem. For example when we want to calculate the sum of nested lists, we can write a recursive function as we can break down this problem into smaller sub problems.

In writing a recursive function we should be careful not getting stuck in an infinite loop and in order to do that we need a base case. By base case we mean an input for which the function has the result without recursion. Without the base case the function will raise runtime error.

Learning recursion is a bit hard but one way to learn it better is to trace the code and write the result of each function call on paper. Thanks to our lab exercises we had this opportunity which was really helpful!

Reading week and 148 term test! How should I study for the test? There are no lecture videos like 108, so I should read over the slides and reading materials. They are helpful but I wish we had videos like last semester, they were really helpful. Besides reading the links I should go over exercises and the assignment. Do them from the scratch, find my week points and work on them. I hope I will do well on this exam!

Apparently, I should write about the assignment this week: Tower of Hanoi. This assignment is complicated and after reading the handout I was confused and a little bit stressed. But being stressful does not help with anything, so I should take the problem oriented coping strategy, calm down and try to find a way to do well on this assignment. The good point of the assignment though is that it is step by step, and it makes it easier to break down the whole assignment. So I started by reading and understanding how the starting code works and what code should I write. For each function I tried to first write the aim of the function on a piece of paper and how the function may use other objects and so on, and then I start writing the code. This was a beneficial approach. I still need to work on this assignment hope that I can write the rest of them successfully. 

Week four was all about recursion!

Recursion happens when a function calls itself to solve the sub problem. We use recursion when we have a problem that we can break it down into sub problems. One of the coolest examples was drawing using turtle. It was a recursive function and the drawing has a pattern: each time the program calls itself to draw the pattern and it happens over and over again. This example shows that when we want to solve the problem (drawing a complicated pattern) we can break it down into sub problems (drawing simpler patterns) and call it again and again.   This is the power of recursion!