Last Impressions

    If I had to summarize my experience in CSC148 with one word, it would be "wow!". Honestly, going from CSC108 to CSC148, I didn't think I would be learning much since most people mostly talk about how CSC148 is all about recursion. I guess they weren't wrong... But for me, I feel like I always learned something new every time I walked into a lecture. 

    I have had about 3 years of programming experience from highschool but I never really learned about ADT or OOP so those concepts were very new to me. I feel like I picked up ADT and OOP fairly quickly and easily because Prof. Heap explained and presented the material very well.

    Overall, I can say that I learned quite a lot during this course since people are always talking about how you need to know data structures and algorithm analysis for interviews and etc. I am also looking forward to taking upper year CSC courses where I will learn more concepts about computer science!

Revisit

    For this SLOG post, I will be revisiting an old post and talking about how my opinion might have changed throughout this course... The post that I will be revisiting is actually my first post, "Why Geeks Should Write!".

    In that post, I talked about the importance of computer scientists being able to write. Throughout this course, I found that writing about  my weekly experiences and the material that I didn't understand allowed to to get a grasp of where I stand in this course. It allowed me to see what areas I need to work on to do well in this course.

    Throughout this course, I also found myself browsing quite a few forums about programming i.e. stackoverflow and /r/learnprogramming to ask questions or read about some concepts that I don't quite understand. Overall I think that writing a SLOG has helped me succeed in this course. I also still stand by my opinion about why geeks should write!

Assert, Unit Tests and Call Stacks

    This week we learned about asserts and how to make assertions. Assertions are extremely helpful when it comes to debugging because instead of executing your code line by line in the debugger or printing something after every line or so it will only print when the code does something you didn't expect it to do. In other words, it will print a message telling where things went wrong even though you didn't expect it to go wrong! Pretty useful eh?

    Another thing we covered was coming up with good test cases for unit testing. An exercise we did was figuring out what makes a good test case and what doesn't. So with that being said we starting to come up with test cases to see if our minimax strategy was working properly. We looked at different test cases for minimax being used with our game, subtract square, and we tried to figure out if the test case provided us with information on if our minimax was working. properly. We looked at 3 test cases for subtract square; 9, 10, and 11. After looking at the possible number of winning moves or losing moves each current total for subtract square provided, we concluded that either very little information is given or no information is given about whether or not our minimax was working properly. We then concluded that in order for us to come up with a good test case, the test case required more losing moves than winning moves. Thus we came up with test cases with only 1 winning move and 4 losing moves; 25, 27, 28, and 29. Since these test cases had only 1 winning move and 4 losing moves, the probability of winning all 4 games was (1/5)^4 which is about a 0.16% chance of our minimax NOT working properly but still leading us to the winning move by randomly selecting a move...

    The last thing we covered was the function call stack. At first I was like "what's a function call stack" and about 20 seconds later it hit me... It's pretty much what the name says it is... A stack of function calls. HAHAHAHA! We did an example to show how each function call is added onto the stack and once it has finished it's job it gets removed from the stack and we go back to finish the previous function call.

BST/Term Test 2

    This week we went back to work with the binary search tree. We previously learned how BST work and its uses but we never really got to the code for inserting and deleting an item in a BST. The insert function was pretty easy to implement because if the item we are trying to insert into the tree is less than the current nodes item we would call the insert method on the current node's left tree, but if it's greater than the current node's item we would call the insert method on the current node's right tree (this is when recursion comes in handy because the insert method is constantly called again on different subtrees in the BST until the item we are trying to insert is in its right place). We also worked on the delete function for the BST. I'll be completely honest here... Implementing the delete function was not as easy as implementing the insert function because it required a lot more thought into the possible scenarios that would happen when we delete a node in a BST. We first come up with the algorithm in plain English to see what scenarios we needed to cover:

    # Algorithm for delete:
    # 1. If this node is None, return that
    # 2. If data is less than node.data, delete it from left child and
    #     return this node
    # 3. If data is more than node.data, delete it from right child
    #     and return this node
    # 4. If node with data has fewer than two children,
    #     and you know one is None, return the other one
    # 5. If node with data has two non-None children,
    #     replace data with that of its largest child in the left subtree,
    #     and delete that child, and return this node

    After coming up with the algorithm in English, we put it into code:

def delete(node, data):
    ''' (BTNode, data) -> BTNode

    Delete, if it exists, node with data and return resulting tree.

    >>> b = BTNode(8)
    >>> b = insert(b, 4)
    >>> b = insert(b, 2)
    >>> b = insert(b, 6)
    >>> b = insert(b, 12)
    >>> b = insert(b, 14)
    >>> b = insert(b, 10)
    >>> b = delete(b, 12)
    >>> print(b)
            14
        10
    8
            6
        4
            2
    <BLANKLINE>
    '''

    return_node = node
    if node is None:
        pass
    elif node.data > data:
        node.left = delete(node.left, data)
    elif node.data < data:
        node.right = delete(node.right, data)
    elif node.left is None:
        return_node = node.right
    elif node.right is None:
        return_node = node.left
    else:
        node.data = _find_max(node.left).data
        node.left = delete(node.left, node.data)
    return return_node

    We also had our second term test this week... I feel like a did quite well on the test because I made sure that I understood all the materials by going over the lecture slides and examples and also redoing the weekly labs. But I guess I won't know how well I really did on the test because the TA's are still on strike. Hopefully the strike will end soon...

Linked Lists

    This week we learned about a new data structure called 'linked list'. A linked list is a group of nodes that represents a sequence. Each node in a linked list consists of a data and a reference (link) to the next node in the sequence.

   At first I didn't really understand what a linked list was, but after we worked on a few example methods such as the __getitem__ and append method for our LinkedList class, I started to get a better understanding of what it was and how it works. Since our LinkedList class only had a 'front' and a 'back' it was very clear that in order to access an item (that wasn't the first item or the last item) in a linked list we would have to iterate through the list i.e. walk along the list with a for loop. Another thing that also became clear to me and actually surprised me a bit was that reverse traversing ('walking backwards') can be extremely difficult!

    Due to the TA strike I had a slight bit of difficulty doing lab 07 with linked lists because even though I understood some of the things, there were also a few things that I didn't quite fully understand until I spent some time drawing out a linked list and seeing how to properly implement methods for the linked list.

Summary of Abstract Data Types (ADT)

    Over the past few weeks we've been working with recursion and a few new abstract data types. Since I've already talked about recursion in a previous post, I'll be talking about abstract data types in this post. An ADT specifies a set of operations (or methods) and semantics of operations (what they do), but it does not specify the implementation of the operations (that's what makes them abstract).

    The first ADTs that we learned in class were the Stack and Queue. Both stacks and queues are collections which means that they are data structures that contain multiple elements. They are also generic data structures which means that we can add any type of items to it (int, string, float, etc.). In class we implemented the stack and queue with python lists to use their built-in append, remove, and pop methods.

    A stack is last-in, first-out which means that the last item that is placed onto the stack will also be the first item to be removed from the stack. Our implementation of the stack had 3 main methods: pop, is_empty, and push. Since we implemented our stack as a list, we were able to use the pop method the exact same way for the stack and for the push method we used the list's append method. For the is_empty method we just compared our stack to and empty list, [].

    A queue on the other hand, is first-in, first-out which means that the first item that is placed onto the queue will also be the first item out of the stack (like a line if you were to line-up for something). The implementation for the queue was very similar to the stack. Both the queue method and is_empty method had the exact implementation as the pop method and is_empty method for the stack, but the dequeue method for the queue did not use the list's pop method, it used the remove method instead to remove the item at position 0.

   The next ADT that we learned and worked with was the Tree. Trees simulate a hierarchical tree structure, with a root value and subtrees of children, represented as a set of link nodes. Trees are made up of nodes or vertices with edges without having to cycle. The root of the tree is also known as the top node of the tree and a leaf is a node with no children.

    Another type of tree that we've started to work with is the Binary Search Tree (BST). A BST is a tree where each node contains up to 2 subtrees and each subtree itself is a BST. The left subtree of any node contains nodes with keys that are strictly less than the node's key and the right subtree of any node contains nodes with keys that are strictly greater than the node's key.

   Since BST keep the keys in order it is very easy to find any key in the tree without visiting all the nodes. For example, let's say we want to know if the BST contains the key '7'. We can look at the root and determine which which subtree the key could possibly be in. Since we know that 7 < 8 we can just look in the left subtree (that means we don't even have to look at the entire right subtree!). Now the current node we are looking at has the key '3' and we know that 7 > 3 so we can ignore node 3's left subtree and only look in the right subtree. And since we know that 7 > 6 we can then just look at the right subtree. BAM! We just found '7' in the BST without looking at all the nodes. Now you might be thinking "oh yea, big whop! we didn't have to look at a few nodes and we only saved like 1-2 seconds...", BUT YOU'RE WRONG! Imagine if you have a HUGE BST that is symmetrical in terms of height, each time you compare the keys you are eliminating half the possible subtrees you would have to look through (THINK OF ALL THAT TIME YOU'RE SAVING!).

    Now that we understand how BST work we can easily write some recursive code for it to determine if a BST contains a certain value.

    This first thing this code does is check if there even exists a BST. It then determines if the value we are looking for is less than the current node's value or greater than the current nodes value. If it falls under one of these categories then it will use recursion and call bst_contains on its respected subtree. But if it doesn't fall under one of these categories it will return True because the current node we are looking at contains the value we are looking for!

OOP

    Object-oriented programming (OOP) is a programming language structure that is based on the concept of 'objects', which are data structures that contain all sorts of wonderful information. Different objects can and will have different data (also known as attributes) and different procedures (also known as methods) to do certain tasks.

    Now you might be thinking, "How do we create an object?". Well in Python, objects are instances of classes. So in other words, if you want to create an object, all you have to do is create a class! As we've learned from before, when we create a class, we also need to create the __init__, __str__, __repr__, and __eq__ functions. BUT WAIT!!! These aren't functions! When we write functions inside of a class they are actually called 'methods'.

    I guess the best thing about objects is that it can actually save you time and energy from rewriting code. For example, you can create a subclass for the built-in String class and it will inherit ALL the methods that the String class has! Don't see how that saves time? Go ahead and create a class and try to write ALL the SAME methods that the String class has.

    Just by doing that, MyStringClass has now inherited ALL the methods that the built-in String class has. Don't believe me? Go ahead and create a class like my MyStringClass and use isinstance(MyStringClass, str). It should return True since MyStringClass is a subclass of String.

Recursion

    This past week we started to learn the basics of recursion. Although I have kind of learned recursion before, I was never really able to truly understand it. All I knew about recursion was that the function would actually call itself over and over again until it reaches a condition that makes it stop... Now that I think about it... it's kind of like inception, but instead of going deeper and deeper into dreams you're going in deeper and deeper into the layers of code every time the function calls itself.

    The work we have done so far with recursion is just tracing the code when a recursive function is called with a list and we trace the code with nested lists as well to get the final result. I guess the biggest problem I had with tracing recursion was knowing when to replace calls I've already traced with their value. So with that problem, instead of tracing something like sum_list([[1, 2, 3], [4, 5], ,8]) in 2-3 lines, I would end up tracing each call of the function so I end up with 6 or 7 lines which most of them I have already traced before.

    After doing the lab on recursion, I feel that I have a much better understanding of it and I can trace simple recursive functions without much trouble. But one of the exercises on the lab was to write a recursive function and since we never went over how to actually write a recursive function during the lectures, I had quite a bit of trouble with that. After working on it for a while, my lab partner and I were finally able to write a recursive function. Since the lab ended of with a bit of practice on writing recursive functions, I guess this weeks lectures will teach us how to actually write recursive functions!

First Impressions

    These past few weeks we have mainly worked on class design. We went through how there can be abstract classes that don't really have to do much other than initializing and raising 'NotImplementedErrors' and more specific classes that can inherit methods from the abstract class and do more things with them! I guess a good example of the use of abstract and specific classes would be assignment 1, where we have our abstract game state and our more specific game state for the subtract square game. I guess assignment 1 has really opened my eyes and showed me why the more abstract your class can be, the better it is. I only say that because we've been told that assignment 2 and 3 is going to use the abstract game state and build on to it, so I guess it's a good thing it's abstract and not specific to any game at all or else I'd have to rewrite code... While I'm on the topic of assignment 1... I feel like my partner and I wasted quite a fair amount of time rewriting and modifying our code because we didn't really know what to put in our classes when we first started off. But when we finally figured out how we wanted to design our classes and implement subtract square, the assignment went pretty smoothly from that point on and I feel that we were able to get our abstract classes and our game view class to be as generic as possible (which is good!).

Why Geeks Should Write!

    The past few weeks of this course has been very interesting because we started off the course with OOP (Object Oriented Programming) which I've only worked with a bit back in high school using java. I never really understood OOP in high school but now I feel like I have a better understanding of it since the first  labs was about class design and inheritance. I won't get into OOP too much in this post yet because I'm still not extremely comfortable with it... maybe by next week  I'll have a firm understanding on it after working on A1!    

    During the first few lectures, Professor Heap always talked about how computer science and programming is all about collaboration since no program, website or project can be effectively completed by one person. While he was saying all that, I just sat there and agreed because... well, IT'S TRUE. I believe that no matter how good you are at programming, there's probably someone else out there that's better than you and can give you some advice or help on whatever project you are working on. With all that being said, here's why I think geeks should write (LET'S GO!):

1. Keeping a log for catching bugs: 

    

    After reading through other people's blogs about debugging and keeping a log of the bugs they found, I realized that I should probably write some sort of log on the bugs that I find/fix when I'm writing code since I might run into the same bug again but this time around it would be easier to find the cause of the bug and fix it! It would also give me a better understanding of the bug and why it happened if I kept a log of it since I could read over it and learn from my mistakes so it wouldn't happen again.

2. Documentation:

    If I had to explain the purpose of documentation in code I would use one and only one word... LAZINESS! Professor Heap has mentioned the "three great virtues of a programmer" many times in both CSC165 and CSC148 and of course, laziness is one of 'em. Why bother explaining to a partner/group member multiple time what this line or this chunk of code does when you can just write a small little comment? It will save you all the effort of explaining your code to anyone and everyone!

3. Help each other out!

    Throughout my studies in programming, I have always said to myself "if you've encountered a problem someone else in the world has probably encountered it too or something similar". So with that being said, whenever I encounter a problem and I can't seem to find a solution to it I'll look it up online. Most of the time someone has also encountered a similar problem and has made a post about it on some kind of forum such as: stackoverflow or reddit's own /r/programming. With programmers constantly posting questions and answers on forums you're bound to find a solution to your problem... and if you don't, MAKE YOUR OWN POST! Someone will probably have a solution to it and come to the rescue!

    I guess that's all I have to say about the first couple of weeks in this course and why geeks should write! Until next time! :D