CSC148 Marth 30th 2015

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.

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.

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.

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.

CSC148 February 29th 2015 Writing Recursion

In this post, I will be writing about object-oriented programming as well as writing recursion, to make up for the blog post that i forgot to write during reading week.

Object-oriented programming is a term that i first heard of near the end of CSC108, as we began learning about writing our own classes.  At that time, my understanding of OOP is simply what my professor had taught me, a way of programming that focuses on objects.  I learned after doing some research that OOP is focused on objects rather than actions, and data rather than logic.  In this model, objects are well defined data structures that can be manipulated through methods, and objects can also interact with each other through methods.  Programs that are built on OOP are essentially objects that interact with one another though logical functions.  Python is a common type of OOP language, as are C++ and Java.

In Python, objects are defined by their class, which may be inherited from another class.  These classes may be modified versions of generic data structures such as lists, and in turn they may be modified into objects such as queues and stacks.  Classes not only represent objects through different data structures and attributes, but also include ways of how these objects can be manipulated.  For example, a class that represents a circle may have methods that adjusts the radius of the circle, as well as tell whether or not two circle objects are the same.  Classes can even represent complex objects such as chess, and different chess strategies.  With creativity, i believe a great deal of both real and abstract objects can be defined by Python classes.

Now onto recursive functions.  The focus of the last two weeks of 148 was the writing of recursive functions.  As i have mentioned in a previous post, the process of writing recursive function is really similar to induction to me.  First i have to find a base case, which in most recursive functions is the basic output on a simple object.  Then, the recursion will repeat a certain process over and over until it reaches the base cases, and then it will perform a boolean function on the base cases.  However, in the last lab, i practiced writing more complicated recursive functions that involved if statements.  Though i was able to figure out how to implement the 4 practice functions, i feel like i still havent grasped the intuition of recursion yet.

CSC148 February 9th 2015

The highlight of last week's CSC148 is the first midterm of this semester.  Having gone to Danny's lecture for 165 last semester, I had a pretty good idea of what I should be expecting, and i was very nervous before the test because truthfully i feel like i haven't learned a whole lot of new stuff since the beginning of this semester.  As i recall, the first 165 midterm was a simple, yet difficult test to me, and i didn't do particularly well on it either.  After reading over the lecture slides as well as the lab handouts multiple times, i felt like i had a good grasp of what will be tested, mainly writing classes and subclasses, and a bit of recursion tracing as well.  The test itself was surprisingly simple, and did not require much "smart" thinking.  Practice from assignment one on writing classes and subclasses certainly helped me feel at home as i worked through questions 1 and 3 on the test.  The recursion tracing bit was also pretty simple, as long as i took the time to write out the steps instead of being lazy and trying to cut corners.  However after writing the test, i realise that i misunderstood a method in the first question, which many cost me a fair bit of points.  The method that Professor Heap intended us to write was one which stores information passed in as arguments into an object attribute.  When i read the question, i thought that i was required to also prompt the user to give an answer as part of the method, and so my code was unnecessarily long.  The lesson that i have learned from this is to read each question description thoroughly, and never assume i know what i am asked to do and skip reading the latter part of the question.

CSC 148 February 1st 2015: Recursion

During this week's lecture, i learned about recursion: what it is, how it looks like in code, and how to trace and understand it.  When the professor opened with the example question of how we can add up integers in an arbitrarily nested list, i thought the solution would be using some sort of while loop, and that recursion was simply repeating the same action many times until the desired result is obtained.  However, instead of using loops, the solution to the problem was a function that calls itself in its body.  At first i thought, will this really work?  Wouldn't Professor Heap just get some sort of name error saying that the function name is undefined?  But it worked, and the idea of a function calling itself confused me to no end.  The only similar thing that i have seen was when Professor Heap introduced the idea of uncomputable problems using halt and naval gaze, and that example was a very confusing one already.  However, after working through some tracing exercise for the example function, i realized that tracing function calls on simple to complicated arguments really helped me understand how the function itself works.  For example, with the problem of finding the sum of integers in arbitrarily nested lists, i started with example calls on ints, then a single list, and then a list of depth 2, and so on, and i found that tracing recursion is much like expanding out a compact mathematical equation.  Starting with the function call on the argument, recursion causes the function to be called on each element of the iterable argument, and then on each element of those, and so on, similar to expanding functions such as (x-3)^3.

During the lab this week, i did some more tracing exercises, and i found that by tracing, i could more or less figure out the gist of a function, however i think that if i were to use tracing to figure out the purpose of a function, i need to come up with relevant examples, for example passing in strings to a function thats meant to work on ints and lists wont achieve much.  Just when i thought recursion was a pretty simple idea, i got stumped on the last exercise of the lab, which was to write the body of a recursive function.  At this point, i knew that i should include an if statement to essentially separate the arguments of the function into two types, one where object type that the function is intended to work on, and the other where basically every other object type is filtered.  The tricky part was implementing the recursion.  The function that i needed to write is supposed to find the maximum length of a list in the argument and return that number as an int.  I knew that i had to work with len() and max(), however i was stuck on which process i should repeat(with recursion).  I knew that i needed to find the length of every list in the argument, and somehow use the max() function to compare them to each other, but there are also other objects such as ints in the argument, and when trying to pass an int to len(), i get an error.  Furthermore, int isn't an iterable object, so i cannot use list comprehension to build new lists with len().  I tried to think about the very basics of this problem.  The recursive part will repeat that section of the code on every list in the argument, but how do i go deeper and look at each element of the list?  In the end i ran out of time before i had to complete my quizz.

At the end of the tutorial, i gave up and asked my T.A. on the possible solutions of this problem, and she showed me a much simpler and different method of implementing this function.  Instead of creating a list where each element is an int that represented the length of each list in the argument, i can simply use the max function to compare the length of the outmost list to the length of every list nested inside of it.  After thinking about it more at home, i finally came up the solution:

return max( [len(L)] + [length(x) for x in L])