Monday, April 6, 2015

Last Impressions

What a ride CSC148 has been.

If I had to sum up my weekly experiences with CSC148, I think it would go something like this:

1. Learn a topic in class, and feel confused about anywhere from 50-80% of the material.

2. Go to labs and bombard the TA with too many questions. Fortunately, clarify a few points, and approach the labs with more confidence(, often completing them all and acing the quiz)!

3. Read over the new assignment handout, feel confused about anywhere from 80 - 100% of it. At this point, I have a mini-breakdown and probably Skype in a friend for support.

4. Inhale. Exhale. Determine what the assignment is really asking, go to office hours and get some insight from profs (although for most of office hours, I spent the time asking questions to my fellow classmates, who are a great source of help). Tackle the assignment.

5. Struggle with the assignment, consider giving up, attending more office hours, pushing through. Feeling on top of the world when my code returns the first move in the centre grid of an empty 3X3 Tippy grid.

6. Feel extremely rewarded when I see how I was able to solidify lecture material and understand it so much better through application in labs and especially assignments.

7. Repeat steps 1 - 6

I guess what I am trying to say is that there wasn't any one conceptual hurdle in this course, because everything was a struggle at first. Every step of the way, I encountered conceptual hurdles with the material at the time, starting with object-oriented programming in the first few weeks of class, and progressing  to ADTs, recursion, trees, and linked lists. However, along every step of the way, I also realized that the obstacles I faced were indeed hurdles and not brick walls. Through practice and a lot of help, I was able to overcome all of them, and subjects that seemed so difficult in week one, like class design and working with game states/strategies, are a breeze now.

Besides the material we covered in class, another major component of the course were the SLOGs we have been keeping. Trust me when I say that this may be my last SLOG entry for the course, but it definitely won't be the last SLOG entry I'll every write. Through writing SLOGS to organize my jumbled thoughts into words, reviewing my peer's SLOGs to see how they approached certain things and what they struggled with, and revisiting my own SLOGs from just a couple of months ago, I have been able to learn a significant deal and witness how much I have progressed. In retrospect, it has been a truly rewarding experience, even though I didn't always think that way when I sat down at my computer to type up a new entry every week.

The only other comment I wanted to make was on the subject of the strike. I think in the context of this course specifically, the strike had a huge negative impact, because the weekly support I needed to solidify my learning (and quite frankly, to keep me on track) was taken away. These last few weeks have been a heck of a lot harder, simply because the material was getting harder and we were getting less rather than more support. In a course like CSC148, where everything we learn builds on previous knowledge, being confused in one week really carries over and messes things up from there on out. However, what's done is done, and I sincerely hope that events like that never disrupt the quality of our education again.

And now, as I am about to sign off on the topic of last thoughts, I figured it would be suiting to look back on my first impressions of the course. I remember how overwhelmed I had felt in the first several weeks of class, while I was still in the transition period from CSC108 to CSC148. I think the best part of taking courses like computer science is not that it's an easy 4.0, or a course that requires minimal effort. In fact, I found this course hard to understand and hard to get stellar marks in without a significant deal of effort. However, I think the work we have done in CSC148 has really paid off, because it forces us to use our brains, and take foreign concepts and fully digest them so that we can apply them comfortably. Never before have I felt the gears in my brain turning like I did in this course as I tried to solve the problem at hand. It hasn't been easy, in fact sometimes it has been downright frustrating, but those struggles can be overlooked when you come out triumphant. Ultimately, it's amazing to see how far I've come throughout this course, and I wanted to thank the professors and TA's for their multitude of contributions to my learning process. I am excited to see where I will continue to go, as I embark further in my computer science endeavours.

Revisiting... Recursion!

Wow, it's hard to believe that we are already at the point in the course where we have to write the revisiting SLOG! I wanted to do mine on the topic of recursion, since has been, well, a recurring subject. Over the course of this semester, we have been introduced to recursion and befuddled by the idea of calling a function within its own return statement. We have traced recursion calls and convinced ourselves to believe that each recursive call will work if the previous call worked (much like mathematical induction). Most of all, we have wrestled with recursion in our labs, tests, and assignments, and looking back now, I can definitely say I am much more comfortable with it than before. I scrolled down to reread my original entry about recursion, all the way back in week 4, which can be found here: http://angeslog.blogspot.ca/2015/02/recursion.html

Overall, I still agree with my simple entry on my impressions to recursion. It seemed that I had a pretty good grasp on the very fundamentally basic applications of recursion back then, for functions like sum_list. I was able to understand that the reason calling a function in its own function body did not result in an infinite loop of function calls, because of the if/else (looking back, it doesn't always have to be an else statement!) statement that looked for the base case that doesn't require recursion or calling the function and actually returned a value or object.  From there, that value or object is passed on up to the function call that produced it, which returns a new value or object that is then passed up, all the way to the very first function call. This was very well illustrated in labs where we had to deal with trees, and leaves. For example, in the lab from week 6, we were required to complete the body for the following function:

def evaluate(b):
    ''' (BTNode) -> float

    Evaluate the expression rooted at b.  If b is a leaf,
    return its float data.  Otherwise, evaluate b.left and
    b.right and combine them with b.data.

    Assume:  -- b is a binary tree
             -- interior nodes contain data in {'+', '-', '*', '/'}
             -- interior nodes always have two children
             -- leaves contain float data

    >>> b = BTNode(3.0)
    >>> evaluate(b)
    3.0
    >>> b = BTNode('*', BTNode(3.0), BTNode(4.0))
    >>> evaluate(b)
    12.0
    '''

My implementation was the following:

    if is_leaf(b):
        return b.data
    else:
        return eval(str(evaluate(b.left)) + b.data + str(evaluate(b.right)))

At the base case when we had reached a leaf and the first if-statement was reached, we would simply return the leaf's data which was a float. If we hadn't yet reached a leaf, we would keep calling the function on the left and right children of each subsequent node, until we reach a leaf, and then continue passing the data up through the nodes, evaluating along the way to produce a final float. I thought it was really cool how we could break a recursion case down into its base cases, and cases that do require recursive calls.

Now that I revisit my introductory days to recursion, I realize that I also learned through the assignments that the recursive calls don't always have to be in one compact line like the above return statement in the else-statement. In Option A of Assignment 3, I was able to play with recursion with the original Strategy Minimax, which bought about Memoize, Prune, and Myopia. I want to use StrategyMinimaxMemoize to illustrate my point.

In StrategyMinimaxMemoize, I fine-tuned my original recursive function for suggest_move, which significantly improved the efficiency of my code. At each step along the way, if the present game state was not over, and we had to keep checking the subsequent game states down to an end game state, my code no longer simply returned a recursive call to reach those states. Instead, before making those recursive calls, I checked a dictionary of game states, to see if I already encountered this one and had the score already saved. If not, I used recursion to find the score of the present game state, and stored it in the dictionary in case I came across it again in the future. I thought this was really cool, because I was under the impression that recursion had to be a single-line return statement to work properly. Instead we can check values in dictionaries, and assign new values, all the while not breaking the pattern of the recursive calls.

However, not everybody feels the same way about recursion. It was very interesting reading over the thoughts a fellow peer had on recursion, in his or her SLOG entry found here:

http://mycompsciblog123.blogspot.ca/2015/03/revisiting-recursion.html

In this entry, the author mentions why they feel strongly against recursion, because it is difficult to understand the code, and even more hard to debug it. My peer wrote:

I originally found recursion difficult to read. I still 100% agree with this. Despite becoming incredibly familiar with recursive code I still find it a huge pain to read. I am definitely not alone with these thoughts, I have talked to classmates, upper years, as well as professional software developers. I found it incredibly interesting when one of the software developers were told me that recursion is usually frowned upon during most projects. When I asked why, he said that when new people are brought onto a team, recursive code can be very difficult for them to understand how the pre-existing code works... The most frustrated I have been all year was having to debug the minimax algorithm. The main difficulty with going through the code was that it hard to see exactly how the code was looping. With iteration it’s very easy to see how the program loops. With iteration it is usually much easier to see where the code is going to end. With recursion it is exceedingly difficult to see what the code is going to return.

I do agree with some aspects of what he or she had to say. Recursion is more difficult to read, because we don't immediately see what the function is returning, since we have to call it repeatedly. This naturally makes it even more difficult, when we are trying to find an error in our code, because we cannot see what is passed on through each iteration of the function. However, with the aid of a diagram, I think many problems are simplified enough that recursion makes perfect sense. In addition, with recursive calls, the same function is called over and over again, so if we are trying to spot an error, it wouldn't find it seven or eight steps into the recursion - it should be right there in our recursive statement, right from the first call. Although I do see where my peer is coming from in terms of the difficulties presented, I definitely do not believe that "recursion should be avoided whenever possible".

Overall, I think recursion is a super powerful, albeit sometimes slow, tool that really utilizes the computer's power in calculating permutations quickly, when human brain's cannot. Now that we learned some cost-cutting tricks like memoization and alpha-beta pruning, I am even more confidenct in the power of recursion to solve almost anything from sum_list, to minimax, to the many more problems that lie ahead!

Sunday, April 5, 2015

Week 9 Reflections

TEST 2:

This week, we wrote our second term test! I really didn't know how I felt going into it, particularly about linked list, which I was still wrestling with the night before. Overall, I think it went alright. The first few questions were about BSTs and traversing the tree in preorder, which were fairly simple to work with. However, I realize I made a careless error for the list_even_between method we had to implement, which required us to traverse a BST and find all even values in the tree between the lower and upper bounds provided in the method call. In addition, we have to take advantage of the structure of a BST (all left children's values are less than the current node's value, and all right children's values are greater for any given current node that isn't a leaf) in order to avoid checking redundant nodes. Here is my code to achieve this:

result = []
if node is None:
    return []
if start <= node.data <= end and node.data % 2 == 0:
    result.append(node.data)
if node.data >= start:
    result = result + list_between(node.left, start, end)
if node.data <= end:
    result = result + list_between(node.right, start, end)
    

return result

In retrospect, I made an error in the conditions if node.data >= start: and  if node.data <= end:. Considering that I already checked if node.data was equal to start or equal to end in the first if statement, I should not have checked again if node.data was >= start or <= end, rather I should have only checked for strictly > start or < end, because a BST cannot contain the same value twice anyway.  Other than that, I think the method for absorbing linked lists was rather simple if you understand the structure of a linked list, and overall the test went relatively well! Fingers crossed!

WEEK 9 LECTURE MATERIAL:

This week in lecture, we revisited Binary Search Trees, and talked about the code for insertion and deletion in a BST. An interesting analogy I turned to can be found my peer Nana's SLOG at:

https://nanalelfecsc148slog.wordpress.com/2015/03/16/binary-search-trees-week-9/

I found out that binary search trees can be used to construct and maintain ordered lists such as priority queues (similar to simple Queues seen in class, but where each node also has a priority, and nodes with highest priority exit first). Self-balanced binary search trees combined with priority queues create High Performance priority queues. Here is an example.
Let’s assume that we’re running a hospital and there is only one doctor on staff. The first patient walks in. Since there is no one else in queue, the doctor takes him in immediately. The second patient walks in with a cold, so he’s added to the queue with priority 1 and waits for the doctor to become available. Next, a third patient walks in with an axe in his head. He is added to the queue with priority 10, so the patient with a cold is bumped down the line. Next, a man walks in with breathing problems, so he’s added with priority 7, and once again the man with a cold comes last. As more and more patients come in, the queue gets bigger and bigger, and it takes more time to search for the patient with the highest priority. This is when self-balanced binary search trees come in use.
fig548_01_0

This example is a really cool illustration of how BSTs have an impact on our everyday lives. Instead of the doctor browsing through the entire queue in the worst case to find a patient with the highest priority, he could organize his patients in a self-balanced BST with the node value representing their priority level. In order to find the patient with the highest priority, the doctor only has to look at the rightmost leaf, and then traverse in the tree in a flipped "inorder" pattern (visiting right child, current node, then left child). This greatly improves the efficiency with which the doctor can determine which patients require the most attention, and may help save previous times and even lives!
Reading Nana's SLOG inspired me to think about the purpose behind everything we are learning in computer science. Through learning about self-balanced BSTs, I was able to appreciate the efficiency it provides, but what good is this efficiency anyway? I mean, we don't create BSTs for our health, do we? It turns out we actually do (as seen in the above example), and I found this really amazing, because I had never really drawn connections from what we're learning to very necessary real-life operations. Making the connections between BSTs and this hospital analogy excites me, because I am  starting to see how the things we learn in class can make an impact on daily life, and that makes the material much more meaningful to learn!