In this slog, I will be reviewing my earlier slogs on recursion, as well as how my impression has changed. When I was first introduced to recursion, and practiced implementing recursive functions on tree structures, I felt like I knew how the concept worked, but trying to put all the pieces together to form a function was still difficult. At that time, what I did was basically copy the format of examples provided during lectures, and making small modifications so that they would work for the lab problems. However, most of the time I was really just guessing and checking, and even when I managed to solve the problem, I didn't really understand how or why. That strategy worked until I encountered problems that required me to add in new things, such as multiple if statements in the recursive step. I think my moment of clarity came as I worked on assignment 2. I spent 2 days staring at diagrams of trees of gamestate, trying to figure out the link between each of the nodes, how to get from the root to the leaves, etc. I ended up writing 3 separate functions, and then trying to put them all together in my attempt at a recursive function. After reading the assignment sheet again, I started to look at the problem from another approach. Instead of looking at the entire tree, I decided to only looked at the root and its children. Doing this allowed me to figure out the base case of minimax, because each children is also a leave. Then, I added children to the leaves of the original tree, and looked at the relationship between the root and its children, as well as the children and the grandchildren. This is how I figured out the recursive step, and what helped the most was the realization that whatever the root asks its children, the children will ask the grandchildren. This simplified by though process A LOT, as I only needed to think about one relation, instead of trying to think about all the possible interactions between every node in the tree.
I also read a few of my peer's slogs, notably Ken's at "http://slogfor148.blogspot.ca/". Ken's post about recursion gave me a new perspective on how one can approach recursive problems. Ken wrote that when he encounters a problem, he usually thinks about various code that can be possible solutions, while I tend to first try to figure out what sort of computations a human would do to solve a problem, and then translate that process into code. Thinking directly in code definitely has its benefits, as there are many shortcuts and functions that can compress the steps that a human mind might take. Another very important lesson that I learned from his post is how he analysis the data structure of the problem, and how his solutions can be generalized to work with difference scenarios using the same data structure. This way of thinking will cover any potential holes or bugs that the code might encounter on different objects of the same data structure.
Monday, March 30, 2015
Friday, March 27, 2015
CSC 148 March 27th 2015
Normally I would be discussing this week's material, but I realised that I forgot to write a blog last week so this one will be based on the materials covered in week 10.
In week 10's lecture, Professor Heap showed us his sample solution of minimax, as well as introduced assignment 3. The sample solution pairs every possible move of a gamestate with a score of 1, -1, or 0, depending on whether or not the move can guarantee a win. Then, the sample solution will pick a move that has the highest score, and return it. The sample solution is much shorter and more efficient than my code, because my solution uses two functions instead of one. One of my function essentially takes a gamestate, and returns a score. The second function uses the first one to determine the score of the opponent's gamestate, and picks the move that leads to the gamestate with the lowest score. The main reason I split it into two functions was because when I tried to use max() on a list of tuples, where each tuple had an int representing the score, and a move, I kept getting errors because I didn't implement any methods that compared moves to each other. The Professor showed us that we can use the max() function on only the first index of each iterable, and I will use this to rework my minimax strategy. Other than that, we talked about how to create test cases to test our code. These test cases should include as many possible scenarios as possible. For minimax, there could be cases where there are no winning moves, gamestates where all moves are guaranteed wins, and gamestates that has a mixture of both. We also discussed the difference between global and local variables in a tracing exercise, which is similar to questions that were tested on in 108 last semester. Overall, the content this week was pretty mild, and I look forward to the materials next week.
In week 10's lecture, Professor Heap showed us his sample solution of minimax, as well as introduced assignment 3. The sample solution pairs every possible move of a gamestate with a score of 1, -1, or 0, depending on whether or not the move can guarantee a win. Then, the sample solution will pick a move that has the highest score, and return it. The sample solution is much shorter and more efficient than my code, because my solution uses two functions instead of one. One of my function essentially takes a gamestate, and returns a score. The second function uses the first one to determine the score of the opponent's gamestate, and picks the move that leads to the gamestate with the lowest score. The main reason I split it into two functions was because when I tried to use max() on a list of tuples, where each tuple had an int representing the score, and a move, I kept getting errors because I didn't implement any methods that compared moves to each other. The Professor showed us that we can use the max() function on only the first index of each iterable, and I will use this to rework my minimax strategy. Other than that, we talked about how to create test cases to test our code. These test cases should include as many possible scenarios as possible. For minimax, there could be cases where there are no winning moves, gamestates where all moves are guaranteed wins, and gamestates that has a mixture of both. We also discussed the difference between global and local variables in a tracing exercise, which is similar to questions that were tested on in 108 last semester. Overall, the content this week was pretty mild, and I look forward to the materials next week.
Monday, March 16, 2015
CSC148 March 16th: Linked List
In this post, i will be talking about linked lists and linked list nodes, which was covered in class a week ago. Last week was the second midterm of 148, and i think it went pretty well. The three quests were very similar to tutorial problems that i have solved before, and i was able to breeze through them without many difficulties. Now, onto linked lists.
I was taught that there are two main approaches to visualizing linked lists. One is of lists that contained some data, and possibly another linked list. This way, inside each linked list could be another linked list, and thus the lists are linked. The other approach is the one that this course will be taking, which is of objects(nodes) that contain some data, and a reference to another object(node). With this approach, we will need to defined the object(node) as a class, and also a wrapper that contains the linked list as a whole. This concept was simple enough, however when it comes to implementing methods that manipulates linked lists, things become more complex. To me, i think of a linked list as a train, with a beginning node, intermediate nodes, and an ending node. However, these nodes do not have any form of indexing, and so to manipulate a specific node, i must use a loop that moves down the linked list one node at a time, starting from the beginning. The difficulty of doing this is that you really don't have a way to knowing exactly the location of the current node in the linked list. All you know is the data that the current node contains, and its previous and next nodes. That's why when iterating over linked lists, it is important to be able to clearly visualize how your loop will work, so that you don't end up manipulating the wrong nodes, or worse, severing the link of the linked nodes.
I was taught that there are two main approaches to visualizing linked lists. One is of lists that contained some data, and possibly another linked list. This way, inside each linked list could be another linked list, and thus the lists are linked. The other approach is the one that this course will be taking, which is of objects(nodes) that contain some data, and a reference to another object(node). With this approach, we will need to defined the object(node) as a class, and also a wrapper that contains the linked list as a whole. This concept was simple enough, however when it comes to implementing methods that manipulates linked lists, things become more complex. To me, i think of a linked list as a train, with a beginning node, intermediate nodes, and an ending node. However, these nodes do not have any form of indexing, and so to manipulate a specific node, i must use a loop that moves down the linked list one node at a time, starting from the beginning. The difficulty of doing this is that you really don't have a way to knowing exactly the location of the current node in the linked list. All you know is the data that the current node contains, and its previous and next nodes. That's why when iterating over linked lists, it is important to be able to clearly visualize how your loop will work, so that you don't end up manipulating the wrong nodes, or worse, severing the link of the linked nodes.
Sunday, March 8, 2015
CSC148 March 8th 2015
Much of the focus of this week was on assignment 2, and i must say, the process of writing recursion became a lot more clear to me after figuring out how to implement minimax. In my last post, i said that to me, writing recursion is just like induction. First, find the base case, or cases, and then apply the inductive step. Generally, the recursive step in writing functions is harder than identifying the base cases, but i think have finally discovered a way of thinking that will allow me to arrive at the correct recursive step. When i worked on recursive functions in previous labs, after identifying the base case, i was often stuck thinking about what steps i need to repeat, and in what order. Determining where place the recursive call was also difficult, as i end up thinking about too many factors all at once. However as i worked on minimax, i began drawing my own trees, branching out from a root gamestate. I knew what the base case of the function was, but i had trouble bringing the base case results from the leaves of the tree all the way back to the root. After spending hours staring at the tree that i had drawn, i suddenly realized that recursion is much simpler than what i had thought. Instead of looking at the tree and trying to think of a process that passes information from each of the leaves all the way back to the root, all i needed to do was look at how the information is manipulated between each level of nodes. I started by looking at only the root and its children. The root will ask each of its children a question, and then process all the answers into a single answer. This is basically the recursive step that i was always over thinking about. As long as i can figure out what the parent should ask its children, and how the parent can process all the answers into one, i can repeat this question on the children of the children, and so on, until the base case us reached. This way of thinking really made the process of recursion seem much less daunting, and i am sure it will help me in the upcoming midterm.
Subscribe to:
Posts (Atom)