Week 12

This was the last week of classes. I am so happy I survived this semester. This week in lecture we learned about the efficiency of recursive algorithms. We did a few examples in class which included search algorithms as well. We also learned about Big-O of recurrence relations and their time complexity. Then we compared a few function to check which was the better one. We also talked a bit about the final exam and how to study for it in order to get a good grade. This week we did the week 9 lab as we didn't have a lab that week because of the good Friday holiday and the week after we had our assignment 2 demo. The lab was quite easy, we had to record the time each search algorithm took with a different n and then make a chart of the data. Overall, for me, this course went really well. I am excited to study other CS courses in the future.  

Week 11

I feel recursion is one of most important topics in computer science. Week 6 we learned recursion, I also talked about it in my SLOG for that week. At that time, to me it seemed that writing recursive code was comparatively easier than tracing it. Although both of these jobs were hard for me. For test 2 when we were going to be tested for it I had to solve a lot of example problems to completely understand the topic. My main focus was recursion as I knew the rest of the topics well. After doing a number of problems and going to office hours of my professor, I finally learnt how to write and trace recursive code properly. I think office hours are an extremely advantageous thing and every student should make use of it. A few days ago when I was going through some of the SLOGs of other students, I realized that there were only a few who felt the same as I did about recursion. The labs on tree and binary tree were a great deal of help in my process of understanding recursion as they tested this concept very well. Now I can confidently say:

The rest of the topics in the course are not very complicated, one can understand them with little effort. Recursion is the only topic I felt was tricky and it was very easy to get confusing when writing recursive code especially when the base case is not straight forward. I am glad that I have finally aced the topic. Now that we have started learning about Big O, I am anticipating it to be the next difficult topic in line for me. It seems quite complicated so I hope I am able to understand it the same way as I understand recursion.

Week 10

Assignment 2 was due this week, I think my partner and I did a good job. All our methods and search algorithms were working. The program was also not taking a lot of time to run. Last week we wrote a method to delete a node from the tree, but that was an iterative approach. This week we learned how to write the same method recursively. Again, we discussed several cases and possibilities. The solution for the recursive one had way less lines of code than the iterative solution. We also started talking about the efficiency of algorithms, it seemed to be difficult but I will only be sure once we learn more about it. Since my lab is on Friday, this week the university is closed for Good Friday so I don't have my lab. Next week we are supposed to give a demo for our assignment, we have to explain our understanding of the code. I hope it goes well.

Week 9

The week we had our term test 2, I found it to be fair. Some of my class mates were saying that it was harder than the morning sections. Next week assignment 2 is due, my partner and I have been working on it since it has been posted. This assignment is harder than the previous one. We have to write functions to get the possible moves that reach to the solution for four different games. We got 95% on the previous assignment so we are hoping to do well on this one too. This weeks lecture was based on binary search trees as well, we wrote methods to insert nodes and delete from the tree. For delete, we discussed different cases and examples the we implemented the actual method. The professor explained it very well so it wasn't too hard to understand. The insert function was quite easier than delete. This weeks lab was based on also based on binary search trees. We had to implement three different functions, they were also recursive like the ones we did for our previous lab. We had to implement a method to get the values from the longest path in the tree and a method to get the values between a certain range. If one understands the structure of tree and binary search tree properly then implementation of any method is not too hard. 

Week 8

This week we learned about trees and binary trees. A binary tree is a tree which branching factor 2. Branching factor is the maximum number of children a node can have. The children of the tree are called the left and right child. The values in the left subtree are smaller than the node and the values in the right subtree are larger than the value of the node. We talked about tree traversal in lecture this week, there are three standard orders for traversal; in-order traversal, pre-order traversal and post-order traversal. This is an examples of a binary search tree.

In lecture we implemented the special methods. We also implemented two other methods one was contains which checks if the specified value exists in the tree. The other was evaluate, which evaluates the values of the tree based on the operator which is the node. We discussed the height of the tree, as the number of nodes of the tree increase the height of the tree becomes the logarithm of the number of nodes. This weeks lab was based on trees as well, we had to implement three different methods. I did all of them recursively so I didn't find them very hard to do. Next week we have our term test 2, I am kind of nervous for it. Last time I did not write the test because of the fire alarm. I hope I do well on this test.

Week 7

Recursion

Recursion is one of the main ideas of Computer Science. A common thing done when writing code is to divide the problem into smaller problems and then combine the results. It is mostly used when the problem can not be solved by a for or while loop for example, checking elements in an arbitrarily nested list. One of the exercises we did in lecture was tracing this code:

def sum_list(L):

    """ (arbitrarily nested list of int or int) -> int 

    Return the sum of all ints in L. 

    >>> sum_list([1, [2, 3], [4, 5, [6, 7], 8]]) 

    36 

    """ 

    if isinstance(L, list): 

        return sum([sum_list(x) for x in L]) 

    else: 

        return L  

In the code above, the function sum_list is calling itself inside its own definition. It keeps on looking inside the nested lists until there are no lists left and returns the sum in the end. There are three helper functions used in this code, sum, isinstance and sum_list. Our base case is when L is an integer, we do not need recursion for this. So, when the function is called on an integer, it will the integer. For example, sum_list(25), L is not a list, so the if condition is false and it returns L which is 25 in this case. Here, recursion is needed when calling the function on nested lists. For example,

sum_list([4, [1, 3, 5], 9]) -> sum([sum_list(4), sum_list(1, 3, 5), sum_list(9)])

                                      -> sum([4, sum(sum_list(1), sum_list(3), sum_list(5)), 9])

                                      -> sum([4, 9, 9])

                                      -> 22

Recursion is basically a method where the solution of a problem depends on smaller instances of the same problem. Recursion is very useful, big problems can efficiently be solved by dividing the problem into smaller versions and then combine the results to get the solution to the big problem. Recursion actually helps in saving up so many lines of code. Recursion is so far my favourite topic. Although sometimes it does get quite hard to trace the code but it is an extremely useful thing. A code with recursion looks beautiful but it is hard to understand at first.

Week 6

This week's lecture was about recursion is a way of defining a functions in which the function is applied in its own definition. It is one of the main ideas of Computer Science. A common thing done when writing code is to divide the problem into smaller problems and then combine the results. It is mostly used when the problem can not be solved by a for or while loop for example, checking elements in an arbitrarily nested list. One of the exercises we did in lecture was tracing this code:

def sum_list(L):

    """ (arbitrarily nested list of int or int) -> int 

    Return the sum of all ints in L. 

    >>> sum_list([1, [2, 3], [4, 5, [6, 7], 8]]) 

    36 

    """ 

    if isinstance(L, list): 

        return sum([sum_list(x) for x in L]) 

    else: 

        return L  

In the code above, the function sum_list is calling itself inside its own definition. It keeps on looking inside the nested lists until there are no lists left and returns the sum in the end. There are three helper functions used in this code, sum, isinstance and sum_list. Our base case is when L is an integer, we do not need recursion for this. So, when the function is called on an integer, it will the integer. For example, sum_list(25), L is not a list, so the if condition is false and it returns L which is 25 in this case. Here, recursion is needed when calling the function on nested lists. For example,

sum_list([4, [1, 3, 5], 9]) -> sum([sum_list(4), sum_list(1, 3, 5), sum_list(9)])

                                      -> sum([4, sum(sum_list(1), sum_list(3), sum_list(5)), 9])

                                      -> sum([4, 9, 9])

                                      -> 22

The function calls itself on each list. This is how recursion works.

This week's lab was on list comprehension and unittests, we were given code we just had to rewrite it without using list comprehension and also write test cases for each function. It was very easy.