Week 7: Linked Lists

When first introduced, linked lists appear to be abstract and hard to grasp. The idea of "next" or "rest" does not strike me as a straight forward concept until explained by our TA, Bryan. This is what I've come to terms with at the end of the week:

Node 0: empty; The variable to the class instance. In other words,
  >>> a = LinkedList()
Node 0 is basically a, used to call the first node, node 1, of the newly created instance of the class LinkedList. So, node 0 points to node 1.

Node 1: first element of the linked list; similar to the first element of a traditional python list. It points to node 2, i.e. the "rest" or "next" of node 1 is node 2.

Node 2:  second element of the linked list; similar to the second element of a traditional python list. It points to node 3, i.e. the "rest" or "next" of node 2 is node 3.

Consider node one as the head, the rest would be node 2, node 3, node 4, until the end because all the nodes are linked and point to their own next.

24.2 of the reading explained this similarly, but with graphical aid and shell code to illustrate it.

The methods to implement LinkedList are generally recursive. As the lab activity suggests, once you understand one code, the others tend to be similar.

The key is to start with the base case to handle None, then save rest as temp to preserve them while you change the head. Also, to traverse the list, use index value and recursively call index - 1 with the next node until index value puts you to where you want to be.

That's it for the week! Hope we all did up to our standards on our midterms!

Week 6: Trees

I've never been a morning person. Especially not on Mondays. But, ever since I switched to Comp. Sci., the life of returning to the lecture hall every Monday morning wasn't the same anymore.

But I digress...

Back on Monday, Dan covered tree terminologies, tree traversal, then followed up with code implementation the rest of the week. The tree terminologies seem simple enough. "Parent" and "siblings" makes sense to about anyone. But, the tree traversals aren't as simple as it looks.

On page 11 of week 6's slides, it says:

"Preorder: Visit the root node, do a preorder traversal of the
 left subtree, and do a preorder traversal of the right subtree

Inorder: Do an inorder traversal of the left subtree, visit the
root node, and then do an inorder traversal of the right
subtree

Postorder: do a postorder traversal of the left subtree, do a
postorder traversal of the right subtree, and visit the root node"

I thought I understood tree traversal after reading these three definitions, but once we got to the actual example, the inorder traversal was far from what I expected.

After a simple Google search, I found a website with a more detailed example and explanation for a CS beginner like me.

Here's the link: http://datastructuresnotes.blogspot.ca/2009/02/binary-tree-traversal-preorder-inorder.html

(This is a picture from the same website.)

The Inorder traversal is done recursively. Here's how the author of that blog explained it:

"(i) Traverse the left most subtree starting at the left external node, (ii) Visit the root, and (iii) Traverse the right subtree starting at the left external node.

Therefore, the Inorder traversal of the above tree will outputs:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10"
It cleared my concept quite a lot, as I originally thought you start with the left subtree and just enumerate each level is an ascending order, then visit the root, and visit the right subtree eventually. This is wrong. But, to further illustrate my wrong concept, here's an example of what my method would create using the above figure: 1, 0, 3, 2, 5, 4, 6, 7, 9, 8, 10.

Of course, don't do that!

That's all for the week. Thanks!

Week 4&5: Recursion...

Before I switched to CS, I was warned by a friend that dropped out of CS on his third year. He told me the thinking process to derive a code gradually becomes unfathomable and abstract. It would be more poetic to picture a battlefield, a scene where your elder comrade had fallen right before your eyes, warning you to take heed before you venture far into the chaos... But I digress. I took his two cents and was mentally prepared to face difficult concepts.

So here I was, dealing with recursion for seemingly the first time of my life. Both Dan and our TA expressed the importance and delicacy of recursion. I get it. It's quite peculiarly logical, but hard to grasp because of you're "defining something in terms of itself". It's no longer a one-shot logic and I feel like I'm getting to the weird part of math. Anyhow, Dan did a wonderful job showing us the ropes: tracing from the simplest parameter. I watched the Recursion lecture by Harvard University on Teaching Tree, but that didn't help me any better than Dan's lecture. Thus far, for every single recursion code CSC148 showed us, trying to trace it in one go is sometimes possible, but less effective than doing an organized, step-by-step tracing method.

For example, from the Permutations and String Length Examples shown in lecture,

def strlen(s):
  '''(str) -> int
  Return length of s.

  >>> strlen('abcd')
  4
  '''
  if s == '':
    return 0
  len_smaller = strlen(s[1:])
  return len_smaller + 1

You can trace it starting with strlen(''), the simplest case. 

Then, trace strlen('a') with the knowledge that strlen('') returns 0. 

So on with strlen('ab') then strlen('abc'). 

I can mentally trace it without plugging in values in parameters for this one by considering how recursion stops when you're left with an empty string after eliminating the first index. In other words, the very first index of a non-empty string will always be counted by the + 1 in return len_smaller + 1, then consider how strlen(s[1:]) rids the first character in the string each time and basically adds one for each character because of the last line of the code.

The latter method of tracing is way clumsier while in the end, I still indirectly traced it considering the base case strlen('') and strlen('a'). I'm assuming that for recursive codes, it'd be more efficient to be organized and start from bottom to top or top to bottom depending on the case.

Another example is the gcd code from the recursion lab. This is easier done from top to bottom when you are given csc_gcd(15,35) only.

def csc_gcd(n1: int, n2: int) -> int:
"""Return the GCD of non-negative integers n1 and n2
>>> csc_gcd(0, 0)
0
>>> csc_gcd(5, 0)
5
>>> csc_gcd(15, 35)
5
"""
# The gcd of n1 and n2 is n1 if n2 is zero, otherwise it is
# the same as the gcd of n2 and (n1 % n2)
if n2 > 0:
return csc_gcd(n2, n1 % n2)
else:
return n1

So you start from gcd(35,15) and then do csc_gcd(n2, n1 % n2) over and over again in an organized manner. This table was introduced to us by our TA Bryan. He also told us it would come in very handy during tests and exams because it is easy to help us trace, it is easy for the marker to give you full marks as well.

My bigger issue is with making a code using recursion. Honestly, I haven't gotten much practice yet. The labs felt rushed because I don't like missing anything the TA says, in case it is important like the table (that comes in really handy imo). So when I spend time to listen to the TA, I am left with less time to read the next section and actually write a code for it. He tries to compensate the lack of time by taking up codes (solutions) early, which means I never really got to think about it much before time's up. After the labs, I feel that I should redo the lab at my own time. Yet I didn't. At least not yet.

Honestly, this week had been quite hectic with family and friends. Too much trivial but time consuming things stopping me from studying and finishing up my assignments. So, hopefully I will get the time to think about binary_search(lst, s) and read the solution this coming weekend, as well as finish my A1.

Last but not least, I read two blogs today:
http://ilovecsc148.wordpress.com/ - 1/2/2014 Recursion with a bit of Intuition
http://quererna.blogspot.ca/ - 23/1/2014 Some comprehending for the introduction of Object-oriented Programming
I like the former better because it's not that easy to read the second one. I like the approach quererna has. Also, ilovecsc148 made a well-detailed tutorial and a nice description of his/her feeling towards recursion. Nice job to both of them! :)

Third week: exceptions

The past weeks, Dan had been covering exceptions but it wasn't quite emphasized on this week's lab. The concepts seemed easy to grasp, but when I work on my exercise, it was quite challenging. Since the exercise is already past the due date, I'll post related code here.

I understand how normally, programs stops on the first error raised, but it is also true that you can mitigate that by using try: . For example:

class E1(Exception):
  pass

class E2(Exception):
  pass

def raise_errors(x):
    try:
        int(x)
    except ValueError:
        raise E1('Raise errors')
    finally:
        raise E2('because i said so')

raise_errors("now")

The finally clause makes sure the code under it is ran despite the error in try. This code gives 3 errors when you run it. I highlighted the errors below:

Traceback (most recent call last):
  File "H:\Libraries\Documents\UTM\CSC148\Exercises\E2\raise_errors.py", line 9, in raise_errors
    int(x)
ValueError: invalid literal for int() with base 10: 'now'

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "H:\Libraries\Documents\UTM\CSC148\Exercises\E2\raise_errors.py", line 11, in raise_errors
    raise E1('Raise errors')
E1: Raise errors

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "H:\Libraries\Documents\UTM\CSC148\Exercises\E2\raise_errors.py", line 16, in <module>
    raise_errors("now")
  File "H:\Libraries\Documents\UTM\CSC148\Exercises\E2\raise_errors.py", line 13, in raise_errors
    raise E2('because i said so')
E2: because i said so

The reason I did this was a misinterpretation of the sentence "Your function reporter must always return normally, so it must catch all exceptions raised while it is executing and must never raise an exception itself". I thought function f is allowed more than one error since it says "catch all exceptions", and so I made this code to try forcing another error. 

I posted about this concern I have on discussion board and it appears that function f should not keep going with more errors. Rest assured, I do not need to prepare for such case when I do e2b.py.

To whoever reads my blog: what do you think about this?