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.

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!

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.

Week 5: Tracing 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 of the 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?’



    

Week 4 : Recursion

In week 4 of CSC148, we have 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, or the computer will eventually runs out of memory and crashes 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.

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.

Also, whimsies left me a nice comment on my last post. I decided to return the favour and leave a comment on her page as well.

Week 3: Why Geeks Need to Write

For week three of CSC148 SLOGs, we have been assigned the topic of "Why Geeks Need to Write". This presents an important topic in computing, as it articulates the necessity of writing and written correspondence.  Writing is a means of delivering information to others, and analyzing your own understanding of a topic.

Knowing is not enough. Communicating what you know is a necessity of life, and english is a medium through which we can deliver this information to others. Whether it be filling out a document, writing a paper for a class, or reporting on a work project; writing never truly disappears from our lives.

Much like syntax is important in our coding, it is also important in our writing. In fact, coding and english are both languages in which we can convey information. Sufficient context, eloquence, and precision are required in both of these languages.

Written information is easily revisited and a great means of recording facts and opinions. The brain is notorious for overwriting and misplacing information that we learn. Graphite, digitized text, and ink are excellent mediums for preserving information that could otherwise be lost. Recording the facts we learn, the concepts we find difficult, and the new information we derived from our learning processes, are methods that can be used to harness our minds.

Often, when attempting to convey information to others, we are able to identify any gaps in our understanding of a topic, or inconsistencies in our theoretical knowledge. Additionally, by conveying information, we are often forced to summarize information in a concise but informative way, thereby helping us to distinguish important information. Learning, and sharing what we have learned, can often be one and the same thing.

A miracle!

I went into the CSC165 exam with a mark in the high 90s, and left the exam completely convinced that I had not managed to achieve a 40% on the exam. Since the course requires you to achieve a grade of 40% on the exam in order to pass the course, I was convinced that I had failed and would be doomed to failure. After an excruciating month of waiting, I received my final grade. An A. I don't think words can describe the simultaneous feelings of relief and inadequacy that flooded over me. Relief, as I had, through some miracle of God, passed. Inadequacy, as I feel that it was most probably a huge fluke. Regardless, I will take what I can get. A new semester has begun. I wish everyone luck =).