My third blog post was about recursion. You can tell I was not prepared to write about recursion at the time since I had to Google it in the first place. Here's the post:
http://sloglogblogslog.blogspot.ca/2015/02/week-4-recursion.html
Now that I have been working with recursion for longer, I can safely say that thinking about it only makes my brain sore rather than the searing pain it used to cause. So, let's get a little more in depth, and walk through the process of writing a recursive function, and explain why it works.
Let's say we want to write a function that takes a nested list of integers, which could be lists within lists within lists but ultimately they contain integers, and sums them all up. The first thing we want to do when writing a recursive function is decide what the function should do if no recursion is required. In this case, a single integer would be the simplest input, in which case we should simply return the integer. But we should only do this if the input is an integer, so we get:
def recursive(m):
if type(m) == int:
return m
Now we need to know what to do when we are given a list. This would be as simple as summing up the values in the list, which we can do with a default python function.
def recursive(m):
if type(m) == int:
return m
else:
return sum(m)
Unfortunately this will only work for integers and flat lists. Let's see what we would write for a list of lists.
def recursive(m):
if type(m) == int:
return m
else:
return sum([sum(x) for x in m])
Now for a list of list of lists...
def recursive(m):
if type(m) == int:
return m
else:
return sum([sum([sum(y) for y in x]) for x in m])
You can see that this isn't very good, as the expression will just keep getting longer and longer, and will only work for exactly the right kind of list. This is where recursion saves the day.
def recursive(m):
if type() == int:
return m
else:
return sum([recursive(x) for x in m])
This seems almost too good to be true. How is there such little code? How is this even supposed to do what we expect it to? Well, let's trace an example.
>>> m = [2, 4, [2, 6], [[4]]]
>>> recursive(m)
-> sum([recursive(2), recursive(4), recursive([2, 6]),
recursive([[4]])])
We already know that recursive(2) and recursive(4) will return their inputs, so lets keep breaking down what this function is doing.
-> sum([2, 4, sum([recursive(2), recursive(6)]),
sum([recursive([4])])])
-> sum([2, 4, 8, 4]) -> 18
As can be seen, recursion is witchcraft and is only practiced by those wicked of heart.
Thursday, April 9, 2015
Impressions of Week 9
The lab this week had to do binary search trees. In my post "Impressions of Week 7" I summarized what a binary tree was, and mentioned that a binary search tree could be searched more efficiently due to the fact that not every node has to be visited. To elaborate on this, say we have a binary tree such that all of the nodes' data are integers. To the left of each node is a sub-tree (also a binary search tree) where all its nodes contain data that is less than its root, and to the right is a sub-tree (also a binary search tree) containing nodes that have data that is greater than its root. If you are searching for the value 7 in a binary search tree with a root containing the value 15, only one half of the tree needs to be traversed, which would be the left side as the right side only contains values greater than 15. This makes binary search trees much more efficient, as finding values is faster than if it was a flat list.
As an example, here is a visual representation of a binary tree. Let's say we are looking for the value 200. If we used pre-order traversal, we would need to look at 14 nodes before we get to 200 (90, 50, 20, 5, 25, 75, 66, 80, 150, 95, 92, 111, 175, 166, 200). By traversing this as a binary search tree, we would only need to look at 3 nodes before arriving at 200 (90, 150, 175, 200). Looking at the first node, we go to the right since 200 > 90. 200 is also greater than 150 so we go on to 175, where 200 is once again somewhere to the right, and there it is at the end. That's 11 nodes that did not even have to be looked at, which may not seem like much, but if the tree was massive then it could save a lot of time.
Another neat thing about binary search trees is that the data it contains does not have to be numbers, it can be any kind of data as long as its comparable. This could have many applications that would make searching algorithms much more efficient in a variety of useful programs, especially if the number of data entries is extremely large.
Sunday, March 29, 2015
Impressions of Week 8
In this week, we had some very exciting things going on, such as the heart-pounding race to finish assignment 2 before 10:00 pm on Thursday and an unguided session of wracking our brains over lab #7. While it does feel nice to not go to labs, it's starting to take its toll. This class is starting to feel more and more like my high school programming class which went something like this: "Here's your assignment, now go teach yourself how to code!" Not that I had a problem with this in high school, but perhaps CSC148 material isn't that easy to figure out on your own.
Assignment 2 was pretty straightforward in terms of making the Tippy game, and so far it's the closest we've come to actually making graphics for a game, if you can call the grid made out of text 'graphics.' My grids looked something like this:
0 1 2 3
0 / / / /
1 / / x /
2 o o o /
3 / / / x
I'd say my greatest accomplishment was to add numbers to indicate columns and rows, so the player doesn't have to count for himself like some sort of peasant.
As for the Minimax strategy, I'm pretty sure it works but I don't remember how I completed it or how it works, that memory is suppressed until I'll probably need it in assignment 3.
Mandatory Acknowledgement of Other Slogs
http://initializationcomplete.blogspot.ca/
When I first looked at this SLOG, I was blown away. The style of writing, the comprehensive understanding this student displays of CSC148 content, it's almost perfect! The only possible flaw I could find here is that there isn't a single post, but surely that's only a small imperfection.
http://thecstists.blogspot.ca/
One of the great things about this SLOG is that this student actually talked about linked lists, unlike me, because I only talked about A2 in my week 8 post. Even better is that this student actually walks us through their learning process, starting with a concept they had difficulty understanding, and outlining how they figured out the problem. For example, they talked about how they couldn't quite comprehend how the 'append' method is implemented in a linked list, and goes through the steps of how they finally understood it.
Sunday, March 15, 2015
Impressions of Week 7 + Other SLOGS
In week 7, we learned about Binary Trees, and Binary Search Trees. This is actually a simple concept in itself. There is a node with data, and it references up to two other nodes: left and right. These referenced nodes could also contain left and right nodes, and those could also contain left and right nodes, and so on. Here is a representation of a binary tree, which as you can see starts with a root, and then branches out into left and right nodes.
This tree is labeled 'Full Binary Tree' because each node actually references two other nodes, except for the leaves (nodes at the very end). A tree like this could also be a binary search tree, which would have to satisfy the following properties: the data contained in each node must be comparable (like integers), the data in the left node must be less than that of its root, and the data in the right node must be greater than its root. Now, the reason this is called a binary SEARCH tree is because this data structure can be searched more efficiently than a list. If you want to find all the numbers within a certain range on a binary search tree, you don't have to visit every node because a search algorithm would know not to visit nodes that will not contain the data its looking for.
And now for the mandatory acknowledgement of other SLOGS:
http://cslogcs148.blogspot.ca/
First off, this URL is very unimaginative. I can already tell just from the URL that this is going to be very dull yet informative...
...well it is informative, I'll give it that. However, this one part bothered me: "The computer is way smarter than a1 now, you can hardly beat it :D" (in reference to the minimax strategy we implemented in a2). What kind of n00b loses to a bot? You gotta step up your game.
http://joshpinkney-csc148.blogspot.ca/
Still a boring URL, but at least it's personalized with the author's name. I particularly like the examples he uses when talking about class inheritance:
>>> horse = horse("Jim", "Black")
>>> horse.noise()
"NEEEEIIIIIIGGGGHHHHHH"
>>> cow = cow("Bob", "White with Black spots")
>>> cow.noise()
"MOOOOOOOOOOOOOOOOOOOOO"
>>> piggy = pig("Timothy", "Pink")
>>> piggy.noise()
"OINK OINK"
I think that this might be the most useful program I have ever encountered, because I always seem to forget what noise a horse makes.
This tree is labeled 'Full Binary Tree' because each node actually references two other nodes, except for the leaves (nodes at the very end). A tree like this could also be a binary search tree, which would have to satisfy the following properties: the data contained in each node must be comparable (like integers), the data in the left node must be less than that of its root, and the data in the right node must be greater than its root. Now, the reason this is called a binary SEARCH tree is because this data structure can be searched more efficiently than a list. If you want to find all the numbers within a certain range on a binary search tree, you don't have to visit every node because a search algorithm would know not to visit nodes that will not contain the data its looking for.
And now for the mandatory acknowledgement of other SLOGS:
http://cslogcs148.blogspot.ca/
First off, this URL is very unimaginative. I can already tell just from the URL that this is going to be very dull yet informative...
...well it is informative, I'll give it that. However, this one part bothered me: "The computer is way smarter than a1 now, you can hardly beat it :D" (in reference to the minimax strategy we implemented in a2). What kind of n00b loses to a bot? You gotta step up your game.
http://joshpinkney-csc148.blogspot.ca/
Still a boring URL, but at least it's personalized with the author's name. I particularly like the examples he uses when talking about class inheritance:
>>> horse = horse("Jim", "Black")
>>> horse.noise()
"NEEEEIIIIIIGGGGHHHHHH"
>>> cow = cow("Bob", "White with Black spots")
>>> cow.noise()
"MOOOOOOOOOOOOOOOOOOOOO"
>>> piggy = pig("Timothy", "Pink")
>>> piggy.noise()
"OINK OINK"
I think that this might be the most useful program I have ever encountered, because I always seem to forget what noise a horse makes.
Saturday, February 28, 2015
Monday, February 23, 2015
Object Oriented Programming Concept Summary
So far, we have learned how to create classes, subclasses, methods, and how to implement these in the proper style for both readability and efficiency. But how does this relate to object oriented programming? While we're at it, what is object oriented programming? Well to answer that, we must first define what we mean by an 'object' in the context of computer programming.
An object is essentially a chunk of data; ones and zeros grouped together, represented in a way that humans can understand. For example, a variable in python: NUMBER = 2. As we can see, the variable refers to the integer 2. It also refers to a memory address in the computer, since the variable and the value it represents must be kept track of. It gets much more complicated than just simple variables, as complex classes containing multitudes of data types and information, which are all represented as a single object. At its lowest level, it is just a series of incomprehensible data, but object oriented programming groups it into something that humans can understand, and from there data can be manipulated.
Speaking of manipulating data, this is what functions are for. They might not necessarily manipulate data, but they perform an action with the data. It could represent the data in a certain way, or it could write the data to a file. An object class is a group of functions called methods. The class can be used as an object, and the methods within the class determine how it stores and manipulates data. Typically, there is an __init__ method, which is short for 'initialize,' as that is exactly what the method does. It performs certain actions that allow the object to work. Usually included are a __str__ method (returns a string representation of the object, meant to be readable by the user) and a __repr__ method (a representation that is unambiguous, a raw representation of the data for the use of the programmer). Finally, there might be an __eq__ method, which just compares two objects of the same type. Not all of these methods are implemented in every class. Sometimes it wouldn't be applicable to give a string representation of an object, or perhaps the method is implemented in a subclass.
A subclass is a class that inherits its base features from another class. For example, one would make a generic class to keep track of names, and implement a subclass for the names organized by first name, and one for the names organized by last name. Having generic classes makes the code easier to read, and allows the code to be reused in the future if more subclasses are to be implemented.
Through the use of class objects, very complex programs can be constructed, from video games to integral calculators. Or a video game where the user solves integrals, or an AI that uses integrals to beat video games, or a program that calculates the... okay that's enough, I hope you've enjoyed this summary of object oriented programming in python.
An object is essentially a chunk of data; ones and zeros grouped together, represented in a way that humans can understand. For example, a variable in python: NUMBER = 2. As we can see, the variable refers to the integer 2. It also refers to a memory address in the computer, since the variable and the value it represents must be kept track of. It gets much more complicated than just simple variables, as complex classes containing multitudes of data types and information, which are all represented as a single object. At its lowest level, it is just a series of incomprehensible data, but object oriented programming groups it into something that humans can understand, and from there data can be manipulated.
Speaking of manipulating data, this is what functions are for. They might not necessarily manipulate data, but they perform an action with the data. It could represent the data in a certain way, or it could write the data to a file. An object class is a group of functions called methods. The class can be used as an object, and the methods within the class determine how it stores and manipulates data. Typically, there is an __init__ method, which is short for 'initialize,' as that is exactly what the method does. It performs certain actions that allow the object to work. Usually included are a __str__ method (returns a string representation of the object, meant to be readable by the user) and a __repr__ method (a representation that is unambiguous, a raw representation of the data for the use of the programmer). Finally, there might be an __eq__ method, which just compares two objects of the same type. Not all of these methods are implemented in every class. Sometimes it wouldn't be applicable to give a string representation of an object, or perhaps the method is implemented in a subclass.
A subclass is a class that inherits its base features from another class. For example, one would make a generic class to keep track of names, and implement a subclass for the names organized by first name, and one for the names organized by last name. Having generic classes makes the code easier to read, and allows the code to be reused in the future if more subclasses are to be implemented.
Through the use of class objects, very complex programs can be constructed, from video games to integral calculators. Or a video game where the user solves integrals, or an AI that uses integrals to beat video games, or a program that calculates the... okay that's enough, I hope you've enjoyed this summary of object oriented programming in python.
Sunday, February 8, 2015
Week 4: Recursion
Ah yes, recursion, an absolutely fascinating tool that is used in programming for the sole purpose of drawing trees. So what is recursion? Let me just look that up...
Wait, I swear I spelled that correctly. Why would Google say "Did you mean: recursion?" Oh I get it. Real funny Google, but there goes 20 minutes of my life trying to figure out what was wrong.
As Wikipedia has said, recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem. In CSC148 we would be given a recursive function, which generally involves using the function itself within the function definition to produce a result. We would be given a function, an input, and be asked to trace the result. As expected, there were function calls within function calls within function calls within function calls... And it really hurt my brain. Luckily, the whole point of computers is to compute things that we don't have to, so I can just let my computer's processor take the brunt of the calculations.
Subscribe to:
Posts (Atom)