Sunday, April 5, 2015

Week 9 Reflections

TEST 2:

This week, we wrote our second term test! I really didn't know how I felt going into it, particularly about linked list, which I was still wrestling with the night before. Overall, I think it went alright. The first few questions were about BSTs and traversing the tree in preorder, which were fairly simple to work with. However, I realize I made a careless error for the list_even_between method we had to implement, which required us to traverse a BST and find all even values in the tree between the lower and upper bounds provided in the method call. In addition, we have to take advantage of the structure of a BST (all left children's values are less than the current node's value, and all right children's values are greater for any given current node that isn't a leaf) in order to avoid checking redundant nodes. Here is my code to achieve this:

result = []
if node is None:
    return []
if start <= node.data <= end and node.data % 2 == 0:
    result.append(node.data)
if node.data >= start:
    result = result + list_between(node.left, start, end)
if node.data <= end:
    result = result + list_between(node.right, start, end)
    

return result

In retrospect, I made an error in the conditions if node.data >= start: and  if node.data <= end:. Considering that I already checked if node.data was equal to start or equal to end in the first if statement, I should not have checked again if node.data was >= start or <= end, rather I should have only checked for strictly > start or < end, because a BST cannot contain the same value twice anyway.  Other than that, I think the method for absorbing linked lists was rather simple if you understand the structure of a linked list, and overall the test went relatively well! Fingers crossed!

WEEK 9 LECTURE MATERIAL:

This week in lecture, we revisited Binary Search Trees, and talked about the code for insertion and deletion in a BST. An interesting analogy I turned to can be found my peer Nana's SLOG at:

https://nanalelfecsc148slog.wordpress.com/2015/03/16/binary-search-trees-week-9/

I found out that binary search trees can be used to construct and maintain ordered lists such as priority queues (similar to simple Queues seen in class, but where each node also has a priority, and nodes with highest priority exit first). Self-balanced binary search trees combined with priority queues create High Performance priority queues. Here is an example.
Let’s assume that we’re running a hospital and there is only one doctor on staff. The first patient walks in. Since there is no one else in queue, the doctor takes him in immediately. The second patient walks in with a cold, so he’s added to the queue with priority 1 and waits for the doctor to become available. Next, a third patient walks in with an axe in his head. He is added to the queue with priority 10, so the patient with a cold is bumped down the line. Next, a man walks in with breathing problems, so he’s added with priority 7, and once again the man with a cold comes last. As more and more patients come in, the queue gets bigger and bigger, and it takes more time to search for the patient with the highest priority. This is when self-balanced binary search trees come in use.
fig548_01_0

This example is a really cool illustration of how BSTs have an impact on our everyday lives. Instead of the doctor browsing through the entire queue in the worst case to find a patient with the highest priority, he could organize his patients in a self-balanced BST with the node value representing their priority level. In order to find the patient with the highest priority, the doctor only has to look at the rightmost leaf, and then traverse in the tree in a flipped "inorder" pattern (visiting right child, current node, then left child). This greatly improves the efficiency with which the doctor can determine which patients require the most attention, and may help save previous times and even lives!
Reading Nana's SLOG inspired me to think about the purpose behind everything we are learning in computer science. Through learning about self-balanced BSTs, I was able to appreciate the efficiency it provides, but what good is this efficiency anyway? I mean, we don't create BSTs for our health, do we? It turns out we actually do (as seen in the above example), and I found this really amazing, because I had never really drawn connections from what we're learning to very necessary real-life operations. Making the connections between BSTs and this hospital analogy excites me, because I am  starting to see how the things we learn in class can make an impact on daily life, and that makes the material much more meaningful to learn!



No comments:

Post a Comment