Saturday, 28 February 2015
Tuesday, 17 February 2015
slog 7: trees
trees are an interesting ADT. that is because although in code they are depicted of as an unorganized nested list, however their true structure can only be revealed in a diagram.
a property of such a diagram includes:
nodes
the root
path
length
leaf
internal node
height
depth
arity.
even though the "look" like an unorganized list, in order to construct a tree object using OOP, (at least ) python recognizes key worlds "value" as the root and "children" as its branches when declared in the initializer.
although we have not encountered a situation where a tree can be used to solve real computer science problems, it is not a stretch to say that there are "ideas" that can be represented by trees if you were to see how to sort (or, traverse) through one:
this goes back to the idea that a tree in python can look like an unorganized nested list. as such, one should build a recursive function to traverse through it.
there are (so far) two implementations of functions that we have worked on the the labs, however, both of which have in common of: 1) making a recursion call at each depth, 2) for loop iterating through each element within that depth.
as such, since an universal algorithm is established above, one can easily see that, at the very least, a tree can be used to represent directories and subdirectories of information. using folders and subfolders in our computer is a classic example.
even though (at our current level of computer science) we have only seen numbers in each node, i firmly believe that the use of the properties of implementing a tree can become very useful when storing information in a computer that is just as complex as the structure of a tree itself.
a property of such a diagram includes:
nodes
the root
path
length
leaf
internal node
height
depth
arity.
even though the "look" like an unorganized list, in order to construct a tree object using OOP, (at least ) python recognizes key worlds "value" as the root and "children" as its branches when declared in the initializer.
although we have not encountered a situation where a tree can be used to solve real computer science problems, it is not a stretch to say that there are "ideas" that can be represented by trees if you were to see how to sort (or, traverse) through one:
this goes back to the idea that a tree in python can look like an unorganized nested list. as such, one should build a recursive function to traverse through it.
there are (so far) two implementations of functions that we have worked on the the labs, however, both of which have in common of: 1) making a recursion call at each depth, 2) for loop iterating through each element within that depth.
as such, since an universal algorithm is established above, one can easily see that, at the very least, a tree can be used to represent directories and subdirectories of information. using folders and subfolders in our computer is a classic example.
even though (at our current level of computer science) we have only seen numbers in each node, i firmly believe that the use of the properties of implementing a tree can become very useful when storing information in a computer that is just as complex as the structure of a tree itself.
Monday, 2 February 2015
sLog 5: recursion
Assigned topic: Recursion.
At this point, i have had my first exposure to recursion, a powerful technique in computer programming.
According to wikipedia,
"Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration)."
Simply put, recursion technique is seen when the function being run calls itself within its own code (because the function calls itself to start its work again on the given input).
The following code illustrates an example of recursion (stolen from week 4 lecture slides):
def rec_max(L):
return max([rec_max(x) if isinstance(x, list) else x for x in L])
This function sorts through a given list input and returns the greatest value within the list.
The most important component of any recursive call is its "base case." This is the condition in which the function has to reach so that it terminates and stops running. Otherwise, python will return a "recursion exceeds maximum depth" error.
The closest analogy that comes to my mind is the concept of a "while loop," because it is also an iteration technique that keeps running and running until it reaches a condition in which it stops. Likewise, the while loop faces the same problem of an "infinite loop" if its exit condition is not well defined.
So, it begs the question, what is the point of recursion when there already exists a similar technique that does the same job?
Refer to the rec_max(L) function above.
If the given input is a list of [1, 2, 3, 4, 5], the function would return 5. A very simple test case which either the for loop or while loop can easily accomplish.
However, what if the given input is something like: [1, [2, 3, 4], 5]?
A for loop, for example, would iterate through: 1, the inner list, then 5, and return 5, with no regard for the content of the inner list - for its assigned objective does not directly deal with such a disposition.
Even if you were to install a command to the effect of "if you encounter another list, start the iteration again," it is still not going to account for an input which has 99 layers (an exaggerated point) of nested lists.
This is where recursion comes in.
the 1 line code above in english means "if you encounter another list, start the iteration again." The code re-executes itself given the condition is met. In the example of the nested list, the only (known) way to dealing with an ADT that contains layers and layers of variables is to start the count again, as if you were to do it manually.
This is where recursion becomes indispensable: when the input ADT consists of entries that are not of the same format.
Recursion, at its base definition, is a form of loop. A loop is a command to the computer to execute code over and over again until the condition is met. However, recursion allows itself to start the iteration again if it becomes necessary. But, in general, a recursion should always be used when a big problem needs to be broken down into small problems and solved step by step. ex. decomposing a big list into smaller lists and iterating through each item to return the desired entry.
In brief, recursion is a powerful tool in computer science that allows the computer to solve complicated problems by breaking it down into smaller ones via. starting the iteration again - very useful when the given input ADT is not of a consistent format.
At this point, i have had my first exposure to recursion, a powerful technique in computer programming.
According to wikipedia,
"Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration)."
Simply put, recursion technique is seen when the function being run calls itself within its own code (because the function calls itself to start its work again on the given input).
The following code illustrates an example of recursion (stolen from week 4 lecture slides):
def rec_max(L):
return max([rec_max(x) if isinstance(x, list) else x for x in L])
This function sorts through a given list input and returns the greatest value within the list.
The most important component of any recursive call is its "base case." This is the condition in which the function has to reach so that it terminates and stops running. Otherwise, python will return a "recursion exceeds maximum depth" error.
The closest analogy that comes to my mind is the concept of a "while loop," because it is also an iteration technique that keeps running and running until it reaches a condition in which it stops. Likewise, the while loop faces the same problem of an "infinite loop" if its exit condition is not well defined.
So, it begs the question, what is the point of recursion when there already exists a similar technique that does the same job?
Refer to the rec_max(L) function above.
If the given input is a list of [1, 2, 3, 4, 5], the function would return 5. A very simple test case which either the for loop or while loop can easily accomplish.
However, what if the given input is something like: [1, [2, 3, 4], 5]?
A for loop, for example, would iterate through: 1, the inner list, then 5, and return 5, with no regard for the content of the inner list - for its assigned objective does not directly deal with such a disposition.
Even if you were to install a command to the effect of "if you encounter another list, start the iteration again," it is still not going to account for an input which has 99 layers (an exaggerated point) of nested lists.
This is where recursion comes in.
the 1 line code above in english means "if you encounter another list, start the iteration again." The code re-executes itself given the condition is met. In the example of the nested list, the only (known) way to dealing with an ADT that contains layers and layers of variables is to start the count again, as if you were to do it manually.
This is where recursion becomes indispensable: when the input ADT consists of entries that are not of the same format.
Recursion, at its base definition, is a form of loop. A loop is a command to the computer to execute code over and over again until the condition is met. However, recursion allows itself to start the iteration again if it becomes necessary. But, in general, a recursion should always be used when a big problem needs to be broken down into small problems and solved step by step. ex. decomposing a big list into smaller lists and iterating through each item to return the desired entry.
In brief, recursion is a powerful tool in computer science that allows the computer to solve complicated problems by breaking it down into smaller ones via. starting the iteration again - very useful when the given input ADT is not of a consistent format.
Sunday, 25 January 2015
sLog 4: why geeks should write?
In elementary school we are taught: a sentence is a complete thought, with an object and a verb. To write thoughts down solidifies it, makinng it concrete. Even if it is wrong, it can be reviewed by someone else and corrected.
In computer science, writing down thoughts may be just as (if not more) important than writing down code.
In my view, computer science is a lot like mathematics, in a sense that it starts off with the most basic concepts: if, for, while, recursion, and ideas stacks on top of ideas on top of ideas. While i am not introduced to the later more complex ideas yet, I do believe that the current material lays a foundation that will become useful in making sense of the material to come. So, why is it important to write (journals)? Answer: to keep track of what you have learned - to solidify your foundation - to have them reviewed by someone who knows what they are doing - so that one day when you are stuck on something more complicated, you can come back to it for review.
If learning is a jouney, writing down thoughts is like drawing a map for yourself that you do not get lost later on.
In computer science, writing down thoughts may be just as (if not more) important than writing down code.
In my view, computer science is a lot like mathematics, in a sense that it starts off with the most basic concepts: if, for, while, recursion, and ideas stacks on top of ideas on top of ideas. While i am not introduced to the later more complex ideas yet, I do believe that the current material lays a foundation that will become useful in making sense of the material to come. So, why is it important to write (journals)? Answer: to keep track of what you have learned - to solidify your foundation - to have them reviewed by someone who knows what they are doing - so that one day when you are stuck on something more complicated, you can come back to it for review.
If learning is a jouney, writing down thoughts is like drawing a map for yourself that you do not get lost later on.
sLog 6: object oriented programming
The first few weeks of csc148 were good review. However, I was also introduced to a new concept: Object Oriented Programming. In the past, I have only thought of programs as simple machines that takes in input and spits out something else. Object Oriented Programming is exactly what it sounds like: you use code to create "objects."These objects contain characteristics that are executed by functions. It may only seem like a way to organize code, but it operates with efficiency far beyond that.
An example of such is a game, such as subtract square that our group has already been working on. a super class is a game object (almost like a game console, even though i have never owned one) is a platform which the game operates on. The platform contains atributes which the game operates on. The game itself, Subtract Square, is a module that is attached onto the superclass (the "platform"). Attributes that are common across every "game" (such as: the turn, the score, the game over state) are embedded in the super class (platform) and inherited to every game (module).
Even though not thoroughly covered in class, my curiosity has led to the "why's" of OOP via. google, and there are a few which i found profound:
1. Code reuse. example: since every game has almost the same characteristics, the platform can have multiple games attached to it.
2. Encapsulation (csc207 concept). Hiding code from the next software engineer so that they are not tampering with things that might cause problems. Useful when working in teams.
I believe in education. However, I want to also believe that the techniques I am learning in "practical" courses can be applied within the industry.
In brief, Object Oriented Programming has been taught to me in such a way that i am beginning to understand software development process. It is a concept that I am currently learning to apply in my assignments and I believe will be here for the next few decades.
An example of such is a game, such as subtract square that our group has already been working on. a super class is a game object (almost like a game console, even though i have never owned one) is a platform which the game operates on. The platform contains atributes which the game operates on. The game itself, Subtract Square, is a module that is attached onto the superclass (the "platform"). Attributes that are common across every "game" (such as: the turn, the score, the game over state) are embedded in the super class (platform) and inherited to every game (module).
Even though not thoroughly covered in class, my curiosity has led to the "why's" of OOP via. google, and there are a few which i found profound:
1. Code reuse. example: since every game has almost the same characteristics, the platform can have multiple games attached to it.
2. Encapsulation (csc207 concept). Hiding code from the next software engineer so that they are not tampering with things that might cause problems. Useful when working in teams.
I believe in education. However, I want to also believe that the techniques I am learning in "practical" courses can be applied within the industry.
In brief, Object Oriented Programming has been taught to me in such a way that i am beginning to understand software development process. It is a concept that I am currently learning to apply in my assignments and I believe will be here for the next few decades.
Subscribe to:
Posts (Atom)