As mentioned in week 8's post, binary search trees can sometimes be problematic. The example that I remembering being the most convoluted was deleting nodes from a binary search tree. There were like 6 different cases that we had to account for and write separate if statements. That was pretty crazy. I imagine that when I try to write that code, I'll get some serious errors, and I'll have to test each case individually to know what's really broken.
The test! Went alright. The structure was pretty much identical to the 2014 previous midterm. The only thing that I forgot to review was the post-order traversal for the tree. I think I got it right. I forgot the order of left tree, right tree, node, but the name "post" kind of gives away the fact that the node will be the last one checked. Also, I think I got lucky on the tree function question called leavesbetween I think. You gave it a range for a tree and it gave you back all the values within that range that were also leaves. On my cheat sheet, I had written down a function from one of the labs that returned values for internal nodes I think. So instead of checking if it had no children, I just had to check if it had at least one child. So that was pretty fortunate =).
Tuesday, March 17, 2015
Week 9 - Linked Lists!
I lied, we return to crazy binary search trees next week. This week we talk about linked lists (and bemoan the challenges of assignment 2). Linked lists have a recursive structure like trees which is kind of neat. That means we can perform similar techniques on them such as seeing if any of the linked lists contain a certain values. The other neat thing that I remembered from lectures is that when you are writing class methods such as "__contains__" and " __setitem__" can be called with "in" and "l[0]" respectively. The implications for that are pretty cool. For any class we define, we can add in __contains__ and __setitem__ just like we would __str__ or __repr__ and get some basic python functionality for our objects.
Assignment 2 was tricky. In hindsight, I think I should've worked with a partner. There was a lot of room for error in the assignment, and I think it would have been helpful to have another set of eyeballs evaluating my code. We were also given a bit more independence for this assignment in terms of how we solved problems. For instance, we know we needed a way of storing the information on the tippy board, but we weren't explicitly told to make a dictionary, list structure, or some custom coordinate system thing. There were some neat learning opportunities here because my original data structure (a single list) only worked for a 3x3 board size. In order to get an nxn board working, I needed to change the structure (lists within lists). Because I changed the structure, I had to change how game checked for a tippy.
Minimax was a bit laborious. On my own, I could write a function that could evaluate the score of a move for me, but it only worked properly if a win was two moves away. When I finally read the instructions on piazza (which were virtually identical to what Danny had said in class, but were even more explicit) I figured it out on my commute into school. I originally wrote minimax for subtracts quare, so adapting it to tippy was surprisingly trickier. Ultimately, there was more to do on this assignment than I expected, and another partner working with me probably would've helped.
Assignment 2 was tricky. In hindsight, I think I should've worked with a partner. There was a lot of room for error in the assignment, and I think it would have been helpful to have another set of eyeballs evaluating my code. We were also given a bit more independence for this assignment in terms of how we solved problems. For instance, we know we needed a way of storing the information on the tippy board, but we weren't explicitly told to make a dictionary, list structure, or some custom coordinate system thing. There were some neat learning opportunities here because my original data structure (a single list) only worked for a 3x3 board size. In order to get an nxn board working, I needed to change the structure (lists within lists). Because I changed the structure, I had to change how game checked for a tippy.
Minimax was a bit laborious. On my own, I could write a function that could evaluate the score of a move for me, but it only worked properly if a win was two moves away. When I finally read the instructions on piazza (which were virtually identical to what Danny had said in class, but were even more explicit) I figured it out on my commute into school. I originally wrote minimax for subtracts quare, so adapting it to tippy was surprisingly trickier. Ultimately, there was more to do on this assignment than I expected, and another partner working with me probably would've helped.
Week 8 - Binary Trees
One of the main topics we discussed in week 7 was Binary Trees. The main difference between binary trees and regular trees is how they deal with children. Binary trees have at most two children in them. So where tree's would have a list of children for self.children, binary trees have self.left and self.right. Some of the implications of this are that when we have a binary search tree, we can choose to perform recursion on the right side of the tree or the left side. Initially, I thought that these trees would be easier to work with, since they only have two children to deal with. That's true to some extent. For lab #6, the functions were easier to implement because the binary tree structure as a consistent logic to it. But as we find out in next week's class, they can be considerably more complicated!!
Subscribe to:
Posts (Atom)