I have come to the end of another school year and another SLOG. I really can't believe that I'm almost finished my first year of university. I still think that it's 2010 sometimes and that I never really left middle school.
I really hope I did well on assignments 2 and 3. It's really hard writing and handing in an assignment when I don't know the marks for my SLOG or previous assignment. I think that I did well on assignment 3, but it seemed to be a little too easy. I did part B, and while it took a lot of helper functions, I finished it rather easily. Some other students really struggled with part A. I hate when this happens because I always think that I did something wrong, but we'll see how it goes.
I learned a lot in this course, and I am really happy with it. I rarely feel like I actually learn anything from a course I take. At the end of most school years I often end up feeling like I just memorized a bunch of facts, spit them out on tests, and then I forget everything. I think that what I learned in CSC148 will stick with me for a while to come. I think that I now have a much better grasp of recursion, and I now really understand abstract data types. I see some of the practical applications of what I learned in CSC165 and I am finally starting to think about the more abstract science part of computer science instead of just programming. I have also learned the importance of doing stuff on paper as I commented here.
Tuesday, 7 April 2015
Monday, 30 March 2015
CSC148 Lecture Week 11
Looking Back
As I was studying for midterm number 2 I realized that the code I came up with for lab 6 and documented in my SLOG was actually quite redundant.
In lab 6 my solution to the list_longest_path function looked like this:
if node is None:
return []
elif is_leaf(node):
return [node.data]
I didn't really need all those nested if statements and the second if statement also was not necessary. I managed to come up with some simpler, easier to read code:
if node == None:
return []
else:
right = [node.data] + list_longest_path(node.right)
left = [node.data] + list_longest_path(node.left)
return right if len(right) > len(left) else left
I think that this SLOG entry and my SLOG overall really shows how I have learned and grown throughout the course. As another slogger has said, practice makes perfect. I have spend a lot of time practicing new recursion techniques and I think that I have a much better grasp of it now. I'm also really missing the labs that were cancelled due to the TA strike. They were a great place to practice and as another slogger points out, they were all about practicing our coding skills, and we never wasted time on pointless name games or team building activities.
As I was studying for midterm number 2 I realized that the code I came up with for lab 6 and documented in my SLOG was actually quite redundant.
In lab 6 my solution to the list_longest_path function looked like this:
if node is None:
return []
elif is_leaf(node):
return [node.data]
else:
if not node.left == None:
left = list_longest_path(node.left)
else:
left = []
if not node.right == None:
right = list_longest_path(node.right)
else:
right = []
return [node.data] + left if len(left) > len(right) else [node.data] + right
if not node.left == None:
left = list_longest_path(node.left)
else:
left = []
if not node.right == None:
right = list_longest_path(node.right)
else:
right = []
return [node.data] + left if len(left) > len(right) else [node.data] + right
I didn't really need all those nested if statements and the second if statement also was not necessary. I managed to come up with some simpler, easier to read code:
if node == None:
return []
else:
right = [node.data] + list_longest_path(node.right)
left = [node.data] + list_longest_path(node.left)
return right if len(right) > len(left) else left
I think that this SLOG entry and my SLOG overall really shows how I have learned and grown throughout the course. As another slogger has said, practice makes perfect. I have spend a lot of time practicing new recursion techniques and I think that I have a much better grasp of it now. I'm also really missing the labs that were cancelled due to the TA strike. They were a great place to practice and as another slogger points out, they were all about practicing our coding skills, and we never wasted time on pointless name games or team building activities.
Monday, 23 March 2015
CSC148 Lecture Week 10
This week we discussed testing. Specifically, we focused on testing the minimax strategy. If we were to test minimax with subtract square, there are certain test cases that would not help at all. There are a few numbers that will always result in a loss no matter what number the player picks. Wikipedia calls there 'cold numbers'. When coming up with test cases, cold numbers such as 10 or 15 would not be useful at all. Numbers such as 9 also may not inspire much confidence when used as test cases. If there are more winning moves then there are losing moves, then the random strategy would still work more than 50% of the time. Therefore when picking test cases, we would have to carefully consider the outcome of each case.
Monday, 16 March 2015
CSC148 Lecture Week 9
Last week we covered linked lists in class. Linked lists can be though of a tree with airity of one. Each node has a value and a reference to another node or None if it is the end of the list. A wrapper class can then be used to keep track of the size of the list, the front node and the back node. Recursion can be used to traverse linked lists, but due to the more linear nature of the lists iteration works just as well. A while loop or for loop can be used to step through the list until you get to the desired node. The basic structure would look something like this:
cur_node = lnk.front
while cur_node:
cur_node = cur_node.nxt
I liked going back to iteration. It was nice to be able to use loops again and not have to think in a recursive manner. Working with linked lists also involves mutation. It is important to change things in the correct order so that you don't lost data. I found this part of linked lists to be manageable. What I found difficult was remembering to change the front, back and size data in the wrapper. I created a check list for the test, so hopefully I did everything properly on the test.
Saturday, 7 March 2015
CSC148 Lecture Week 8
Assignment 2 was due this week, and I am very glad that I was able to finish it. When I first looked over the assignment, I though that it would be pretty easy so I didn't start anything until the Saturday before it was due. Coding TippyGameState was relatively easy. winner() and rough_outcome() were pretty long since my group just did that by brute force. On Piazza, Danny answered a question about winner() and said that there was no really elegant way for it to be implemented, so just decided to go through the whole board and check for all four possible tippies.
What really cause me trouble was minimax. My whole group had a lot of trouble with it and we came up with some really complicated methods that did not work. After taking a step back and rereading the assignment page, I realized that we were probably over-complicating it. The assignment handout pretty much gave us the exact algorithm for the minimax strategy:
What really cause me trouble was minimax. My whole group had a lot of trouble with it and we came up with some really complicated methods that did not work. After taking a step back and rereading the assignment page, I realized that we were probably over-complicating it. The assignment handout pretty much gave us the exact algorithm for the minimax strategy:
I then worked on translating this algorithm to code. I had trouble pairing the moves with their scores, but that was fixed with the help of a helper function (they're so helpful aren't they?).
The final problem was that minimax worked with subtract square and not tippy. It took a lot of tracing through the Wing debugger, but we eventually realized that apply_move() in TippyGameState was changing the original game state. This was fixed with the use of deepcopy() (Thanks again to Piazza).
Friday, 27 February 2015
CSC148 Lecture Week 7
I would like my summary of Object Oriented Programming concepts to be graded.
Lab 6 this week is the first lab that I really struggled with. The function list_longest_path asked us to write a function that would find the longest path in a binary tree and return that path. The starter code came with the following docstring examples:
>>> list_longest_path(None)
[]
>>> list_longest_path(BTNode(5))
[5]
>>> list_longest_path(BTNode(5, BTNode(3, BTNode(2), None), BTNode(7, BTNode(4, BTNode(9)), BTNode(6))))
[5, 7, 4, 9]
The first two examples give us the two base cases for the algorithm. When there is no tree at all, the longest path contains nothing. When only the root is present, the longest path is obviously just the root itself.
Translated into code this would be:
if node is None:
return []
elif is_leaf(node):
return [node.data]
The recursive case was what I really struggled with. I couldn't figure out how to keep track of all the data because we couldn't just find all possible paths, store them in a list and then look through that list, which is the type of recursion that we had been doing before. What really helped was one of my partner's ideas and actually drawing out the tree itself.
My partner, Wendy, realized that at each node we would need to look at the right node and the left node and then compare them. I then started walking through the tree starting at the root. Node 8 would ask Node 7, "What is your longest list?", then it would ask Node 1, "What is your longest list?". This would continue until a leaf was reached. The leaf would then know right off the bat that its longest path was itself. This information would then be sent back up the tree. The final piece of the puzzle was realizing that we would have to concatenate the data of the node itself to the data it was getting from it's children. This then lead to the final solution:
else:
if not node.left == None:
left = list_longest_path(node.left)
else:
left = []
if not node.right == None:
right = list_longest_path(node.right)
else:
right = []
return [node.data] + left if len(left) > len(right) else [node.data] + right
Another slogger also has a great explanation of recursion here.
Lab 6 this week is the first lab that I really struggled with. The function list_longest_path asked us to write a function that would find the longest path in a binary tree and return that path. The starter code came with the following docstring examples:
>>> list_longest_path(None)
[]
>>> list_longest_path(BTNode(5))
[5]
>>> list_longest_path(BTNode(5, BTNode(3, BTNode(2), None), BTNode(7, BTNode(4, BTNode(9)), BTNode(6))))
[5, 7, 4, 9]
The first two examples give us the two base cases for the algorithm. When there is no tree at all, the longest path contains nothing. When only the root is present, the longest path is obviously just the root itself.
Translated into code this would be:
if node is None:
return []
elif is_leaf(node):
return [node.data]
The recursive case was what I really struggled with. I couldn't figure out how to keep track of all the data because we couldn't just find all possible paths, store them in a list and then look through that list, which is the type of recursion that we had been doing before. What really helped was one of my partner's ideas and actually drawing out the tree itself.
My partner, Wendy, realized that at each node we would need to look at the right node and the left node and then compare them. I then started walking through the tree starting at the root. Node 8 would ask Node 7, "What is your longest list?", then it would ask Node 1, "What is your longest list?". This would continue until a leaf was reached. The leaf would then know right off the bat that its longest path was itself. This information would then be sent back up the tree. The final piece of the puzzle was realizing that we would have to concatenate the data of the node itself to the data it was getting from it's children. This then lead to the final solution:
else:
if not node.left == None:
left = list_longest_path(node.left)
else:
left = []
if not node.right == None:
right = list_longest_path(node.right)
else:
right = []
return [node.data] + left if len(left) > len(right) else [node.data] + right
Another slogger also has a great explanation of recursion here.
Tuesday, 17 February 2015
CSC148 Lecture Week 6
Object Oriented Programming Summary
Object Oriented Programming is a style of programming that involves grouping similar idea into classes. These classes are then used as blueprints that can be used to create instances of objects that have methods and attributes associated with them. Objects can then manipulate their attributes and use their methods to perform tasks.
Self
For all methods associated with a class, the first parameter is always the object itself. By convention this parameter is named self. This then allows you to call the method using syntax like this:
object.method()
which is equivalent to:
method(object)
Inheritance
The major idea that we covered in object oriented programming is the concept of inheritance. Sometimes classes will have many similarities and repeated code. Instead of copying and pasting code, which can cause many problems, inheritance is a much better solution. Copying and pasting code would force you to change many files every time you changed your design. With inheritance, a parent class has all the attributes and methods that are common to all the similar classes. For example, if you were designing a program to manipulate shapes, you would have a general shape parent class and child classes for specific shapes like triangles and squares. The parent class would have general attributes like side length, and general methods like find area. The child classes would inherit all this.
The parent class can implement some methods, but it might not actually know the specific details about methods like find area. In this case, it is not meant to be instantiated, so a NotImplementedError would be raised if the parent class' method was called. The child class would have a proper implementation that overrides the parent class method. Code that uses these classes would then be written for any general shape. It would not need to know what specific shape that it is dealing with and this allows for more flexibility.
Object Oriented Programming is a style of programming that involves grouping similar idea into classes. These classes are then used as blueprints that can be used to create instances of objects that have methods and attributes associated with them. Objects can then manipulate their attributes and use their methods to perform tasks.
Self
For all methods associated with a class, the first parameter is always the object itself. By convention this parameter is named self. This then allows you to call the method using syntax like this:
object.method()
which is equivalent to:
method(object)
Inheritance
The major idea that we covered in object oriented programming is the concept of inheritance. Sometimes classes will have many similarities and repeated code. Instead of copying and pasting code, which can cause many problems, inheritance is a much better solution. Copying and pasting code would force you to change many files every time you changed your design. With inheritance, a parent class has all the attributes and methods that are common to all the similar classes. For example, if you were designing a program to manipulate shapes, you would have a general shape parent class and child classes for specific shapes like triangles and squares. The parent class would have general attributes like side length, and general methods like find area. The child classes would inherit all this.
The parent class can implement some methods, but it might not actually know the specific details about methods like find area. In this case, it is not meant to be instantiated, so a NotImplementedError would be raised if the parent class' method was called. The child class would have a proper implementation that overrides the parent class method. Code that uses these classes would then be written for any general shape. It would not need to know what specific shape that it is dealing with and this allows for more flexibility.
Subscribe to:
Posts (Atom)