Wednesday, April 1, 2015

Week 12: Last Impressions

CSC148 has been an enjoyable experience, and a great introduction to ADTs such as LinkedLists and Binary Search Trees. The most important concept that I have encountered this semester, in my humble opinion, would definitely be the ever-so-frightening recursion. Although this semester has been a bit of a struggle with grasping and harnessing recursion in my code, I expect to continue to hone by skills over the rest of my undergraduate career.

Unfortunately, I do have some concerns that my choice in completing A3 Option B instead of Option A will hurt me on the CSC148 final exam. A2 was markedly harder than A3, and I feel that option B was most probably tacked onto A3 as a result of a lack of feedback on our A2. The strike definitely has impacted me a many ways this semester.

However, I feel confident that I am continually improving on my coding skills, and I look forward to this summer where I'll be taking CSC207 and CSC236.

Good luck to my fellow classmates, and Happy Exam Season!

Saturday, March 28, 2015

Week 11: Revisiting a previous post

Note: Links to blogs that I have commented on or read have been included in this post. 

I have decided to revisit last week's (week 10's) post, as it describes the continuing struggle I have faced with grasping and mastering recursion. I wish I could say my approach to learning recursion has been anything other than brute forcing my way through a problem until I obtain a correct answer, or learning through mimicry, but that would be a lie. 


Recursion is the one concept in CSC148 that I have struggled with, and it is a fundamental concept that all programmers should have a strong understanding of. 


In week 7 of this course, I defined recursion in my own words:


"""

Recursive functions are functions that call themselves. If a task can be divided into identical, smaller sub-tasks, this is a good indication that you can perform this task by recursion.

They have a conditional structure that specifies a base case (or cases): a condition (or conditions) that will stop the function from making calls to itself.  The also have a general case, which specifies the method in which recursive sub-calls will be combined. Essentially, the general case is the part where the function calls itself. It is important that you designate a base case, or the function call will reach a maximum recursion depth, and result in a stack overflow.


What is this legendary stack you speak of? Recursion is actually a method of using stacks to achieve a task. However, call stacks are stored in a computer's memory, and these stacks cannot become infinitely large, as computers do not have an indefinite amount of memory space. Thus, when a recursive function has a bug, and never reaches a base case, the computer will eventually runs out of memory and crash the program. This is called a "stack overflow".

"""


I think recursion is definitely a concept that does not come easily to me. It will most probably be a concept that I gradually come to terms with as I grow as a programmer. It is certainly a new, and unused way of approaching a problem that I have never personally encountered prior to this semester.

I worry for myself, as I am concerned that I will not do well without having a fully understanding of recursion going into the exam and into 2nd year programming courses.Regardless, all I can do is try harder.

I think the one thing that keeps me afloat is realizing that my struggles are not unique to just me. 

For example, here are a list of blogs that I have either read or commented on:



https://humaircsc148slog.wordpress.com/2015/03/15/week-9-back-to-bsts-insertions-and-deletions/comment-page-1/#comment-2  Humair takes time this week to describe Binary Search Trees and various methods associated with these classes. Humair always takes the time to write informative posts, and it's always informative to see how my peers approach different problems. Humair's blog has been a pleasure to read this semester

https://csc148winter2015.wordpress.com describes their journey with recursion, and how they developed over the period of a semester. Notably, the writer finds that they learned how to approach recursion in their own unique way. 

http://christiangarciacsc148.blogspot.ca/2015/03/week-10-impressions-of-week-9.html?showComment=1427568192945 always takes the time to create clear and concise diagrams to help his peers understand topics. His posts are always informative. In one of his posts, he mentions a quote from a fellow student that he found guided him through his learning: 

“I think the key concept is: don’t start [from] details but start from structure.”

He proceeds to state that: "This is definitely a good advice to take home. Structure is really important when programming. A clear structure can help not only the person coding, but people looking at that code. Also, having a plan before starting anything helps to clarify ideas and to have an easier time coming up with a solution."

I think, ultimately, that recursion is as complicated as you make it. I have to learn how to simplify problems. To not overthink things, and to take things slowly. Rather than coding desperately, and trying a billion solutions until I find the one that works, I should rather just sit down and pause. Think about the core problem I'm trying to solve, and let things fall into place. 

I think one's approach to solving a recursive problem could actually be indicative of one's approach to solving every day problems. 

I'm normally a highly stressed individual who sweats all of the details. I angst over the trivial technicalities, and fail to see the larger picture at times. I have long since come to recognize this problem, and I continually work to change this aspect of myself. Hopefully, as time passes, I will be able to apply a calmer, more methodical approach to solving problems both in my programming life and in my everyday life. 


Tuesday, March 17, 2015

Week 10: Assignment 3

Again, the strike continues, and it's beginning to take its toll. I haven't really been following up on the lab material, as I should have, because of the chaos that has been going on. Debates being turned into term papers, assignments being pushed forward or pushed back. It's been a crazy time. In particular, the wording of the last couple of labs has been a little confusing and off-putting for me, and I'm not very sure how I should approach them.

Regardless, I've been working on Assignment 3, and it has been successful for the most part. Again, in this assignment we are working with trees. However, the tree is composed of GameStateNodes. I found that this lab required an extensive use of helper functions that simplified the assignment for me.  The difficult part was identifying the helper functions that were needed.

I had problems with two of the functions in the assignment, but these problems were fairly quickly overcome. Strangely enough, I found that assignment 2 was leaps and bounds more difficult than assignment 3. This may in part be because I chose to complete Option B rather than Option A, which seemed to be a longer undertaking.

Anyways, branching_stats was one such function that I had difficulties with, as my preconceived notions of dictionaries in Python were lacking. I kept attempting to use the .add() dictionary method, to no avail. A little tinkering around with dictionaries put me back on track.

Another function I had difficulties with was a helper function I used to collect all of the paths in the tree. I had difficulties conceptually seeing the path I had to undertake so as to obtain the path in each tree. Although I could see how I would go about doing this visually, I had difficulties translating it into code. After deriving the solution for the answer, I was saddened by how simple the answer really was, and how long it took me to find the solution .

I think recursion is definitely a concept that does not come easily to me. It will most probably be a concept that I gradually come to terms with as I grow as a programmer. I worry for myself, as I am concerned that I will not do well without having a fully understanding of recursion going into the exam and into 2nd year programming courses.

Regardless, all I can do is try harder.

Tuesday, March 10, 2015

Week 9: Optimizing Recursion

Thus far in CS148, we have learned that while recursive functions are often more elegant than functions that use loops, they are often not as efficient. However, there are ways of optimizing recursive functions.

For example, in a recursive function on a tree, you can choose to ignore branches of the tree that will not impact the output of your function. This reduces the number of recursive calls you make on your tree, and optimize the efficiency of the function.
        
    # The optimization here is that you can ignore branches. So you add conditions to IGNORE them.
    # When do you ignore the left branch? When node.data < start.
    # When node.data < start then you ignore the left branch.
    # See below:
    
    def list_between(node, start, end):
    ''' (BTNode, object, object) -> list
    
    Return a Python list of all values in the binary search tree
    rooted at node that are between start and end (inclusive).
    
    >>> b = BTNode(8)
    >>> b = insert(b, 4)
    >>> b = insert(b, 2)
    >>> b = insert(b, 6)
    >>> b = insert(b, 12)
    >>> b = insert(b, 14)
    >>> b = insert(b, 10)
    >>> list_between(None, 0, 15)
    []
    >>> list_between(b, 2, 3)
    [2]
    >>> L = list_between(b, 3, 11)
    >>> L.sort()
    >>> L
    [4, 6, 8, 10]
    '''
    if node is None:
        return []
    else:
        left_list = (list_between(node.left, start, end) 
                     if node.data > start 
                     else [])
        right_list = (list_between(node.right, start, end) 
                      if node.data < end 
                      else [])
        node_list = ([node.data] 
                     if (start <= node.data <= end) 
                     else [])
        return left_list + node_list + right_list

Tuesday, March 3, 2015

Week 8: Linked Lists

In week 8 of CSC148, we learned about Linked Lists (LLs).

Summary of Linked Lists:

- Linked lists are data structures
- Linked lists are similar to trees in that they utilize nodes.
- These nodes are represented as a sequence.
- Linked lists are similar to arrays (lists), as they both store data.
- However, there is a unique difference between lists and LLs.

- In a vector, if we wish to insert data into our array, we have to move all of the subsequent entries by one or more indices. Although this is not too much of a problem when we have a list of length 1 or 2, this becomes a huge undertaking when we have a list of length 2,000,000. The amount of work grows in direct proportion to the number of items in the list.
- Insertion and deletion operations in an array grows linearly with the number of entries.

- We can use another data structure to perform an insertion or deletion operation that is independent of the number of items in the array : the LL
- In a LL structure, each of our nodes is linked to the node following it.
- We access elements in a vector through indices. Each element is contiguous to one another
- In a LL, the way we get to another node is through links that use pointers to point to the memory address with the next node in the LL. We also have a terminating value for our last node in the list to indicate that it is the end of the list.

- To insert a new element in the list, all we must do is grab one of the pointers in the list (let's call this point A) and point it to this new value (C). Initially, node (A) was pointing to node (B). So, we can point this new node (C) to point (B). In a LL, we can have a million values, but all we have to do to insert one node is redirect those three values. This is in comparison to having an array with a million values. Nifty!
- However, vectors(arrays/lists) excels in different ways. Although LL are superior for insert/deletion. It does excel at being able to access any particular element in a constant amount of time through the power of indices.
- In the case of LLs, you must follow the pointers throughout the LL to "find" the node that we're interested in. In LLs, we only have a mechanism to go forward, and we must start at the front of the LL and traverse the entire LL to "find" our node.
- WLists can go backwards, but we have not covered this topic.

Monday, February 23, 2015

Week 7: Selected Summary - Recursion Post from Week 4/5

In week 4 of CSC148, we broached the topic of recursion. Recursive functions are functions that call themselves. They have a conditional structure that specifies a base case (or cases): a condition (or conditions) that will stop the function from making calls to itself.  The also have a general case, which specifies the method in which recursive sub-calls will be combined. Essentially, the general case is the part where the function calls itself. It is important that you designate a base case, or the function call will reach a maximum recursion depth, and result in a stack overflow.

What is this legendary stack you speak of? Recursion is actually a method of using stacks to achieve a task. However, call stacks are stored in a computer's memory, and these stacks cannot become infinitely large, as computers do not have an indefinite amount of memory space. Thus, when a recursive function has a bug, and never reaches a base case, the computer will eventually runs out of memory and crash the program. This is called a "stack overflow".


If a task can be divided into identical, smaller sub-tasks, this is a good indication that you can perform this task by recursion.


Fortunately, I find tracing recursion (relatively) straightforward to parse. Unfortunately, I find recursive functions extremely difficult to write. In last week's lab, we were introduced to tracing recursive functions in Python. Tracing recursion mentally is a bit of a mess at times, when you're trying to determine the output of a function call. 



For example:

def nested_concat(L):
    """(list or str) -> str
    Return L if it’s a str, if L is a (possibly-nested) str return
    concatenation of str elements of L and (possibly-nested) sublists of L.
    Assume: Elements of L are either str or lists with elements that
            satisfy this same assumption.
    # examples omitted!
    """
    if isinstance(L, str):
        return L
    else: # L is a possibly-nested list of str
        return ’’.join([nested_concat(x) for x in L])

In this function, we pass an argument that can either be a list or a string. If the argument is a string, then then argument is returned. Else, the join function is used to concatenate all ofthe elements in the argument. The tricky part is realizing the recursive bit: essentially, the 
base case is that the argument should be a single, concatenated string. The function will
mutate all of the elements, sub-elements, sub-sub-elements (and so on), until it meets this condition. I've commented the tracing of two of the example calls posted in the lab below. 
    1) nested concat([’how’, [’now’, ’brown’], ’cow’]) # To trace this call: nested_concat([[’how’, [’now’, ’brown’], ’cow’]]) # We notice that L is a list: thus the else condition is reached --> ’’.join([nested_concat(x) for x in [’how’, [’now’, ’brown’], ’cow’]) #We notice that there is a sublist in L, so we concatenate the elements in that list --> ’’.join([’how’, ’nowbrown’, ’cow’]) #Now L is a list of str. Let's concatenate! --> ’hownowbrowncow’ 2) nested_concat([[’how’, [’now’, ’brown’, [’cow’]], ’eh?’]]) # First, we notice that there are multiple sub-lists --> ’’.join([nested_concat(x) for x in [[’how’, [’now’, ’brown’, [’cow’]], ’eh?’]]# We identify that ['cow'] is the innermost list, and concatenate each element in that list (only 1)# The list containing ['cow'] is ['now, 'brown', ['cow']] # so we would end up with 'nowbrowncow' # The list containing 'nowbrowncow' is [['how', 'nowbrowncow', 'eh?']] --> ’’.join([’how’, ’nowbrowncow', 'eh?’] --> ’hownowbrowncoweh?’
Although I understand the concept of recursion, I am finding it difficult to actually put it into practice. Specifically, I have difficulties selecting and coding the base case and the general case of a recursive function. Parsing and developing recursive functions is something that will take some time to get the hang of. Hopefully I will be able to wrap my head recursion and get a strong handle of this very essential concept.

whimsies and I were in a similar situation of understanding the conceptual ideas behind recursion, but having difficulties executing this knowledge in week 5. Hopefully, our understanding of recursion has grown over the last couple of weeks!


Monday, February 9, 2015

Week 6: Object Oriented Programming

Please head over to https://nanalelfecsc148slog.wordpress.com/2015/02/16/summary-of-object-oriented-programming/ for an interesting post on OOP!

In week 6 of CSC148, we have been assigned the topic of summarizing Object-Oriented Programming.

Below, I will share a quick summary of OOP in jot-note and sentence form.

The Object-Oriented Paradigm

Object-Oriented Programming emphasizes objects (data) over actions. This is in contrast to procedural programming, where programs are approached by decomposing problems into a series of actions (functions).

In OOP, we approach a problem by decomposing it into data types. The difference is what we consider first (data before actions vs actions before data).

Objects in Python:
Class (data type definition): a blue print for creating objects
- field/attribute (data member)
- method (function member [action], operations for acting upon data)

Instantiating an Object
An object/instance is a piece of data.

When we instantiate a class,  each instance has its own copy of the fields, but not its own copy of the method.

Principles of OOP

[1st Principle]
Encapsulation: The fields of an object should only be read by methods of that instance's class.
 
- Methods act as "interface" to object's field
- Idea that when you create a class, the methods that you give that class encapsulate (encompass) all of the knowledge that is meant to be done to the data that makes up that data type (modulate data)

[2nd Principle]
Inheritance: The idea of inheritance is that some data types/classes may overlap, such that one data type has all of the same methods/fields found in another.

- The child class will inherit all of the methods/fields of the parent class (including any attributes/methods that the parent class has inherited itself)
 - Child/Descendent = subClass. Parent/Ancestor = superClass

Abstract data types can be a bit confusing to identify as supertypes/subtypes. Think before using inheritance. is-a (a car is a type of vehicle) vs has-a (cars have steering wheels, but a steering wheel would not be a subclass of a car. a steering wheel is not a type of car). Extending/composition.
 
In some OOP languages, every Class is required to inherit from one other class. By default, this Class is a special Class called the object Class, which is built into the language.

Overriding: To override in OOP means to redefine an inherited method.

Invoking methods: object.method(args)

Polymorphism
x.foo()
Polymorphism: depends on type x

Class member (member of class itself, not any instance)
- Class.field
- Class.method(args)


Summarizing Privacy and Property in OOP (Jot-notes)

- Python has no notion of attributes being private, so they're all accessible to clients, but Python has a property mechanism to redirect access to an attribute so that it muse use a method

- property() function:
    - create a method to set x to its initial value. can only be done during initialization. check whether             the name _x is already defined in object self
    - def set_x(self,x):
        if '_x' in dir(self):
            raise Exception('Cannot change')
        else:
            self._x = float(x)
    - next, make sure anybody wanting to use value of attribute x actually uses the value referred to by     _x:
    - def get_x(self):
        return self._x
    - Now, we must tell Python to redirect all atempts to assign to or evaluate x using applicable    
    methods
    - property() ==> takes 4 arguments: method to get value of x, method to set value, method to del         attribute x, and some documentations (arguments can optionally be done)
    - x = property(get_x, set_x, None, None)
    - now: all client code that evalutes or assigns to x is redirected to get_x and set_x

Optionally, you can use @ headers:

For example:

class Example(object):
    def __init__(self, value):
        self.x = value
    @ property
    def x(self)
        return self._x
    @ x.setter
    def x(self, value):
        if '_x' in dir(self):
            raise Exception('Cannot change')

These headers accomplish the same objective as the property function. Now, even the code we have written in the method of class's init gets redirected.

Overall, I believe that I have a strong inclination towards OOP versus Procedural Programming, as I prefer approaching problems by decomposing them into data types rather than decomposing them into functions. Python is an extremely accessible and intuitive programming language that is an excellent introduction to the world of programming.