Wow, 12 weeks do past by really quickly. I know that I'm a bit late on this SLOG, but I wanted to make sure that I had a comprehensive understanding of what we learned exactly this semester. I was also rushing to finish the third and final assignment, and I definitely planned to have that finished by writing this. So all in all, even when I read this a few years down the road, here goes my final SLOG, covering the topics of:
1) The 3 assignments
2) The lecture materials
3) The term tests
4) Anything else
--------------------------------------
1) Assignments
To start off, the assignments definitely became much easier as the semester progressed. That is to say, in terms of hardest > easiest, it was undoubtedly A1>A2>A3 (the third assignment being the easiest). When I initially saw the first assignment, I was bewildered: I wasn't exactly the most confident in classes, and the multi-class, multi-method, multi-method aspect of creating the game confused me greatly. After much struggle and forum-stalking, and constantly using smaller examples, I finally had something that functioned. It was a mess between the gameview, gamestate, and strategy. I understood the desired implementations that the profs wanted from generic states, but I felt like my approach and style were counter intuitive from what was expected of us. Lo and behold, I received a decent mark for my approach. My biggest struggles, and accomplishments likewise, were the implementations of parent (generic) -> child (specific game state) classes.
The second assignment was mildly easier, as in the starter code, or the prof's "official" solutions were given to us, for us to plug in our new Tippy game to. I had much fun implementing the actual logic behind the Tippy game, and creating the algorithm to detect the Tippies themselves. The solution actually game to me from a quick jaunt to the shower... However, there was one really tough approach, which was Minimax, the 'unbeatable', logically objective strategy for the computer. Looking back now, I realized that my largest setback was being unable to break away from the simple list comprehension base case type of recursion. Luckily for me, professor Heap gave us essentially the solution to the code via pseudocode in a course-wide email... but even that was unhelpful. The office hours were blessed, and I think I nailed the solution. All in all, the assignment was a nice challenge that tested my knowledge of the course.
The third assignment, however, was very easy. The given option A, which was to optimize our own minimax algorithms was risky for 2 reasons: 1) we didn't receive feedback on our own minimax which made it hard to improve on because we don't even know if it was implemented properly, and 2) we needed to start from scratch 3 separate files for our code. On the other hand, the sparkling golden option B required none of that as it operated only on gamestates. All the functions had been defined beforehand as well, with adequate docstrings and documentation. This was an easy decision; plus I had nailed the "hard" part of the assignment for function grown within an hour, which easily meant that this option was my chosen one. Because of this, option B became easy, and almost trivial as the minimax implementation really helped my recursion programming.
--------------------------------------
2) Lecture materials
At first, I really missed the PCRS spoon-feeding system of hands-on teaching. I thought that code on a projector wouldn't be as useful, but as time passed, Prof Heap proved me wrong. His clarity and concise-ness along with the plentiful amounts of help on the forums were really useful. However, the most helpful resource were the code snippets, lab solutions and annotated slides posted on the website. Being able to freely review all lecture materials at will and play around with all code presented in the course were really, really helpful.
--------------------------------------
3) The term tests
Ah, the great outdoors, or in other words, the room known as EX100. I was nervous for both tests for similar reasons I talked about for the assignments. The first term test, which was about recursion-tracing and parent-child class relations seemed a daunting a topic, especially after receiving 1/2 on the quiz by pure guessing. The given cheat sheet was very useful and I managed to match one of my answers to an example I had noted previously. Similarly, the daunting 2nd term test was blessed by my cheat sheet that seemed to solve the hardest problem, letting me nail an A+ and a high A on the tests, respectively.
--------------------------------------
4) Concluding thoughts
Contrary to my initial fears from the course, CSC148 only helped my love for programming and logic, and I can't wait to attempt things next year! See you all later, and let this be a chapter in my personal testament to becoming a better programmer~
Take care,
Andrew L.
Winter 2015, CSC148
Sunday, 5 April 2015
Monday, 23 March 2015
Week 11: Recursion revisited
No pun this time, just a few thoughts on how I've progressed through the semester on recursion. Reflections on my Week 5: Recurring thoughts about recursion.
Back when I started doing recursion, and after several simple examples/practice problems on basic recursion, I thought that I had a decent grasp on the concept. The examples mostly consisted of one simple check on types inside a list, with an else statement performing list comprehension on nested lists, which would then proceed to call itself and perform recursion.
Okay, so it's been 6 weeks, or roughly a month and a half of having extended my recursion knowledge and increased usage of recursion. Topics included mixing recursion with trees (trees, binary trees, binary search trees), linked lists, and with our second assignment on programming tippies.
Amendment: I'm not that good at recursion.
I had much trouble blending my ability to program trees and recursion. I couldn't really understand how the implementation of trees would be suitable for recursion, and even when I did, I struggled to implement them by myself. The examples seemed to flow so quickly and smoothly when Professor Heap performed them. This was also coupled with me not reviewing lecture material. Skip ahead a few weeks, and I managed to miss a few lectures on linked lists/binary trees. This didn't help my already lacking understanding of mixing recursion.
Quoting myself:
"""
Though I do struggle with some specific tree functions (such as the in_between exercise from lab #6), I do think that recursion can now be confidently added to my toolbox of useful Python tools.
"""
I disagree wholeheartedly. Even after the second assignment and second term test, I realize that I still struggle with many of the recursive aspects of the newly introduced data types, for example, linked lists and trees, contrary to my own "update" on having "mastered" trees. Likewise, I still do hope to improve my own abilities and confidence on recursion, though with this SLOG post I'll refrain from commenting on my own prowess with such confidence.
Back when I started doing recursion, and after several simple examples/practice problems on basic recursion, I thought that I had a decent grasp on the concept. The examples mostly consisted of one simple check on types inside a list, with an else statement performing list comprehension on nested lists, which would then proceed to call itself and perform recursion.
Okay, so it's been 6 weeks, or roughly a month and a half of having extended my recursion knowledge and increased usage of recursion. Topics included mixing recursion with trees (trees, binary trees, binary search trees), linked lists, and with our second assignment on programming tippies.
Amendment: I'm not that good at recursion.
I had much trouble blending my ability to program trees and recursion. I couldn't really understand how the implementation of trees would be suitable for recursion, and even when I did, I struggled to implement them by myself. The examples seemed to flow so quickly and smoothly when Professor Heap performed them. This was also coupled with me not reviewing lecture material. Skip ahead a few weeks, and I managed to miss a few lectures on linked lists/binary trees. This didn't help my already lacking understanding of mixing recursion.
Quoting myself:
"""
Though I do struggle with some specific tree functions (such as the in_between exercise from lab #6), I do think that recursion can now be confidently added to my toolbox of useful Python tools.
"""
I disagree wholeheartedly. Even after the second assignment and second term test, I realize that I still struggle with many of the recursive aspects of the newly introduced data types, for example, linked lists and trees, contrary to my own "update" on having "mastered" trees. Likewise, I still do hope to improve my own abilities and confidence on recursion, though with this SLOG post I'll refrain from commenting on my own prowess with such confidence.
Forgotten slog: Week 8: Linked Lists
So turns out I had this slog post saved into my drafts rather than having posted it, so a quick update to "fill-in" my missing week 8 slog post. (oops). Anyways, moving on:
This week's covered topic was of linked lists, an introduction to another data type, which to me, is a bit of a doozy. In essence, I think of linked lists as a recurring single-item list implementation with a little sprinkle of recurring trees. The way linked lists work is a single element "node" with a reference to another front "node" and "back node". This way, each node contains the element that you want to store, as well as the next and previous elements for manipulation. This notion serves as the list aspect, with the linked part commenting on the back/front references.
Let's examine this crudely drawn diagram. For demonstration, an arbitrary list could be:
[1, 2, 3, 4, 5]
A linked list would be:
[ 1 | x <-]------[->2 | x <-]------[->3 | x <-]------[->4 | x <-]------[->5 | x <-]------[->None]
The 'x' represent the pointer in which other nodes refer to them. We can see that the first element, 1, points forward as its "back" node is 2, while 2's front node is 1. This creates a linked aspect between the elements. Now for the implementation, this will explain why I see it as a single branched tree.
Each linked list has a front, which is of an arbitrary form LinkedList(<val>, front). Val points towards what you're storing, and front refers to another node, which would normally be another linked list. So, a LinkedList(<val>, LinkedList(<val2>, LinkedList(<val3>, None))) would be a nested linked list to create a 3 element linked list. Now, to perform and implement specific methods, such as append, delete, remove element, extend, reverse and all that jazz, you need to iterate over each node as per your function.
To do this, there are 2 methods: iteration and recursion. Using iteration, such as a one-way while or for loop, you check each element of the linked list one by one for your condition, perform the task, and then break the loop. It's almost identical to iterating over a regular list using "for i in range", except slightly more complicated. The other approach, which wasn't really discussed all that much in lecture was using recursion. This simplified the method bodies by reusing code from the method itself, called until the method was completed. Although recursion seems neater and is more concise, iteration for me works better as it comes more naturally to me. It's easier for me to grasp the concept of checking each item once over rather than attempting for simplify my code for a few lines' difference in method length.
So what's the benefit of using a linked list? Well for one, there are many many more operations that you can customize using a linked list. For example, as each element or node is unique in the sense of its data, in addition to its storage as a node, allows for more specific operations that would otherwise require more and more and more nested lists, which in contrast to its seemingly deceptive nature, would make the process more complicated should the standard lists be used.
This week's covered topic was of linked lists, an introduction to another data type, which to me, is a bit of a doozy. In essence, I think of linked lists as a recurring single-item list implementation with a little sprinkle of recurring trees. The way linked lists work is a single element "node" with a reference to another front "node" and "back node". This way, each node contains the element that you want to store, as well as the next and previous elements for manipulation. This notion serves as the list aspect, with the linked part commenting on the back/front references.
Let's examine this crudely drawn diagram. For demonstration, an arbitrary list could be:
[1, 2, 3, 4, 5]
A linked list would be:
[ 1 | x <-]------[->2 | x <-]------[->3 | x <-]------[->4 | x <-]------[->5 | x <-]------[->None]
The 'x' represent the pointer in which other nodes refer to them. We can see that the first element, 1, points forward as its "back" node is 2, while 2's front node is 1. This creates a linked aspect between the elements. Now for the implementation, this will explain why I see it as a single branched tree.
Each linked list has a front, which is of an arbitrary form LinkedList(<val>, front). Val points towards what you're storing, and front refers to another node, which would normally be another linked list. So, a LinkedList(<val>, LinkedList(<val2>, LinkedList(<val3>, None))) would be a nested linked list to create a 3 element linked list. Now, to perform and implement specific methods, such as append, delete, remove element, extend, reverse and all that jazz, you need to iterate over each node as per your function.
To do this, there are 2 methods: iteration and recursion. Using iteration, such as a one-way while or for loop, you check each element of the linked list one by one for your condition, perform the task, and then break the loop. It's almost identical to iterating over a regular list using "for i in range", except slightly more complicated. The other approach, which wasn't really discussed all that much in lecture was using recursion. This simplified the method bodies by reusing code from the method itself, called until the method was completed. Although recursion seems neater and is more concise, iteration for me works better as it comes more naturally to me. It's easier for me to grasp the concept of checking each item once over rather than attempting for simplify my code for a few lines' difference in method length.
So what's the benefit of using a linked list? Well for one, there are many many more operations that you can customize using a linked list. For example, as each element or node is unique in the sense of its data, in addition to its storage as a node, allows for more specific operations that would otherwise require more and more and more nested lists, which in contrast to its seemingly deceptive nature, would make the process more complicated should the standard lists be used.
Wednesday, 18 March 2015
Week 10: Midterm & Linked Lists
Whoops, another late post~
In this little entry, I'm going to recap the week of March 9th - March 13th, which consisted of one lecture and the second term test. Going into the Monday lecture I wasn't too prepared as I had missed roughly 4 lectures in a row due to another term test and sickness (but I'm all better now), meaning that this lecture was almost completely foreign to me. Before class, I had been reading the annotated slides on the CSC148 homepage, and was trying to fervently catch up on the material. I get to class, try my best to keep up, and attempt the worksheet.
Due to other tests, I only really spent about 6-8 hours studying for the second term test, which featured basically all the concepts that I wasn't too confident in linking together: recursion and trees, recursion and linked lists and linked list iterations. Piazza was extremely helpful, as were the professors and other online resources. In trying to answer other students' questions was when I found holes in my studying - in addition to failing the past test.
The cheat sheet on the exam was very helpful too, as one of the code snippets I put on it happened to be a slight variation to a test question, making the whole test just a bit easier. I couldn't remember exactly if a binary tree necessarily needed to be completely filled, so I took the gamble on deciding tree length. All in all, not too much CSC148 that week, but the test really forced me to catch up on concepts.
In this little entry, I'm going to recap the week of March 9th - March 13th, which consisted of one lecture and the second term test. Going into the Monday lecture I wasn't too prepared as I had missed roughly 4 lectures in a row due to another term test and sickness (but I'm all better now), meaning that this lecture was almost completely foreign to me. Before class, I had been reading the annotated slides on the CSC148 homepage, and was trying to fervently catch up on the material. I get to class, try my best to keep up, and attempt the worksheet.
Due to other tests, I only really spent about 6-8 hours studying for the second term test, which featured basically all the concepts that I wasn't too confident in linking together: recursion and trees, recursion and linked lists and linked list iterations. Piazza was extremely helpful, as were the professors and other online resources. In trying to answer other students' questions was when I found holes in my studying - in addition to failing the past test.
The cheat sheet on the exam was very helpful too, as one of the code snippets I put on it happened to be a slight variation to a test question, making the whole test just a bit easier. I couldn't remember exactly if a binary tree necessarily needed to be completely filled, so I took the gamble on deciding tree length. All in all, not too much CSC148 that week, but the test really forced me to catch up on concepts.
Tuesday, 10 March 2015
Week 9: Binary Trees, Binary Search Trees and Minimax
Whew, a delayed post from a whirlwind of a week. Unfortunately, I couldn't attend any of the CSC148 lecture offerings last week due to test and assignment conflicts, which meant that I had to spend this weekend and most of yesterday teaching and reviewing the material that I missed. With that, a little on last week's material: Binary Trees, a variant Binary Search Trees and the dreaded minimax algorithm.
So first off, binary trees, or BT for short, are a method of data/object manipulation that mimic a branching tree diagram in real life, except with the binary restriction, or a maximum of two branches per node. Using the diagram below (sourced from http://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/pix/tree1.bmp), the parent node is at the top 8, and each branch has a maximum of two children (or sub-branches, if you will).
The method can be used to store information according to user-provided restrictions per branch, and is essentially an extension of recursive programming. Examining the sample code snippet below:
class Tree: ’’’ Represent a Bare-bones Tree ADT’’’ def __init__(self, value=None, children=None): ’’’ (Tree, object, list) -> NoneType Create Tree(self) with root node value and 0 or more children. ’’’ self.value = value self.children = children.copy() if children else []
The bare-bones tree abstract data type is instantiated recursively with children, in which the children become the "parent" and thus allows for new children, which then becomes the new parent for more children and etc etc. (Except with a binary tree, the init variables are limited to self.left and self.right for its corresponding left and right children). Using this class, it's possible to implement many manipulative methods, such as getting the height (the number of nodes from the parent to the last leaf, or children-less node), getting the arity (maximum number of branches), or counting the number of leaf nodes.
Now, binary search trees, or BSTs for short, are a subset of binary trees (which in themselves are a subset of trees), except with an imposed limitation of increasing node value from left to right. All values that are less than that of the parent node are added to the left branch, and similarly, all values that are greater than that of the parent are appended to the right branch. Using the following image (sourced from programminggeeks.com), let's traverse the tree.
Suppose the values were appended in this order: 8, 10, 3, 1, 14, 6, 7, 4, 13.
The value 8 is situated as the parent node, that much is apparent. Next, the value 10 is compared to 8. It is larger, and thus placed on the right branch. Next, 3 is smaller than 8 and is placed on the left branch; the branches for the binary tree node 8 are now complete, which means that further values to be placed onto the tree are compared with its children 3 and 10. 1 is smaller than 3, and now becomes the left child of 3. 14 is larger than 10, so it becomes the right child. Similarly, 6, 7, and 4 are sorted into their own tree, and the tree ends at value 13 becoming the final left leaf of the node 14. The BST is now complete in that all values can be scanned from left to right in accordance to its literal value from smallest to largest. To me, its implementation is very similar to that of the standard binary tree, barring a condition that would examine each value before being appended to the tree.
Finally, onto the topic of minimax and assignment 2. Assignment 2's main objective was to utilize a system to "plug in" our own methods to a pre-written set of methods provided by the professors. The game that we had to implement was Tippy, or tic-tac-toe with Tetris' Z/S tetrominos. This game was created purposely such that the first player to move was guaranteed a win no matter the actions of the other player: an ideal situation to implement minimax, an unbeatable computer.
After creating my Tippy state and functions, I looked to minimax. It was an algorithm that rated each move on a basis of -1.0 for detrimental, 0.0 for neutral or non-game-ending, and 1.0 for a winning move. By playing out every single possible combination of the board and looking for the best score for itself, the computer would then play accordingly. What stumped me for the longest time was integrating the scores into choosing a move. I had solidly implemented a fashion of rating the moves with their appropriate score, but struggled with deciding which move to play based on the said score - my AI stubbornly randomly chose a move despite there being an obvious winning move.
I consulted Prof. Heap for help, and the solution seemed much more simple than I had thought: I simply wasn't telling the computer that the highest score was the best move (that, and my recursion was a bit wonky). Ironing these little kinks out, my AI worked: it could now crush me every single time,
Monday, 2 March 2015
Sunday, 15 February 2015
Week 6: Object Oriented Programming
OOPS, we're on week 6 already and just finally summarizing objected oriented programming (see what I did there ... again?)
It's been a bit of a ride, having just finished the first midterm and received the marks for both the midterm test and the first assignment. At the start of the year in September, we learned the hard basics of Python programming (by hard I mean literally, not difficulty-wise) - putting together a slab of functions, variables, and nearing the end of the course, classes. That was our first introduction to what was later perceived as "object oriented programming", in addition to "abstract data types". So, that brings us to the painfully obvious question: what exactly is an object? After reviewing some slides and doing some online digging, I came to a simple conclusion:
Everything in Python is an object.
Again, what does this entail? Well, everything in Python, from classes, functions, variables, methods, can all be passed as arguments to other, well, functions, methods etc etc. This means that they can be assigned to variables to be passed and have operations performed upon. Tying it to object oriented programming (or OOP for short), it essentially means that everything I've ever done in Python from the basics of arithmetic to module manipulations and recursions have all been classified as "OOP". Now, with the introduction of abstract data types of creating our own variables and classes, the idea of object oriented programming stretches a bit,
In creating our own variables and classes, I feel that we've stretched the boundaries of object oriented programming, yet at the same time progressed towards a better understanding of the subject/material. Hear me out:
Traditionally, I understood object oriented programming as operating with objects - that is, to create variables, and through a large series of functions/methods/operations, to manipulate and add on to a series of standard variables (str/int/float/list etc), thus the "stretching" of boundaries. Yet with Python and the concept of anything being an object, this fulfills my understanding of the concept of OOP.
It's been a bit of a ride, having just finished the first midterm and received the marks for both the midterm test and the first assignment. At the start of the year in September, we learned the hard basics of Python programming (by hard I mean literally, not difficulty-wise) - putting together a slab of functions, variables, and nearing the end of the course, classes. That was our first introduction to what was later perceived as "object oriented programming", in addition to "abstract data types". So, that brings us to the painfully obvious question: what exactly is an object? After reviewing some slides and doing some online digging, I came to a simple conclusion:
Everything in Python is an object.
Again, what does this entail? Well, everything in Python, from classes, functions, variables, methods, can all be passed as arguments to other, well, functions, methods etc etc. This means that they can be assigned to variables to be passed and have operations performed upon. Tying it to object oriented programming (or OOP for short), it essentially means that everything I've ever done in Python from the basics of arithmetic to module manipulations and recursions have all been classified as "OOP". Now, with the introduction of abstract data types of creating our own variables and classes, the idea of object oriented programming stretches a bit,
In creating our own variables and classes, I feel that we've stretched the boundaries of object oriented programming, yet at the same time progressed towards a better understanding of the subject/material. Hear me out:
Traditionally, I understood object oriented programming as operating with objects - that is, to create variables, and through a large series of functions/methods/operations, to manipulate and add on to a series of standard variables (str/int/float/list etc), thus the "stretching" of boundaries. Yet with Python and the concept of anything being an object, this fulfills my understanding of the concept of OOP.
Subscribe to:
Posts (Atom)