First, a note to the TA: On the right side of the blog page is a list of blogs that I have been following and commenting on.
Overall, I thoroughly enjoyed this course. At the beginning of the course, we learned about class design and Object-oriented programming which I found very interesting and was familiar with from CSC108. When we started recursion, I was initially confused, but by working through the lab exercises and assignments, I became more comfortable writing various recursive functions. After recursion we moved on to LinkedLists which are iterable functions. This was a nice break from a recursive-heavy course. Finally we talked about algorithm analysis and Big O. I had previously been exposed to this concept in CSC165 and this topic was mainly review as we did not go into much detail like we did in CSC165.
I found the assignments challenging but not too difficult. Assignment 2 was by far the hardest of the three assignments, whereas I found Assignments 1 and 3 to be relatively equal in terms of difficulty.
Despite the fact that the strike cancelled four of the labs, I found the first few very helpful in understanding the material presented in class, especially the labs about recursion, trees, and binary trees/ binary search trees.
Thursday, 2 April 2015
Sunday, 29 March 2015
Reflecting on Trees and Binary Trees
In an earlier post, I wrote that I preferred working with binary trees and binary search trees than with trees, because I could make assumptions about the number of children of each node, rather than dealing with a tree with a random number or arrangement of children per node.
Although my view hasn't really changed, after finishing Assignment 3, I have a better understanding of how trees work and how to implement functions that use them. Even though I still prefer binary trees, I feel much more comfortable now working with trees than I did when I wrote the earlier post. The grow function in Assignment 3 especially helped my understanding of trees because it required the construction of a tree from scratch. Similar to when I wrote my first recursive function, writing the grow function with my group members allowed me to explore the construction of trees which made it easier to implement the remaining functions.
I decided to ask my group members what they thought of binary trees vs. trees. One preferred binary trees because of the assumptions you can make when accessing the items in the tree, while the other preferred working with trees because they were more versatile as you are not limited in the branching factor of the tree.
Although my view hasn't really changed, after finishing Assignment 3, I have a better understanding of how trees work and how to implement functions that use them. Even though I still prefer binary trees, I feel much more comfortable now working with trees than I did when I wrote the earlier post. The grow function in Assignment 3 especially helped my understanding of trees because it required the construction of a tree from scratch. Similar to when I wrote my first recursive function, writing the grow function with my group members allowed me to explore the construction of trees which made it easier to implement the remaining functions.
I decided to ask my group members what they thought of binary trees vs. trees. One preferred binary trees because of the assumptions you can make when accessing the items in the tree, while the other preferred working with trees because they were more versatile as you are not limited in the branching factor of the tree.
Sunday, 15 March 2015
Week 9
This week we learned about deleting and modifying binary trees. Originally, the code was a bit confusing to me, but after the professor outlined the algorithm step-by-step in english it became more clear.
We only had one lecture this week because the second term-test was on Wednesday. Despite having done well on the first test, I was still nervous for this one. As I expected, this test was harder than the first one, although I still think I did fairly well. My aid sheet was very helpful as it provided me with hints for two of the questions on the test.
We only had one lecture this week because the second term-test was on Wednesday. Despite having done well on the first test, I was still nervous for this one. As I expected, this test was harder than the first one, although I still think I did fairly well. My aid sheet was very helpful as it provided me with hints for two of the questions on the test.
Thursday, 12 March 2015
Week 8
This week we learned about linked lists, which are a special type of list made up of nodes that reference other nodes. In this way, each of the nodes are linked together. I originally found the concept confusing, but after drawing pictures and practising some of the lab exercises I had a better understanding of the order in which to perform the operations in my code so as not to lose any essential data from the list.
Assignment 2 was also due this week. My group and I had only three functions left to complete: minimax, winner, and rough_outcome. Minimax worked with subtract square, but we had yet to test it with a game of tippy. I realized that our original solution for checking for a tippy was inefficient and would take too long to write and debug. Therefore, I suggested that we only check for horizontal tippys and then rotate the board four times and return whether a tippy is found. Using this code, we only had to deal with the two cases of horizontal tippys rather than the four cases we had to account for prior to my suggestion. We worked out a few errors in the code, such as where it would not detect a tippy in a large compact group of X's or O's, or where it would only detect the first tippy in a row and not all the tippy's. For example, before debugging, our code would incorrectly return on the following boards:
X|X|X|X|
X|X|X|X|
X|X|X|X|
O|O|O|O|
and
X|X|O|O|X|X|O|
O|X|X|O|O|X|X|
X|O|X|O|X|O|X|
O|X|O|X|O|X|O|
X|O|X|O|X|O|X|
O|X|O|X|O|X|O|
X|O|X|O|X|O|X|
After completing winner, we found out, much to our dismay, that minimax did not work correctly for a game of tippy. Luckily, we had lots of time to find the errors and fix them, and we did so fairly quickly. We then implemented rough_outcome without any major errors, although we were not concerned about that function as it wasn't used in the assignment. After fixing some more minor errors, we ran our code multiple times with a game of tippy and it correctly picked the middle square on a 3X3 grid every time.
Assignment 2 was also due this week. My group and I had only three functions left to complete: minimax, winner, and rough_outcome. Minimax worked with subtract square, but we had yet to test it with a game of tippy. I realized that our original solution for checking for a tippy was inefficient and would take too long to write and debug. Therefore, I suggested that we only check for horizontal tippys and then rotate the board four times and return whether a tippy is found. Using this code, we only had to deal with the two cases of horizontal tippys rather than the four cases we had to account for prior to my suggestion. We worked out a few errors in the code, such as where it would not detect a tippy in a large compact group of X's or O's, or where it would only detect the first tippy in a row and not all the tippy's. For example, before debugging, our code would incorrectly return on the following boards:
X|X|X|X|
X|X|X|X|
X|X|X|X|
O|O|O|O|
and
X|X|O|O|X|X|O|
O|X|X|O|O|X|X|
X|O|X|O|X|O|X|
O|X|O|X|O|X|O|
X|O|X|O|X|O|X|
O|X|O|X|O|X|O|
X|O|X|O|X|O|X|
After completing winner, we found out, much to our dismay, that minimax did not work correctly for a game of tippy. Luckily, we had lots of time to find the errors and fix them, and we did so fairly quickly. We then implemented rough_outcome without any major errors, although we were not concerned about that function as it wasn't used in the assignment. After fixing some more minor errors, we ran our code multiple times with a game of tippy and it correctly picked the middle square on a 3X3 grid every time.
Thursday, 5 March 2015
Week 7
Last week we learned about binary trees and binary search trees. Binary trees are a special type of tree where each node only has two children, a left value and a right value. Binary search trees are a special type of binary tree where the left child of the node contains a value that is less than that of the node and the right child of the node contains a value that is greater than the value of the node. With a tree in this configuration, it is easy and efficient to search for values as the computer does not have to look at all of the nodes, only the ones that are greater than the value being searched for.
I found it easier to implement methods for binary trees and binary search trees than for regular trees because I could assume that each node has only two children and I could directly access each node's left and right values, instead of having only a list of the children on the main node to work with, as is the case with trees.
My group members and I also began work on assignment 2 this week and managed to write most of the tippy game state as well as a version of minimax that worked with subtract square. However, we were having trouble with figuring out an efficient way to detect all the possible tippy arrangements on any board size, and thus couldn't test our minimax function with a game of tippy.
I found it easier to implement methods for binary trees and binary search trees than for regular trees because I could assume that each node has only two children and I could directly access each node's left and right values, instead of having only a list of the children on the main node to work with, as is the case with trees.
My group members and I also began work on assignment 2 this week and managed to write most of the tippy game state as well as a version of minimax that worked with subtract square. However, we were having trouble with figuring out an efficient way to detect all the possible tippy arrangements on any board size, and thus couldn't test our minimax function with a game of tippy.
Sunday, 1 March 2015
Summary Topic to be Graded
As I have already written a summary of Object-Oriented Programming and Abstract Data Types I would like my summary of Object-Oriented Programming to be Graded. It is paragraphs one to three of the post entitled: A Summary of Object-Oriented Programming and Abstract Data Type, which can be found here.
Sunday, 22 February 2015
A Summary of Object-Oriented Programming and Abstract Data Types
Object-oriented programming, as its name suggests, deals with objects that contain data, and code, which is implemented as methods. In this course, we dealt with classes and inheritance.
A class is an object that contains code in the form of methods, that can be implemented for any instance of the class. An example of a class and its methods is a class for a day planner. Every instance of the class is a day, and the class might contain methods that add an event, remove an event, and one that checks to see if any events overlap, in addition to an initializer method which creates instances of the class. These methods execute properly for any instance of the class (which is a day) and this class structure is much more efficient than writing separate functions that are not connected as it often requires less code and is more ordered.
Some problems, however, require more complex solutions that just one class. In the case where instances of a class share methods, but not the implementation of those methods, inheritance may be used. A simple example of inheritance that deals with shapes was shown in lecture. The shape class has a method that initializes a shape, one that stores the starting coordinates of the shape, one that calculates the perimeter, and one that calculates the area. While all shapes share these properties, only the method that stores the starting coordinates of the shape will execute properly regardless of the type of shape created. Both the perimeter and area methods are specific to the type of shape created. In this case, subclasses for each shape are created and inherit shared methods from the general shape superclass. The intializer and coordinate methods would be implemented in the superclass because they are shared with all shapes, while the perimeter and area methods would be left unimplemented in the superclass and would raise an error if called saying that a subclass is needed. In the subclasses, the coordinate method would not need to be implemented because it is inherited from the superclass, but the area and perimeter methods can be implemented differently in each shape's subclass. This process is much more efficient than creating separate classes for each shape, especially in larger cases, because it prevents duplication of shared code (the coordinate method would have to be duplicated in every separate class without inheritance) and is more organized.
This course also introduced three new abstract data types so far: stacks, queues, and trees.
Stacks are a last-in-first-out data type that can be envisioned as a stack of paper on a desk. Items can be added on top of the stack, but only the top item can be removed first, or the stack of paper will collapse. Generally, stacks have three key methods aside from the initializer: a method to check if the stack is empty, a method to add an item on top of the stack, and a method to remove and return the top item on the stack.
Queues are similar to stacks except they are a first-in-first-out data type, similar to a line at a cashier. They contain the same key methods as stacks, except the implementation is slightly different.
Trees are a recursive data type, meaning each tree is made up of smaller subtrees. An example of a tree can be created by flipping a coin and recording the possible results. After one flip, the possibilities are only heads and tails, after flipping the coin again, each possibility from before now also has two possibilities. Due to the recursive nature of trees, many of the methods implemented in a tree class also require recursion, such as determining the end values of the tree (the leaves) the number of intermediate values (nodes), or the maximum height of the tree.
A class is an object that contains code in the form of methods, that can be implemented for any instance of the class. An example of a class and its methods is a class for a day planner. Every instance of the class is a day, and the class might contain methods that add an event, remove an event, and one that checks to see if any events overlap, in addition to an initializer method which creates instances of the class. These methods execute properly for any instance of the class (which is a day) and this class structure is much more efficient than writing separate functions that are not connected as it often requires less code and is more ordered.
Some problems, however, require more complex solutions that just one class. In the case where instances of a class share methods, but not the implementation of those methods, inheritance may be used. A simple example of inheritance that deals with shapes was shown in lecture. The shape class has a method that initializes a shape, one that stores the starting coordinates of the shape, one that calculates the perimeter, and one that calculates the area. While all shapes share these properties, only the method that stores the starting coordinates of the shape will execute properly regardless of the type of shape created. Both the perimeter and area methods are specific to the type of shape created. In this case, subclasses for each shape are created and inherit shared methods from the general shape superclass. The intializer and coordinate methods would be implemented in the superclass because they are shared with all shapes, while the perimeter and area methods would be left unimplemented in the superclass and would raise an error if called saying that a subclass is needed. In the subclasses, the coordinate method would not need to be implemented because it is inherited from the superclass, but the area and perimeter methods can be implemented differently in each shape's subclass. This process is much more efficient than creating separate classes for each shape, especially in larger cases, because it prevents duplication of shared code (the coordinate method would have to be duplicated in every separate class without inheritance) and is more organized.
This course also introduced three new abstract data types so far: stacks, queues, and trees.
Stacks are a last-in-first-out data type that can be envisioned as a stack of paper on a desk. Items can be added on top of the stack, but only the top item can be removed first, or the stack of paper will collapse. Generally, stacks have three key methods aside from the initializer: a method to check if the stack is empty, a method to add an item on top of the stack, and a method to remove and return the top item on the stack.
Queues are similar to stacks except they are a first-in-first-out data type, similar to a line at a cashier. They contain the same key methods as stacks, except the implementation is slightly different.
Trees are a recursive data type, meaning each tree is made up of smaller subtrees. An example of a tree can be created by flipping a coin and recording the possible results. After one flip, the possibilities are only heads and tails, after flipping the coin again, each possibility from before now also has two possibilities. Due to the recursive nature of trees, many of the methods implemented in a tree class also require recursion, such as determining the end values of the tree (the leaves) the number of intermediate values (nodes), or the maximum height of the tree.
Subscribe to:
Posts (Atom)