Week Five - Trees

Week Six - Trees

I believe the most important thing beside the lecture this week was assignment 1. So I wish I could spend some time talk about that first.. At first, the assignment looked very complicated - three pages of assignment sheets, five files, hundreds of codes and the codes in GUI files were not making any sense (I later discovered that it is totally unnecessary to understand the GUI files to do the assignment). However, as I started to with through the assignment step by step with my partner, it was surprisingly not that bad. The first three steps were almost review from CSC108 (i.e. choose a data structure, write method for class). The fourth step required some knowledge with exception, however, in my point of view, exercise 2a and 2b really prepared us in order to complete this step. Step 5 is the hardest step in assignment 1, the method of moving three cheeses we discussed in class, and the hints in the assignment sheet really helped us a lot. Me and my partner first thought i is simply n//2 (it worked fined with the n<7). However when we finished implementing the whole method in Tour, we manually calculated more minimum steps for greater number of n, the theory fell apart. So we decided we are going to try all values of i from 1 to n-1 (using a for loop), and compare the number of steps associated with each i. The i with the minimum step among all i for a particular n will be the "i" we want. Since the algorithm involved a lot of recursions, it took so long to run as n becomes bigger. But, the method worked fine (although it is probably not the most efficient way of implementing it).


This week in class we implemented a class called tree, and it is through recursion. I think now we are moving the problem from tracing and understanding recursion to actually writing recursive codes ourselves. Since everything will break down eventually to a base case, I found it much more helpful to think about the base cases first. I think I really got a better understanding on recursion after assignment 1, so this week's lecture material was fine for me to understand. However, I do wish to include two Python build-in functions here, I think they can be really helpful on list comprehensions:
filter(function, iterable):
Construct an iterator from those elements of iterable for which function returns true.
any(iterable):
Return True if all elements of the iterable are true (or if the iterable is empty)

Finally, in the lab this week, there is one part that you have to convert a list comprehension to a for loop, I think it would be a better exercise, if it had been the other way around. Because we are much more familiar with writing a for loop, than a list comprehension.