SLOG #10

    In the last lecture we looked at problems involving the run time of different codes and how we can categorize them using the big-Oh notation. We also looked at how graphs can be useful at modelling a variety of problems that can be thought as entities connected by pairwise relationships. The lecture material was straightforward.
    Looking back at this semester, learning and familiarizing myself with recursive implementation to solve otherwise troublesome problems was perhaps my biggest achievement, and also the task I had the most difficulty with. For me, the most challenging part of this course was designing minimax for assignment 2. I feel assignment 2 was when I had an ambiguous understanding of how recursion works, but hadn't developed a way to think recursively as I try to solve a problem. I read a few other students' SLOGs, and I found myself sharing a very similar experience with the author whose post is at http://dottoripy.blogspot.ca/2015/03/week-11-revisiting-previous-post.html. I'm still not quite able to use recursion with complete confidence, but I believe I will be able to gain insight to this method of solving problems as I progress as a programmer.

Revisit

    For this week's SLOG I want to revisit one of my earlier SLOGs on the summary of recursion. One opinion I had previously formed is that recognizing the base case and developing a comprehensive understanding of the problem are two key components in finding the solution. I still agree with my earlier self. My first attempt at cracking assignment 3 involved just me pulling out rough ideas of the recursive code in my head, but when I actually sat down and tried to write the code, I found myself stumped on important details that I had carelessly neglected  in my rough pictures. I could not get a clear grasp of the problem, and thus did not know how to make my solutions work. After a few hours of futile attempts I decided to take a break. When I came back I decided to use another approach. I drew several diagrams representing data structures of the problem, and asked myself, what exactly is my solution supposed to produce from these diagrams? What needs to be done in order to produce it? How can this process be generalized to fit all possible scenarios of the same data structure? After examining and answering these questions carefully, I developed a much better understanding of the problem, and I was able to come up with a solution that has withstood all my tests, so far.

SLOG #8

    This week's lecture focused on devising tests for assignment 2 and getting started with assignment 3. I have not carefully thought about assignment 3 yet, but I think optimizing minimax is a neat option because right now it takes too long for minimax to suggest a move for most game states. As the author whose post is at http://1024forbidden.blogspot.ca/2015/03/week10-start-of-a3-and.html feels, minimax seems to be stuck forever when starting on a 4 by 4 tippy grid. To put it bluntly, it is useless to provide the best possible move when it takes too long to do so. Then, swapping out the meticulousness for some much needed efficiency would be a wise choice.
    This week's lab activity also covers testing functions and methods with unit tests. One issue I had with testing strategy minimax on subtract square is that it can get strenuous when trying to find good numbers that has few winning moves and many losing moves, because I have to trace through every number and find out whether it is a winning position or a losing position. However, I wonder how much credibility my code would give if, instead of devising new test cases, I just run the test module multiple times, with no exception raised. If the starter code provides test cases where 1 in 625 random responses can pass, then perhaps rerunning the test cases can give a 1 in 625^2 chance of a random response passing? I don't see a flaw in this logic and, the chance of a random response passing would decrease exponentially, much faster than trying to figure out other suitable test cases. Unless, the code being tested only returns that one series of response which is acknowledged by the tests, in which case devising new cases would detect the problem at once.

SLOG #7

    This week's main topic focuses  on writing functions for abstract data type binary search tree. I found the function body of delete(node, data) somewhat difficult to understand. The explanations in the instructor's comments are helpful, and with the aid of some diagrams, I was able to eventually figure out each scenario that this function can encounter and how the function handles it.

    We also had a term test this week. I didn't find the test very challenging because I have seen similar types of problems either in lectures or in laboratory activities. The first question involved the definition of terms related to binary tree, so it was a matter of memorization. The second question tested our ability on writing recursive function for a binary tree, and the last question tested our ability on traversing through a linked list and making certain changes while leaving the rest of the linked list untouched. Overall, the test was straightforward.

    I'm having a lot of problems with this week's lab. Understanding the starter code and inserting data into binary search trees were easy, because I have seen all the methods and functions in previous lectures and labs. However, that is as far as I can go in completing this lab. A hint that was given to me is to look at the random module, and I have no idea how random can relate to making the binary search tree more efficient, or improve the height of the binary search tree in some way. I have tried to look at Piazza and other students' SLOGs, but to no avail. I will have to look at the sample solutions which hopefully will be posted soon, or go seek help from an instructor. I sincerely hope the strike will be resolved soon, because the lack of guidance from teaching assistants has impacted me, and surely other students, negatively in terms of maximizing our learning opportunities. 

SLOG #6

    My focus for this week has mainly been on the completion of assignment 2. The game state class was not particularly difficult because the starter code provides a clear concept of what methods the class should contain, and I only had to come up with some ideas on the abstract data structure to keep track of the state, and some specific attributes that are required to play the game Tippy. Checking the winning condition took a bit more thought because I tried to approach the problem using recursion at first, but coding the method in numerous lines was actually conceptually more straight-forward, since there are only four possible tippy shapes when all translations and rotations are broken down.

    The implementation of minimax really stumped me. I read the assignment sheet over multiple times and was able to figure out the base case to be when the game is over and returning -1, 0, or 1 according to the result. However, I couldn't figure out how to write the general case. Because of the notion that minimax can calculate both the next_player's and the opponent's scores, I tried to split the method into two parts, each for calculating the score of each side. That approach proved to be erroneous because it did not work well with the base cases that I chose. Eventually I realized that I was over-analyzing the problem by looking at the entire tree of possible game states at once. Like the author whose post is linked here http://1024forbidden.blogspot.ca/2015/03/week8-assignment2-about-recursion-and.html says, drawing pictures is quite helpful in figuring out the recursive part of minimax. I drew a game state with two child game states and recognized that this simple structure can be a child of another game state, and also it can have child game states of its own. Then shortly after I figured out to use list comprehension with minimax on a list of possible moves, then multiply all the scores by -1 to obtain the max to produce the current score for next_player.

Summary of Recursion

    After familiarizing myself with the abstract data type Tree and recursive laboratory exercises, I finally have a basic grasp on reading and writing recursive functions. Recursion in terms of programming is a technique that breaks down a complex problem into very basic but also very similar problems in order to solve a problem. In essence, it involves writing functions that call on themselves inside their function definitions. Generally speaking, recursion contains a base case that will most certainly be visited at least once, and also one or more general cases that breaks down the problem and directs it to the base case. The SLOG posted here at http://148blog1.blogspot.ca/2015/03/recursive-code-and-advice-on-how-to.html provides a detailed explanation and tracing of the function sum_list that is of recursive nature. I agree with the author that recursive code allows for efficiency, whereas iterating through a problem can often become very time-consuming, or even impossible for some cases.

    Writing recursive code isn't exactly a breeze. In my previous post I said recognizing the base case means almost solving the problem, but that was not true when I encountered problems involving the abstract data type Binary Search Tree. I was hopelessly lost even after recognizing the base case, because the recursive code actually contains several general cases, such as when the value is greater than the float data rooted at 'node' or when the value is less than the float data. The question was considerably more difficult for me because it wasn't clear what to do once I figure out the base case. Then, I presume there must be many more types of problems that involve some variations of the basic recursive code for sum_list, where the base case does not clearly provide a hint to the next steps, and I think the key to solving these problems is a thorough understanding of the problem and some creativity.

SLOG #4

    The phrase "object oriented programming" has been and still is quite mysterious to me. To my understanding, object oriented programming revolves around creating and modifying an object, such as a class. Then, I can say a few things to summarize a few concepts that I have learned so far. For example, when an instance of an object gets created, it is usually initialized to have some values. These values may be changed, used, or modified in some way later by methods of that instance. Functions defined under a class are called methods of that class. They are defined with a self-referencing parameter called "self" by convention to point to the instance calling it. Hence, we can say that methods revolve around an object, and only instances of this object may call on its special methods. Another important concept is inheritance in classes. When an object inherits from another object, it also duplicates the methods and initial values of the original object. The difference is that the new object may possess new values or methods, or it may modify those of the original object. In short, we can say that the child class is a more specific version of the parent class to specialize in certain tasks.
    This week's main topic was writing recursive functions for an abstract data type called Tree. I was having the same experience as the author of the SLOG posted here http://thecodingdiaries.blogspot.ca/2015/02/week-8.html. During the laboratory assignment, the function list_to_depth was particularly difficult to figure out because it did not quite follow the previously established structure of the other functions in the activity. I agree with the author of the SLOG posted above that, when writing my own recursive functions, often I have to "get creative". Of course, this doesn't mean coming up with random codes that don't make sense or relate to the problem at hand. From my very little experience, the base case provides a huge hint to what the code for the general case should look. The instructor said writing the base case is like getting 50 percent of the work done, but from what I have seen, it should be increased to 65 or even 70 percent. It is composed of code that will be called at least once, and it is used to break down the possibly complicated structures of the inputs. Therefore, successfully recognizing the base case can help in both grasping the main objective of the problem and writing out the general case.