Impression of week 8 --- Binary Tree

This week is about Binary Tree. It is a special case of a normal tree data structure in which each node has at most two children, which are referred to as the left child and the right child. This adds some degree of certainty since each node only have two direction to branch out, either left or right. And this is where a special case of Binary Tree comes into play --- Binary Search Tree. 

BST is essentially a sorted BT in which for every node,  the right child will stores a value that is greater than its parent node, and similarly the left contains a smaller value than its parent.  The purpose for such kind of layout is to increase efficiency. For instance, from the labs, we are able to to search the BST very efficiently since we could avoid visiting unnecessary nodes. 

This week's lab provides a great chance practicing recursion, we call the function on each level of node where we are tackling the same scenario: taking an advantage of the attribute of BST, we could decide which way do we keep recursing.  

impression of week 9 --- I did minimax incorrectly !!!

I should have written about assignment 2 sometime ago, but having a million of other things going on, I didn't even manage to finish it on time. I was stuck on minimax since 6pm on the due date(due 10pm), and I started debugging with my broken minimax till 10pm. Considering even though successfully fixed minimax would probably not give me 5 more marks, I didn't further my struggle after submitting my unfinished assignment 2 to mark us, and then totally forgot about it.

It was not until I saw Danny's code of Minimax on lecture today that I realized I didn't actually implement minimax correctly. Maybe it was due to my lack of understanding of the handout, maybe it's my laziness to seek for help from office hours or TA, maybe it was my own stupidity...but anyways, I was supposed to do minimax in such a way: find out all possible game over states and their scores, for all possible next moves from the original game state, transforming these scores in opponent's point of view and the move with the lowest score is my best move. This would make sure that if there is a move that guarantees a win, we will definitely choose it. Then I decided to redo my minimax.

What troubled me the most is that minimax only process score-move data bundle, and it would only return such a bundle as well, but our suggest_move should only return a Move object, I was stuck on that part for quite a while. The solution turned out to be very simple: use a helper function. We can let the helper function do all the work, and pass the returned bundle to suggest_move, which will extract the desired piece of information from the bundle.

Minimax greatly improve my understanding on recursion as well as many techniques and little hacks of recursion. Recursion is really a power tool, and it marks the milestone of introduction to Computer Science, instead of Programming!

Impression of the week 7 --- Linked Lists

This week we studied linked lists, which is similar to a ''unary'' (base one) Tree where each node has one or no child.  In linked list, each node is directed to the next node in a 'list' of nodes as well as its own value.  And the very first node of linked list is like the root node in a tree, which carries the entire structure, yet it only has direct reference to the next node.

What makes linked list special is its way of inserting new elements to the middle. In normal lists, each element has an index, if we want to insert new item into a certain position of the list, then we will have to move all the elements after that position one index forward to make space for the new item, which will involve lots of unnecessary steps. Where as in linked list, we simply make the two adjacent nodes in that position which used to reference each other, now reference to the new item inserted; and the rest are left untouched.   

However, we do need to loop through the linked list in order to find out the two node which we need to change their linkage according to the index where we desire to insert the item. But intuitively, the worst case of this is in O(n) while the conventional lists insertion is in O(n^2), where n is the length of the list.