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!



Sunday, March 8, 2015

Week 8 Reflections

ASSIGNMENT 2

This week, we submitted our second assignment, and what a roller coaster it has been. I started off looking at the assignment and feeling like breaking down into tears by the sheer overwhelmingness I experienced. What is a tippy? What on earth is minimax? Not to mention we were given starter code that I was not at all familiar with, after having spent so much time lovingly developing my own code.

However, when I couldn't put it off any further, I tackled this assignment head-on. First I read the starter code that we were given, and when I fully understood it, I was able to appreciate why the instructors did things a certain way. For example, I wrote a specific game_view subclass in my first assignment that took care of playing Subtract Square, but now I can see how the apply_move method in the game state class enables one to play straight from a generic game_view that calls on the game state.

Afterwards, I decided to start from the most manageable class - TippyMove. This class was so simple that the parent class didn't have any code in it at all, and I think the fact that it serves only one purpose (creating a move a user could implement) made it easy to overlook in assignment 1. However, it definitely came in handy for apply_move later on.

Next, I took on the TippyGameState class, which was not as gargantuan of a task as I initially thought it would be. I think the most challenging part of that class was determining how to generate a rough_outcome, which I think I could have done a better job on. I didn't realize until after the assignment was over that rough_outcome should only look at the present state and not any possible future states. I don't think it is a necessary method for a tippy game though (especially on a 3x3 board, where there are only so many permutations), but I can definitely see how it could come in handy in a game of chess.

The biggest challenge on this assignment was probably implementing suggest_move in the StrategyMinimax class. First of all, I had trouble understanding how Minimax worked as a strategy, because of the multiplication by -1 each round. However, after I understood it, writing a recursive case was exactly like we had done in classes and labs -> write a base case, and then write a recursive function for cases that aren't so simple. I think the hardest part was pairing up each possible score with the move that produced that score, but I was able to manage that by writing a helper function that found the score, and using it in the suggest_move function which also had a recursive body.

Overall, now that the assignment is over, I feel a lot more confident about recursion and also in my ability to problem solve in general. It is definitely a great feeling to see how far I can come in a span of a couple of weeks - from desperation to having a intimate knowledge of the what and how of the assignment. It almost makes me excited to see what Assignment 3 will bring. Almost.

LINKED LISTS

One of the best parts of keeping these SLOGs is that I'm able to read what my peers are encountering in their CSC148 journey, and I'm able to learn from it. I found Humair's description of linked lists very apt and interesting. His entry can be found at:

https://humaircsc148slog.wordpress.com/2015/03/08/week-8-assignment-2-linked-lists/

In particular, this explanation helped enhance my own understanding of linked lists:

Now, what I find really fascinating about linked lists is how we can make them function just like regular lists. If we had a list say x = [1, 2, 3], and I wanted to find out the value at index 1, I would simply evaluate x[1], yes? Well we can do something similar with linked lists, we just have to implement a method called __getitem__. We were tasked with writing this method for our lab 7. Here was my implementation in python:
12345678910111213141516171819202122232425
def __getitem__(self, index):
''' (LinkedList, int|slice) -> object
Return the value at index.
# Don't worry about slices for now
>>> lnk = LinkedList()
>>> lnk.prepend(1)
>>> lnk.prepend(0)
>>> lnk.__getitem__(1)
1
>>> lnk[-1]
1
'''
if index >= self.size or self.size == 0:
raise IndexError('Index is out of bound!')
else:
if index < 0:
index += self.size
curr_node = self.front
i = 0
while i < index:
curr_node = curr_node.nxt
i += 1
return curr_node.value
view rawgetitem.py hosted with ❤ by GitHub
Here we first make sure that the index that was given is within our bounds. If not we simply return an error. Otherwise we begin our search for the value. There is one minor thing to consider however, if a user wants to search something like x[-1] we have to adjust the index so that it’s searching for the last value, so we need to only perform a simple addition to adjust for the right index if it’s less than 0. 
Having struggled with this problem myself in lab 7, it was very helpful to read his explanation about linked lists. Some things I hadn't considered were: what if the index was not within the range of the linked list and what if the given index was < 0. His code deals with this by raising an index error in the first case, and cleverly devising the corresponding index that is > 0 by simply adding the negative index value to the size of the list in the latter case. After setting the index up that way, the while loop becomes very intuitive, with an accumulator i keeping track of the index of the current node we are at, and having curr_node advance to curr_node.nxt each time i has not yet reached the indicated index. Once the while loop condition is broken, i will be equal to the index value passed in the argument, and we simply return the value of the current node at that index value. 
This explanation definitely helped with the implementation of further methods including __setitem__. Overall, I found linked lists fascinating, because they make use of the recursion we have been learning about, and are a perfect example of object-oriented programming. They were a little bit difficult to grapple with at first, but after many diagrams and with the support of my peers' SLOGs, it became a very intuitive and interesting concept!


Saturday, February 28, 2015

Abstract Data Types

* Please mark my Week 6 entry: Summary of Object-Oriented Programming

For my Week 7 reflection, I will be writing a short summary of what I've learned about abstract data types. In CSC108, all of our assignments were given to us with explicit instructions on what certain functions should return. Because of this, I had become accustomed to seeing a problem and instantly trying to formulate code to resolve it. That may have worked for individual functions, but when presented with classes of various methods and multiple functions that all have to work together to create something like a gaming interface, it's very difficult to start writing function bodies without having a good sense of the big picture.

ADTs are useful in providing a glimpse of the bigger picture, because they describe the data stored in an object and the operations that can be performed on it, but they don't include the actual implementation. When a class' attributes and methods describing what it should be able to do are provided, it is much easier to understand the purpose of each method and see how they are interconnected and summate to the class as a whole. ADTs are also handy when they are made public for clients to use through a specified interface, because the user only has to deal with higher-level details such as passing arguments into a function call, and not with the nitty-gritty details in the function body.

One example of an ADT is a stack, which stores data and has operations push, pop, and is_empty. As a user, one wouldn't have to worry or be confused about how push, pop, and is_empty are implemented to understand how to use a stack, because the information on a stack's data and operations is all they need to effectively use it. All in all, I especially appreciated this aspect of ADTs, because they provide a framework that helps us focus on how we can use certain algorithms to solve problems, without leaving us caught up in the lower-level details like implementation.

Monday, February 16, 2015

Summary of Object-Oriented Programming

Over the past few weeks we have covered and extensively practiced the basics of object-oriented programming. Object-oriented programming helps us to model real-world problems presented to us and find solutions by using objects. Some of the specific OOP concepts we discussed included classes, exceptions and encapsulation.

First of all, objects are used to represent and manipulate information. We can sort objects that represent similar types of data and that have similar operations that can be performed on them into classes. In order to design a new class, we must first declare the class and pinpoint the attributes and behaviours the class needs in order to operate. Then we must write docstrings explaining to the user what the class does, and also write methods that carry out the actual implementation. When one class appears to be a more specific example of another class, we can make it a subclass to the more general class. This is neat, because we can use the idea of inheritance so that the specific class can absorb all the features it has in common with the parent class, and build further on them. Using inheritance is especially handy, because you don't have to repeat code, which prevents tediousness and careless errors, and it is also more easy for the user of the code to read it. A great example of this can be found on the SLOG http://beyoncepadthaiismywarriorname.blogspot.ca:

"Let us say we are playing a couple of board games such as Monopoly and Snake and Ladders.   The initial state of the game such as how much money you are given or not, depends on the game. It is different for Monopoly, Snakes and Ladders etc. Thus, if I decide to play Monopoly(I call an instance of the game), the initial state of the game Monopoly would be called and that would be defined by the parameters in the initializer of Monopoly. On the other hand, if I decide to play Snakes and Ladders, the the initial state of the game Snakes and Ladders would be called and that would be defined by the parameters in the initializer of Snakes and Ladders."

This example extrapolates from our gamestate class in Assignment 1. It groups together board games that have similar features, such as the money assigned to each player. Since the games have similar features, it uses a generic game state class to provide the overarching framework, which each individual subclass (representing a different game) will fill in in its specific implementation. Class design was exhaustively covered in our first assignment and the first midterm. Through them, I was able to appreciate the elegance of classes, subclasses and inheritance.

In addition, I also learned the purpose of exceptions, and how we can raise "NotImplementedError" in the methods of generic superclasses so that we can override the methods in the subclasses with code detailing what the method should do in that more specific case. Another issue was of the client being able to alter the mutable objects in the classes we created. To prevent this, we had to use encapsulation, or information hiding, through the property function, which helped us ensure that the client could not change the "set" or "get" values in the class.

All in all, over these past few weeks, I was able to get a pretty good grasp on object-oriented programming, in particular designing classes to solve problems. Since Class Design was one of the last topics in CSC108 and it was only covered very briefly, I wasn't very conversant with the concepts before. However, I am much more comfortable with employing classes now, and appreciate its usefulness much more!

Saturday, February 7, 2015

Recursion


In week 4, we learned a neat little thing called recursion. It involves calling a function within its own function definition, which was a quite confusing concept for me. However, through tracing many instances of recursion, I was able to understand that it worked because of the "else" component in the if-statement, which doesn't result in the function calling itself.

For example, if given the following function:


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

If L is not a list, L is returned. If L is a list, every element of L is passed as an argument to sum_list, which then checks if each element is not a list and should be returned, or if it is a list and sum_list must be called again for each element within that nested list. I initially wondered how the function could return anything if sum_list would just be called indefinitely, but then I realized that at some point, the nested lists would end, and the sum of that would be returned into the list that is one layer outside, which would subsequently return more sums, until the function produced a final integer value. Thus, the else-statement is crucial for the function not to become an infinite loop.


I found recursion to be a clever concept, because all one has to do is prove the function works for the most minimalistic instance of the function, and work from there. For example, in the case of sum_list, if the function works for a single integer, one can apply that to a list of single integers. If it works for a list of depth two, one can apply that to a list of lists of depth one, and so on, in a method very similar to proof by mathematical induction.