Week 10 - Binary Search Tree and Test

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 =).

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.

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!!

Week 7 - Recursion recursion recursion...

Recursion is about to become trickier. Previously, we've used to search through nested lists and trees to find the longest branch, to sum all of the values, and to return the values of the leaves. So far our assignments have dealt with relatively small trees, only 3 or 4 nodes deep. Assignment 2 won't be so easy. Why? Because tippy can take 9 moves to end and has 138 different terminal positions. That means that the algorithm we make to search through these game states and evaluate the best ones will take a while to search through. Furthermore, we'll have to use come up with a base case that checks if a player has won the game, and then quits searching down that tree. If we don't make sure to stop recursively searching after a player has won, there would be a total of 326,800 different games that could occur (according to wikipedia). It will be crucial to write a tight recursive algorithm.

Week 6 - Trees!

Trees are tricky. They work based on the recursive techniques we've been learning for the past couple of weeks. These techniques served us well for nested objects like lists of lists. So it makes sense that they work for trees, which you are kind of like trees of trees. One new thing we learned that seems to be specific to trees is that we always define the base case to be a leaf (a tree with no children). This case seemed to be present in every module function we wrote for lab 5.

The one thing I still have trouble with is the a if b else c. I can't always predict it's syntax. Whenever it's inside a list comprehension, I don't seem to need the else. When it's anywhere else, however, it needs the "else" at the end. I'm not always sure what to put as the result however.

Anywho, another week, another opportunity for learning!

Week 5 - Thoughts on Object-Oriented Programming

The language we have studied so far in CSC108 and CSC148 has been Python, an object-oriented programming language. While Python is a pretty straightforward language compared to Javascript or any of the C languages, Assignment 1 showed me that it's not always easy to think in terms of object-oriented programming.

For example, it was a bit daunting to create a parent class, such as game state, that could be general enough to support different kinds of future subclass game states. As developers, we don't really know what those new child classes or games will look like. What if my future games support more than two players? What if I want to implement a game that can end in a draw, like Tic Tac Toe? Partly because of these concerns, I was confused with how to implement my parent and child classes in Assignment 1. Sometimes I would put the SubstractSquare code in the the general class, and just call that from the subclass. What I should've done was raise a NotImplementedError if anyone tried to use the general class, and then override those methods with the SubtractSquare code in my subclasses. This was the implementation I used for Lab #4, and it worked well. Hopefully I'll remember to override parent classes when necessary in the future.

Week 4 - Working with Partners

This semester is the first time I've had to labs for a programming course. For last semester in CSC108, I always chose to work on assignments alone. My main concern was that I barely understood how I was going to implement my code, so I didn't want to become further confused with someone else's suggestions. Since I've been working with a partner in the labs, however, I've found the process pretty encouraging. When we're both typing out code, we have twice as many eyes to catch the little errors we make like the wrong kind of brackets, forgetting parentheses when creating an instance of a class, etc. Also, I feel more confident with a class' implementation when I can discuss with someone else how that code should work. Sometimes, we're not sure what the implementation should be from the get go. In those cases, we have to combine our knowledge to figure out the problem. We're also more honest when we become stuck. If I'm programming alone and I become stuck on a certain function, I stubbornly struggle with it for a while without making any progress. When there's two people both stuck, I feel like they can quickly admit their stuck and then figure out why faster. All-in-all, these labs have been a positive experience for working with someone.

Week 3 - Why Geeks Should Write

In this blog post, I'm going to talk about geeks and why they should write. Now when I say "geeks", I'm not referring to videogame geeks, birder geeks, or Magic the Gathering geeks. Specifically, I want to narrow my discussion to computer geeks or software developers (or "devs" for short). So why should devs write? They should write so that they can communicate with other human beings such as other devs they are collaborating with or non-devs they need to talk to. Let's say a team of developers are working on a game, and one of the devs is responsible for debugging someone else's code. If the dev who originally wrote the code didn't leave comments describing how their code works, it will take the dev trying to fix the code a lot longer to find the problem. The next day, one of the designers might ask  the development team something that's completely infeasible for the scope of their project. The development team will have to explain to the designers (possibly in writing) why they can't do what the designers want. If the devs can't articulate why the designers' request is so unreasonable, then they'll have to waste a lot of time and money making something that won't work for their game. Unless the developer is working alone in her basement, she should know how to write in order to communicate with her peers.