assignment 2, Lecture material

Assignment 2 is complete, and I feel pretty good about my work for part 2. I think I managed to get all the functions to work properly (i.e. pass most or all possible test cases). The hardest parts of A2 Part 2, in my opinion, were: figuring out how to find the root of a RegexTree, and the function regex_match.

Finding the root of a RegexTree was important, since I used the algorithm for locating the root of a RegexTree 3 times in my regex_functions module. The root is either a dot or a bar (assuming the tree is not a leaf or a star tree). Locating the root is useful because it allows you to accurately split the tree into a left and right component. This allows you to use recursion on the left subtree and right subtree of the given root.

Regex match was also somewhat difficult. For star trees, you have to split the string s as:

s = s1 + s2 + ... + sk and check that all parts of s match the RegexTree r. However, there are so many ways to split a given string that this task seems almost impossible.

Thanks to Danny Heap's week 10 slides, an equivalent way to match star trees is to use the following algorithm: split s = s1 + s2. Then check that both s1 matches r, and s2 matches r*. s2 has to be a shorter string than the original string s (or else you will have infinitely many recursive calls). The base case here is the empty string, which should return True if the string s is empty. Now, you only have to check '2' possible ways to split the string s.

In other news, we have been looking at various sorting algorithms in lectures recently. Specifically, we have talked a bit about merge sort and quick sort. These are 'divide and conquer' algorithms since they involve dividing a list into half on each pass, making them more efficient than the sorting methods we learned in CSC108, like bubble sort and insertion sort.

One thing that surprises me is how many sorting algorithms actually exist. It is weird to think that there actually exist around 20+ ways to sort things...
http://en.wikipedia.org/wiki/Sorting_algorithm

Assignment 2 and Other stuff

I am very busy right now. I've got 4 tests next week in the span of 3 days, and a CSC148 assignment due next Thursday. Also, I have exercise 3 due this Thursday.

Luckily, I have already worked on Exercise 3 and Assignment 2 (part 2) and have made considerable progress already. Exercise 3 was quite challenging since it took me several hours to complete. At times I wondered whether or not I was even capable of completing it, but thanks to sheer will and determination, I was able to complete it. It feels great when your code works! But, it feels terrible when it doesn't...

So far, I have about half of assignment 2 part 2 completed. Again, it took me quite some time to figure out how to write the functions, but I eventually figured it out. Struggling through exercise 3 and assignment 2 made me realize that in order to solve these computer science problems, you need to be completely focused or else you won't be able to get anything done. Also, you need to be ready for failure. Very rarely do all your test cases pass on the first try, so you need to be patient and figure out where your bugs are, and not panic or else you will stress yourself out even more. 

Something I've learned throughout this course is learning how to use the wing debugger. I used to not use the debugger at all, but now I occasionally use it (with some success). 

As I write this, I am feeling quite stressed and nervous about the next month. I enjoy this course and I am definitely motivated to learn more in this course, but my 4 other courses are temporarily hindering me from working on CSC148 related things. I feel pretty good about my results in this course so far, so I hope I can keep up the good work.

Recursion

Recursion: 

Overview:
Recursion is a problem solving method which involves breaking down a problem into sub-problems. These sub-problems should be able to be solved in the same way as the larger problem. Usually it is a process where a function calls itself while inside the function, sort of like that movie Inception.

Credit: http://icannotdraw.thecomicseries.com/comics/25/

Why would we ever want to call a function inside of itself?
Here is a simple example:
A factorial is the product resulting from repeated multiplications. Specifically, if n >= 0, then
n! = n * (n-1) * (n-2) * ............. * 3 * 2 * 1.
We can break this problem down into sub-problems. Note that n! = n * (n-1)!
But then, (n-1)! = (n-1) * (n-2)!, and so on. Eventually as n decreases, we will reach 1, where we have to stop. (the base case)
Basically, in order to obtain n!, simply multiply n by (n-1)! By the definition of factorial will then compute (n-1)! by computing (n-1) * (n-2)! factorial, and so on.

Here is the code:

def factorial(n):
     '''Precondition: n >= 0, and 0! is defined as 1.'''
     if n <= 1:
          return 1
     else:
          return n * factorial(n - 1)


Here is another example:
The fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ....
is where each number in the sequence is the sum of the 2 numbers before it.

Let's say we wanted the 5th term of this sequence. The 5th term is the sum of the 4th and 3rd terms. Assume we did not know the 4nd and 3rd terms. We can still get their values by using the same algorithm: For the 4th term, this is the sum of the 2nd and 3rd terms. For the 3rd term, this is the sum of the 1st and 2nd terms. Once we run into the 2nd term, we can't say that this is equal to the 1st and 0th term, since this does not make sense. So, we define the base case as: if the term, n, is less than or equal to 2, simply return n-1.

Here is the code:
def fib(n: int):
     if n <= 2:
          return n - 1
     else:
          return fib(n - 2) + fib(n - 1)

Visually:

Advantages/Disadvantages of Recursion:
The factorial program can be written using an iterative process, with loops.

def factorial(n):
    if n == 0:
        return 1

    acc = 1
    for i in range(1, n + 1):
        acc = acc * i
    return acc

However, there exist problems that cannot easily be solved using simple for/while loops. For example, I am not aware of a simpler algorithm that computes fibonacci numbers. Problems like Towers of Hanoi are made much easier using recursion. In Computer Science, trees and linked lists are useful for storing and manipulating data. In order to access the data in trees and linked lists, it is easier to use recursion because trees consist of subtrees, and linked lists refer to other linked list objects making them recursive in structure.
For example in lecture, binary trees were able to be 'traversed' easily using techniques like inorder, preorder, and postorder traversal. These traversals are much easier to implement (1 to 2 lines of code) than any other non-recursive solution you can think of.

Some drawbacks of recursion:
Recursive algorithms can be slow. For example, when I try to move 30 cheeses using 4 stools (from Assignment 1), python took several minutes to compute the solution. Another problem is the usage of memory. If I want to compute factorial(2000), I get a 'maximum recursion depth exceeded' error.

Also, recursive functions can be difficult to write :(

Thinking about Recursion:
How do you know if a recursive algorithm works? Well, you have to have faith! (Sort of)
If I know a recursive algorithm works for the simplest case, I can assume that the algorithm will always work
on any instance of the simplest case.
For example, if I want to calculate the sum of [1, 2, [3, 4], 5], and I know that my summation algorithm works on flat lists (a list with no nested lists), then I can assume my algorithm work on any number of nested lists.

Personally, I relate recursion to mathematical induction. If I know that P(1) is true and I know that P(n) implies P(n + 1), then I can conclude than P(n) is true for all n > 0.

Similarly, if I know that an algorithm works on the simplest case (base case), and I know that the algorithm will work for some higher level cases, then I can reasonably conclude it will work for all cases.


Closing Remarks:
Before this course, I was uncomfortable with recursion. Although I was able to trace code and follow the lectures, I struggled to write recursive functions. Over the past few weeks I feel more confident in my abilities due to hefty amount of time I spent practicing recursion. One of the main problems I had was over-thinking the problem. Sometimes I would trace code too deep, or I would write a function in 5+ lines which actually could have been completed in 1 line using techniques like list comprehensions and ternary if.

Test, Linked Lists

Test 1 was written this week. I did not find any parts of the test particularly difficult, but I do know that I made some small mistakes on the last question about stacks. The question asked to implement a 'dividing stack' class which would only allow you to push items onto the stack if the new item evenly divides the previous number in the stack. In my solution, I called the wrong method: I used self.push(n) instead of Stack.push(n). However, I do believe the structure of my solution was correct (I even tested it myself..). As for the rest of the test, I feel confident that I did well. In particular I think I answered the recursion / tree question correctly, which is great. Of course, I may be completely be wrong so I guess we will have to wait and see.

This week in lecture and in the lab, the topic was linked lists. The lab was frustrating because I was not able to implement a queue using linked lists. I feel like I understand the basics of linked lists - each node has a value (a head) and a reference to its link (rest). But, in the lab I could not figure out how to remove the first element in the queue. The lab handout says we should have 2 attributes: a reference to where you add new LinkedList elements, and a reference to where you remove the oldest LinkedList element. I am not quite sure what this means. My attempt at a solution was to simply have the Queue class hold 1 attribute, a LinkedList object. In order to find the oldest LinkedList element, I tried to use a loop that stops once it reached a LinkedList whose 'rest' attribute was an empty node (i.e. LinkedList()).

So far this has been the only lab that I felt completely lost in, so I will try to re-work the lab this weekend and try to approach the problem in different ways.