Week 8 - Assignment 2

Assignment 2 started out as a nightmare. At a certain point in attempting to write minimax I seriously considered why I was specializing in computer science. Until I made a breakthrough. When I first started to try and write minimax I tried to do it using the current state and running for loops, if statements, accumulators, and list sum opperators. But the way I was trying to do it was nearly impossible, because I hadn't ordered the data in any way. After considering my code for a long time I decided to scrap it and look for other ways of approaching the problem. I looked up explanations of minimax online and eventually came to the conclusion that I would have to somehow implement a Tree structure with nodes.
Learning about Abstract Data Structures in class, at the time I thought it was just a convenient way of storing data that I likely would never need or use. Until I was attempting to write the minimax function. Suddenly it became clear that in order to solve the minimax problem I would have to set up the state data into a tree of the current state, with the children being the next states of every possible move given the root state. The way I wrote the node structure was recursive, because every move called a new node with the move applied to the new state. This would recur for every move made in the root, then every possible move of the next leaf, then the next, etc. Until a tree of every possible move was created.
Once the tree was created I could run a minimax function that runs through the built tree to find the final outcomes of each leaf. If the player won it would return a 1, a draw or still playing was a 0, and a loss was a -1. The recursive function would sum together each leaf for each move root until a value was returned for each possible next move to make. The computer could then pick the outcome with the greatest number, guaranteeing it made the best possible move.

Week 7 - Abstract Data Structures

Throughout the course many Abstract Data Structures have been introduced. In csc108 we used the built in list and dictionary data types. These were simple ways of storing information. In csc148, we have been introduced to many more ways of storing information for use. One of the first was the Stack abstract data structure. A stack can have the top (aka end) item added and removed, but the other items in the stack cannot be modified. This structure seemed to be useful in very specific situations but not useful for most situations I can think of.

The second abstract data structure introduced was the Tree data structure. A Tree structure has a root node  with leaf nodes branching out as the root nodes children. Those leaves can then become roots themselves by adding more leaves to any leaf node. A Tree structure can become very complicated very quickly, depending on the number of children and in turn their children. Using recursion the tree can be traversed going down the roots to the leaves, and back up into the roots until all nodes have been visited.

The most recent abstract structure was the Binary Tree. A binary tree is similar to the tree structure, involving roots and leaves, however a binary tree can only have up to two children. Each root node can have a left and right child. This keeps the binary tree more structured than a regular tree structure. When ordering a binary tree values are ordered by greater than or less than the node. If the value you want to add is greater than the node you are in, move to the right child. If it is less move to the left child. If the left or right child exists then compare your value to the current node and repeat the process. When there is no left or right child then the value becomes the new child. A binary tree structure is a very helpful way to store items when you need to find a particular item quickly. This is because you can compare if the item you are looking for is greater or less than the node you are on, and search through the structure that way.
The class was taught three different ways of visiting each node: in-order, pre-order, and post-order. When visiting in-order, move down to the left child until the left child is empty. Then visit the left child you are on, then back up to the node, then the right child. Then move back up to the next node and continue through the rest of the tree. The method for visiting in pre-order involves visiting the node itself, then the left child, then the right child. This continues through the tree without visiting the same node twice. In post-order the left child is visited, then the right child is visited, then finally the node itself is visited.

This is my summary of the Abstract Data Types covered thus far. Hopefully other students can have a better understanding with this,

Week 6 - Recursion

In high school computer science, I was taught recursion, but because of the way it was taught I could not see the advantage of using recursion over a simple for or while loop. In this course, the challenge of determining how many layers "deep" a given list is proved to be a very practical way of showing why recursion is a necessary tool for any programmer. Since a list can have any number of lists within lists it would very difficult to write a loop for any n depth of list. I could not think of a method to tackle this problem with only a loop. However this problem is solved in just 4 lines using a recursive method. This was an excellent example of the importance of a computer scientist understanding recursion and using it as a tool in their programs.