Week 3: Why Geeks Should Write

        Writing is a fundamental skill that is required not only in academia, but also in everyday life. For instance, Life Science students have to write lab reports, English students have to write essays, and even computer science students have to write comments in their programs. Hence, writing is a universal skill that is essential in any subject field. Particularly, in the field of computer science, the benefits of writing include honing our communication skills, helping to keep track of all the important details, and challenging our creativity.

To begin, have you ever been in a situation where you try to explain some scientific concept to your friend, but failed to pass on the idea even though you clearly understood the topic? Well, it means that you did not fully grasp the concept yet. This is because if you actually master the topic, you could have explained it in a way so that your friend would understand. When we write about a scientific topic or even our daily routine, our mind works strenuously in order to express our thoughts in a way for readers to understand. This process requires the writer to constantly rethink about the concept that is to be written, and forces him/her to express ideas in a coherent manner. The writer only finishes the writing when he/she has fully explained and mastered the concept themselves. Hence, writing perfects our communication skills by practicing our abilities to express ideas clearly and explain concepts in a logical way. Also, writing clarifies our thinking by forcing us to solidify our thoughts and knowledge and put them in a cogent order. In the study of computer science, the ability to express ideas are involved in writing comments in programs. This is because programming usually involve a team of programmers who each write code for different parts of the program; therefore, comments are necessary in order for colleagues to understand their partners’ codes. Furthermore, writing practices our ability to think logically, which enhances a programmer’s skill to program in a logical manner.

Secondly, according to Steve Rydz's (http://steverydz.com/2013/11/19/keeping-a-debugging-journal/) and Tinypig’s  (http://tinypig2.blogspot.ca/2011/06/keep-debug-journal.html) slogs, keeping a debugging journal is extremely helpful. By recording problems and hurdles encountered during programming and their respective solutions, the programmer can see his/her own blindspots and identify troubling areas that call for improvement. Furthermore, if in the future a similar problem is encountered, the programmer can quickly remember its solution by reading previous journal entries. Or even better, the programmer can quickly come up with a solution right on the spot, because he/she understood the problem from writing down the solutions before. Thus, writing a debugging journal helps the programmer to better understand his/her own weakness, and reinforces the programmer’s understanding.

Finally, programmers don’t have to write about academic articles, rather, they can write about anything. Even if the writing is about the writer’s complaints and daily routines, or even a random anecdote or short stories created by the writer. This is because writing itself forces the writer to constantly come up with new and creative ideas. By simply just writing about anything, a programmer can enhance his/her ability to be innovative and creative. Furthermore, innovation is a vital part of programming since algorithms require creative solutions. Thus, in conclusion, programmers should view writing as a daily homework, and spend at least ten minutes everyday just to write.  

Week 12: Reminiscence and last week of class!

        In the last week of class, my emotions were a mixture of euphoria and nervousness. I am elated that summer break is approaching, however I am also nervous about the upcoming exams. Here is a summary of what was taught each week:

Week 1: Review of CSC108 where the  implementation of class was learned. Init, and eq methods were reviewed.

Week 2: Continue to review CSC108 regarding the implementation for rep and str methods. The property mechanism was taught along with introduction to abstract data types such as stack and queue.

Week 3: Introduction to exception and tracing recursions

Week 4: More tracing of recursions

Week 5: More on recursion along with the review of writing unittest.

Week 6: Structure and implementation of a tree involving usage of recursions (count_leaf, count_node, etc.)

Week 7: Binary search tree and three methods of tree traversal (inorder, postorder and preorder).

Week 8: Class LinkedList and LLNode. Recursion was practiced through writing methods for LinkedList (append, prepend, delete).

Week 9: More implementation of binary search tree and recursion.

Week 10: Discussion on assignment 2’s strategy minimax. The professor also taught ways of choosing test cases for an unittest.

Week 11: Types of sort such as quick sort, merge sort and etc. Also definition of big-O and time complexity such as lg(n) are taught.

Week 12: Leaning more about big-O

Looking back over the course, I realized that more than half of the materials learned in class involved implementing recursion. Hence, I should focus more on practicing recursions in order to prepare for the exam. Furthermore, throughout the term, although I have encountered many conceptual hurdles, I solved them nonetheless. Some major conceptual hurdles include understanding recursion and linked lists, where both problems were already discussed and resolved in my slogs. Lastly, strategy minimax in assignment 2 was the most difficult part in all three assignments. What made writing assignment 2 much harder was that help centres are unavailable due to the strike. Hence, I am really glad that strike is over. 

In conclusion, although I used to dislike writing slogs, I now find it really helpful. I would definitely recommend later years to write weekly slogs  since writing improves the understanding of complicated concepts.And lastly, I wish everyone good luck on their respective exams!

Week 11: Everyone had a mental breakdown. I am not the only one.

        After revisiting my week 8 slog, I felt ashamed to have blamed my inability to do assignment 2 on the professors. As a recap, in week 8, my group and I had trouble writing strategy minimax. And when we went to office hours, the professors told us to figure things out on our own. Out of frustration, I complained about the incident in my slog and declared office hours to be useless. Now that I look back, I had to disagree with my previous opinion. As a matter of fact, Danny and Diane did provide some hints regarding minimax, however, they couldn’t tell us the exact way to tackle the problem since that will be telling us the answer. Moreover, they even sent an email to the students describing the approach to the problem. Furthermore, minimax wasn’t as hard as I though it would be since my group managed to finish it in week 9. Although our approach to minimax differed completely from the standard answer, it ran perfectly nonetheless. Out of self interest, I also read over my other older slogs and discovered that I still agreed with the majority things I once wrote. For instance, in Week 4, I mentioned the CSC148 is significantly harder than CSC108, and that I was not used to this fast paced learning environment. Well, I still feel the same, especially when the strike is still continuing and no help centres are available for me to ask questions. Just when I got used to my new schedules and courses, the strike happened and messed up my pace. I now lose the opportunity to get extra help, and have to spend longer time struggling to understand new course materials on my own. Similar to my first three weeks, everything was a struggle as I tried to get used to another new environment. However, I also felt relieved to have solved many complicated topics in my slog. Each time I had some problem regarding recursion (in week 5), OOP (week 6), or inked lists (week 10), I always try to figure things out on my own. After I have fully mastered these concepts, I write them in my slog and explain them in a way that can help other readers’ of my slog master the material. Now that exams are imminent (a month go by really fast!), I realized that studying for CSC148 is so much easier since I already understood all the concepts taught in class. Hence, slog is useful for learning purposes since it reaffirms my comprehension after I tried to explain them in words. 

         Out of interest, I read over some other people’s slogs and discovered that they also had difficulties with assignment 2. For instance http://egq148.blogspot.ca/ mentioned in “The Seven Week Itch” that he/she also had some problems with minimax. Interestingly, one thing mentioned by the blogger caught my attention since it coincided with my previous thoughts: “How are we supposed to write a program that can never lose, if we ourselves are always capable of losing?” I remembered when I had problems with A2, I also felt like minimax is an impossible task. Furthermore, I also read Jingyu’s slog and discovered that we had the same problem regarding the method delete in linked list. (I mentioned that I had trouble understanding linked list in week 10. Similarly, Jingyu also expressed her frustration with delete in her week 10 slog). The difference between us is that I figured out how delete works on my own, whereas Jingyu didn’t. Hence I messaged Jingyu offering her my slog. Hopefully it will be helpful. 

        In conclusion, I want to thank Huan Ling, Jingyu and some other people for mentioning me in their slogs. At first, I disliked writing slogs and considered them to be a waste of time. However, slog is a great tool for learning since it helped me clear out my own misunderstanding regarding certain concepts. Furthermore, I felt accomplished that other readers also found my writing to be useful and helpful. Lastly, I want to mention Christian’s slog. His slog has helped me understand various complicated concepts. And one thing that I really liked about his slog is that he would relate the class materials to some other applications such as math. For instance, in week 7, he related recursion to the Fibonacci sequence. Because I am also in the math major, seeing a topic that is of my interest really helped my understanding. Moreover, his slogs are visually appealing and I liked his choice of pictures. Here is a screenshot of his beautifully done slog:

Jingyu’s slog: http://jingyuwang148slog.blogspot.ca/

Huan Ling’s slog: http://huanlingslog.blogspot.ca/

Christian’s slog: http://christiangarciacsc148.blogspot.ca/

Week 10: My impressions of week 9

         Like Week 8, Week 9 was also a busy week since I had multiple assignments and tests, including the second term test for CSC148. I mentioned in last week’s slog that I didn’t thoroughly study linked list, and that I hope nothing related to deleting nodes will be on the test. Unfortunately, according to Murphy’s Law, “anything that can go wrong, will go wrong.” On the third and last question of the term test, I had to incorporate the idea of deleting nodes. After the test, I discussed my answers with fellow classmates and not surprisingly, my answer for question 3 was wrong. The good thing was my answers for question 1 and 2 were correct. So hopefully, part marks can be given on my attempt at question 3.

        Because of my lack of understanding regarding linked lists, I decided to re-learn the class materials. With the help of my friend a person's slog, I finally learned the structure and implementation of linked list. One important tool that my friend taught me in order to understand linked list is to draw pictures. To begin, linked lists are lists made up of connecting nodes. It is shaped like a chain where each node is connect to only one node. In technical terms, linked list represents a sequence of a collection of objects (nodes) with a value and a reference to other similar objects. To understand its structure better, drawing pictures are really helpful. Here is a pictorial representation of linked list: 

To be more specific, linked list consists of two classes. The first one is called LLNode and it represents one single item (node) in the linked list. This object stores the value of a particular node, and the value of the next node connected to that particular node (represented by the ‘next’ attribute in the init method). The diagram above refers to three distinct nodes connected in the form of a linked list. The first node has the value 1, and its ‘next’ attribute refers to the second node with the value 2. The second class is called LinkedList, which represents the entire list with nodes connected in a particular order. It contains three main attributes, the first being the value of the frontmost node (stored by the variable ‘front’), the second being the value of the last node of the list (stored by the variable ‘back’), and the last being the number of nodes in the linked list (stored by the variable ‘size’). In the above diagram, ‘front’ refers to 1, and ‘back’ refers to the value 3, whereas size refers to 3 since there are three nodes in total. Furthermore, many other methods such as append, delete_front, prepend and __contains__ are also implemented in the class LinkedList. 

        The part that I had the most trouble with was deleting a node. Now that I learned to draw helpful diagrams, the concept of deletion doesn’t seem as hard. To delete a node with a designated value after its first occurrence involves assigning a variable called cur_node (current node), which keeps track of the value of the current node. Here is what the code looks like:

Basically, the code means if the first node exists and has a value, make the variable cur_node refer to that first node, represented by lnk.front. Then continue to traverse down the list looking for the node with the selected value. In case the entire list does not contain the value we are looking for, we have to accompany the while loop with the condition that cur_node always has to exist (not None). Furthermore, if we did not find the node with the value we are looking and the list still has unvisited nodes, assign cur_node to the next, upcoming node. Now, the while loop either terminates if we already searched through the entire list or if we found the node with the value we are looking. If after traversing the entire list, no node contains the value, the if statement determines what to do. If cur_node refers to the value None, it means that the entire linked list does not contain the value we are searching for, hence nothing happens. However, if cur_node exists, we either delete the node after it (if cur_node is not the last node of the linked list), or we do nothing since cur_node is already the last node of the list (the ‘back’ of the list). Here is a diagram:

If the value we are searching for is 55, cur_node will at first refer to 17. Since 17 does not equal to the value we are looking for and cur_node is not None, cur_node is now assigned to be the next node with the value 23. Just like 17, 23 also does not equal to 55, hence cur_node now refers to 55. Since cur_node == 55 == value, the while loop terminates. According to the if statement, cur_node and cur_node.nxt both exists. Hence, the body of the if statement is being executed. Since lnk.back is not cur_node.nxt (meaning node 72 is not the last node of the list), cur_node.nxt will be equal to cur_node.nxt.nxt. This means in the node with the value 55, its attribute ‘next’ will now refer to the node with the value of 14 instead of 72, hence deleting the node with the value 72. Moreover, the size will be decrease by the value 1. Now, if 14 is the value we are looking for, cur_node will end up referring to node with value 14. Since 14 is the last node of the list, cur_node.nxt is None, and nothing happens because the if statement never gets executed. Let’s say the value we are looking for is 25, which is not in the list. In the end after traversing through the entire linked list, cur_node will refer to None, since cur_node = 14 and cur_node.nxt will be None. Similar to the previous example, nothing will happen.

        In conclusion, drawing pictures are sometimes critical for understanding complex data structures. Despite the fact that I was occupied with tons of work last week, I am really satisfied with myself and my problem solving attitude.  In the end, I want to thank the person who wrote the slog http://egq148.blogspot.ca/ since it helped me understand linked list and how it works. 

Week 9: My impressions of week 8

        Week 8 was both a happy and sad time for me due to three major incidents. The happy event was that my group and I successfully completed the code for strategy minimax two days before the deadline. And the sad parts of the week was that I handed in the wrong file during submission, and that I failed to fully prepare for a test.

        Now, I will begin with the happy part of my recount from last week. As a recap, during week 7, my group had trouble implementing strategy minimax. Fortunately, after discussing and thinking for multiple days, we were able to come up with a solution. During multiple group meetings, my group and I knew we had to use -1 as a multiplier to change the score after the player switch turns. However, we were unable to multiply the multiplier into the score list because it contains many lists of inner lists. After thinking about the solution for days, my partner had an interesting idea of using both the max and min function to calculate the score. We then created two functions, where one was called max and the other was called min. And we used the min function within the max function, and similarly, the max function within the min function. In this way, during a game between the player and the computer, the max would return the score of 1 when the computer is the next player, while the min would return the score of -1 to the computer when the opponent is the next player. The min function served a similar purpose as multiplying the opponent’s score by -1 in order to obtain the computer’s score. Proud of our creativity, we successfully completed the code and showed it to Danny and Diane, to which they both replied the word “interesting.” Although our code might deviate from the standard answer that the professors’ expect, my group and I were proud for our completion of assignment 2 nonetheless.

        Despite the above mentioned celebratory accomplishment, my group quickly ( and ironically) realized that we had submitted the wrong version of assignment 2 only after the submission deadline. We then quickly re-submitted the right files and regretted our loss of 5%. From this mistake, my group and I learned to submit the assignment at least an hour ahead, and run our submitted program before the submission deadline. Switching to another topic, Lab 7 was also a challenge. Because I skipped classes in order to have more time thinking about strategy minimax, I missed the lecture about linked list. Hence, when attempting to do the lab on my own, I failed to come up with the implementation for functions such as delete_front and prepend. Furthermore, I had no idea how to delete a middle node and then connect the front node to the back node. Because I had other tests and assignments due in the same week, I didn’t have the proper time to master linked list. And to my dismay, the third question of test 2 involved deleting nodes. 

Me during week 8

        To sum up, last week was like an emotional roller coaster ride. I went from being extremely happy to being disappointed of myself in the end. Although I was able to complete assignment 2, I failed to hand in the assignment on time due to my carelessness. Moreover, my failed time management skills left me unprepared for upcoming tests. Hence, from last week, I realized I had to change my study habits in order to catch up to the missing school work. When submitting assignment 3 in the future, I should submit at least an hour earlier.

Week 8: My impressions of week 7

        Truth be told, I was at the verge of a mental breakdown last week due to Assignment 2. Learning from the mistake of Assignment 1, my group and I decided to tackle the second assignment 10 days earlier, so that we can visit office hours more frequently. However, the office hours proved to be utterly useless as both professors responded to my group’s questions with ambiguity. To my frustration, whenever a question related to strategy minimax was asked, the professors would reply: “I will leave that for you to think about.”  Well, I wouldn’t have attended office hours if I hadn’t already thought about the assignment throughly and get stuck for days. I know my complaint might sound obnoxious and whiny, however, it was difficult to restrain my anger after wasting my class time going to helpless office hours that I had to sacrifice class time for. Now, TippyGameState, TippyMove and GameView were quite easy to write since they are similar to that of a Subtract Square game, and after a few hours, my group and I were able to finish the code. On the opposite, strategy minimax seemed impossible to derive an algorithm. My group and I spent two whole days discussing ideas and solutions to strategy minimax, and whenever we began implementing our ideas, we get stuck writing the code halfway. After multiple fruitless attempts, and after abandoning many ideas, my group decided to attend office hours, which later turned out to be time wasting and useless. 

        Despite facing an unprecedented obstacle, such an unhappy event did not deter me from showing an interest in binary search tree. Due to my fascination and curiosity with such a brilliantly structured tree, I decided to do a quick research on its origin and inventor. From Wikipedia (I know it might not be the most credible and reliable source, but it is the quickest way to research about materials), I learned that the binary search tree (BST) was invented in the 1960 by Windley, Booth, Colin and Hubbard. Each node in a BST contains a maximum of two children, whereby the left node contains a number smaller than the number on the parent node, whereas the right node contains a number larger than the parent node. This structure is very important because it shortens the time of search by half. Relating to the BST is the methods of traversing the nodes. There were three ways of traversal taught in class. The first one was preorder traversal:

Order of traversal: F,B,A,D,C,E,G,I,H

The second one was postorder traversal:

Order of traversal: A,C,E,D,B,H,I,G,F

And the last was inorder traversal:

Order of traversal: A,B,C,D,E,F,G,H,I

At first, the professor’s definition was a bit confusing to understand since it lacked a clear picture. However, after being shown pictorially how to traverse the binary tree in all three orders, my confusion was cleared.

        In conclusion, my impression of last week was horrible due to my inability to write code for strategy minimax. In order to remember the parts where my group and I had problem with, I summarized three major questions regarding strategy minimax:

1. How to derive the scores of the next possible game states using recursions?

2. After computing all the scores, how to select the best score?

3. Lastly, upon determining the best score, how do I associate the score with its corresponding move?

Hopefully, my group is able to solve these problems before the assignment is due.

Week 7: My summary of Abstract Data Types

           Stack, an abstract data type(ADT) was formally introduced to me during week 2 lectures by Professor Danny Heap.  Later, during tutorials and lectures, I also became familiarized with two other ADTs called queue and tree. Although I understood the application of stacks and queue, I still could not understand why they are called abstract data types. Moreover, I was unable to discern the difference of ADTs from other built-in data types such as list, dict, str and tuple, etc,. Hence, in today’s slog, I will be giving a detailed summary on ADT as well as introducing the three examples of ADTs I encountered in class.

          First of all, an abstract data type is a model for a particular data structure defined by the methods it can perform. One thing to keep in mind is that not only can ADT be implemented in python, it can also be implemented in other programming languages like C, java, etc,. This is because ADTs do not contain detailed codes on their implementation. In other words, ADT is concerned only with what the data is representing in general but not the the specifics for its construction.

          Now, I will discuss the definition and purpose of stack. A stack is used to store countless data in an order in which new items are added to the top of the stack, while the top item always gets removed. Hence the acronym LIFO, which stands for “last-in-first-out” is used to describe stack.  Furthermore, stack includes three basic operations. The first method is push(item), where the new data is added to the top of the stack. The second operation is pop() which functions to remove the top (also last) item from stack. And the last method that I was introduced to in class was isEmpty(), which returns True if the stack is empty, else False if the stack contains at least one item. Although Danny did not teach the class all the methods related to stack. I was able to learn them on my own due to my incessant curiosity, After researching online, I discovered that stack also included other operations such as peek(), which returns the topmost item from stack without making any modifications to the stack, and size(), which returns the number of items in the stack. Lastly, real life applications of stack are stacking of plates or books. To see the example calls on these methods, check the link:

http://interactivepython.org/runestone/static/pythonds/BasicDS/TheStackAbstractDataType.html

          The second ADT that I learned is queue. And I learned it in a tutorial as I was told to write my own code on implementation of queue. Similar to stack, a queue also stores data. However, it operates in a FIFO fashion, which stands for “first-in-first-out”. It includes three basic methods (these are the methods I was asked to write during my CSC148 lab). The first operation is enqueue(item) that adds a new item to the the rear of queue. In other words, as items are being added to a queue, the first item is being pushed to the top. Thus, the last added item is at the bottom of queue, which is different from that of stack (as aforementioned, the last item to be added locates at the top of the stack). The second function is dequeue() that serves to remove the first and topmost item from the queue. Lastly, similar to stack, queue also has a method called isEmpty() that returns True if queue contains no data, and false otherwise. Moreover, queue also has the operation size() that returns the number of items stored in it. The real life applications of queue are people lining up to board an airplane or buy tickets from a ticket booth. Lastly, its example calls can be viewed by clicking the link: http://interactivepython.org/runestone/static/pythonds/BasicDS/queues.html

          The third and last ADT I learned is tree. To begin, similar to stack and queue, tree also stores data. However, it stores data in a hierarchical order. Each item/object is called a node, and we refer to the bottom nodes that happen to branch out the top node as the children of the top node. Furthermore, nodes without any children is referred simply as leaves, whereas, the top most node is called the root. Functions for trees that I was taught in class and tutorials included determining the height of the tree, the number of children, etc,. So far, the class only looked at binary trees (trees where a node only has a maximum of 2 children, called the left and right subtree) in great detail. To sum up, the ADT tree is a real world tree flipped upside down. In my CSC148’s assignment two, I will be combining recursion with tree to assess every possible outcomes of the Tippy Game, and then return the best strategy for the player to win the game. (This idea is required in the class called StrategyMinimax).

          In conclusion, throughout these 7 weeks of class, I learned about abstract data types and its three specific examples — stack, queue and tree. Up until now, the most difficult ADT I learned is tree. However, I have no problem understanding its structure and implementation, since my quizzes about count_leaves is perfect, and I was able to complete the labs regarding trees in a efficient and speedy manner. One thing about tree that I enjoy is its frequent application of recursion. This is because I find writing recursions challenging yet satisfying at the same time after reaching a solution. Hence I was elated to find out that I will be combining both tree and recursion in Assignment 2’s StrategyMinimax. So far, my group has completed the codes for TippyGameState and TippyMove, and we will be writing StrategyMinimax tomorrow. Hopefully, my group can finish the GameState by Monday. Lastly, the advantages of using abstract data types is that ADTs can be reused in future programs. Further,  their implementations can be easily modified without having to make troublesome changes to the program that uses the ADTs.