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.

SLOG #3

    This week we delved deeper into recursive functions by looking at quick sort, a recursive sorting method that is supposedly more efficient than other sorting methods such as insertion sort and selection sort. The visual demonstration led by the instructor was quite useful, because I lose track of the code every time I try to trace it with some examples. Because of this, I am still unable to analyze the run time of quick sort compared to other sorting methods, so I am not totally convinced of its efficiency. Moreover, I think it is interesting that quick sort will sort a sequence again even if it is already in order. Would it be more beneficial if there were steps that check if the sequence was already in order?
    We also revisited an abstract data type stack, in which its elements are last in first out. I think it is a great method to check if there are matching pairs of something, among its many other uses. There was not a lot of content this week due to the term test.

SLOG #2

    This week's main topic is recursion. Recursion means defining something in terms of itself. It is the idea that a computer program can break a problem into many smaller parts, then solve these smaller problems using the base case of the program. As we saw in lecture so far, recursion is very useful in solving problems that involve unevenly nested lists.
    At first, the concept of a function calling itself in its own function definition seemed very abstract and impractical to me, because it would seem that the function can get stuck on an infinite loop that keeps on calling itself, or it can simply raise an error because the definition doesn't make much sense. Then, as the instructor traced the code, I realized that the base case of each recursion method would serve to avoid an endless loop and at the same time split the problem into its simplest form. After some practice on tracing recursive codes, I felt somewhat confident in my understanding of recursion.
    However, the hard part about grasping the concept of recursion is producing a working recursive code that solves a problem, as presented during the laboratory activity. Specifically, the problem was to implement a function length(L) that returns 0 if the input is not a list, or the maximum length of any list in the input, including the input list itself. My first attempt at this problem went as far as figuring out the base case, when the input is not a list. That was quite easy because the problem explicitly stated that the function should return 0 if the input is not a list. I could not make any progress on the recursive part of the function for a long time, since I had no idea how to piece together code in a recursive manner that can determine the maximum length of lists within a list. I tried to mimic the example codes that I have traced during the same activity by calling the built-in function max() on a list comprehension that contains length(x). So the code looked something like return max([length(x) for x in L]). That did not work at all when I tried to trace an example call, since there was no way of determining the length of any list in the input, all it could do was return 0.
    After some more trial and error, it became clear to me that I needed to develop a sharper understanding of the problem, which motivated me to look at the goal again. As I read the line 'maximum of len(L) and the length of any of L's sub-lists, if L is a list', I suddenly had the idea of putting two max() functions into my function definition. Using that thought I jammed the code 'return max(len(L), max([length(x) for x in L]))' into my function definition and the doctest passed. It was probably just luck on my part, but from this experience I learned that writing a recursive function requires a clear understanding of a problem and also some planning before jumping right in.

Why Geeks Should Write

    The assigned topic for this week's SLOG is 'why geeks should write'. I consider myself a geek according to the dictionary definition of 'unfashionable or socially inept; having great attention to technical detail'. So here are some reasons why I think I should write.
    First, writing regularly helps enhance my communication skills. Knowing how to express myself clearly and precisely is an useful skill to have, not only for writing docstrings in programming, but also in ordinary incidents such as writing emails. Often when writing an email, I find myself mentioning something that is not related to the topic, an indication of a lack of precise expression. Even as I am writing this SLOG, I am recognizing that several previous sentences I have put down are digressive and serve only to distract my audience, so I eventually had to remove them. However, if I practise writing regularly, I may be able to make fewer of these mistakes and keep the delivery of my ideas concise.
    Second, writing can help me relieve stress. Although the requirement for writing SLOGs every week adds to the heap of stress I must handle, the process of writing, not just SLOGs, sometimes relieves my stress. At the end of the day, I can create a text document and write down everything that bothered me, freely expressing my (sometimes offensive) opinions to the entity that will keep them secrets forever.
    Finally, writing can give me a chance to reflect on myself. I rarely motivate myself, at the end of the day, or week, or even month, to think about what I should have or should not have done, what interesting things I saw, or what I want to do in the near and distant future. Writing things down can help me gather and solidify memories and thoughts that I find worth remembering. Instead of always looking ahead of my journey, it's good to look back at my tracks.
    At this point I realized that I have gone off-topic again, because I didn't explain why, geeks, in particular, should write. I think this is because I truly believe that no one is exempt from the benefit of writing, geeks are no special. Everyone should write.