Every day for the past two weeks, my friend’s stream of Facebook posts poured onto my timeline, engulfing my entire newsfeed with photos of him and his latest girlfriend, having such a comical time together. They can’t get enough of each other. They really can’t. They are glued at the hips. They must share every dish of food. Pictures and pictures of them gazing passionately into one another eyes.
Then, suddenly, his posts seemed to stopped appearing on my feed. At first, I made an assumption that Facebook’s algorithms was becoming so advance that it somehow read my mind and purged all posts that I considered rubbish. But I was wrong. I hopped on over to his Facebook page and low and behold, most of his recent posts are gone. Vanished. Disappeared. Well, not all of them, just the ones with his girlfriend. It’s as if she never existed. What did replace those posts, though, were images with itaclized inspirational quotes on how to avoid dating a sociopath.
Then, no more than one week after they had presumably broken up, he began posting pictures of them together.
I cannot seem to find the right word that encapsulates how I feel about the entire situation. But, I do find it interesting. Interesting that you can digitally erase someone from your history, as if you never met the person. One click here, one click there and poof, problem solved. You’ve rewritten your entire history (it’s like gitrebase, but for your life instead of source code).
I find that unless the material you are posting is self incriminating, it should be left in tact. Those memories—failed relationships, embarassing moments during your drunken stupor, convictions of being with “the one”—are an important part of your story. It paints an important picture. They tell us who you are, and perhaps how much you changed. So please, don’t delete your history. I genuinely want to know if you dated a sociopath.
I’m pursuing a master’s degree in computer science and most of the schools I’m applying to— Seattle University, University of Washington, University of Southern California — require that I take the general GRE (graduate record examination). Although I don’t necessarily agree with standarized tests, especially the GRE, I recognize the necessity to establish some sort of bar for applications. So, instead of fighting the process, by attempting to convince admissions to waive the GRE requirement (although some do), I reluctantly scheduled my exam for December 16th. That’s gives me about two months to study.
That’s not a whole lot of time to prepare. Magoosh, an online platform that prepares exam takers, suggests that most students should aim to study for about three to four months: ain’t nobody got that time for that[1]. Therefore, I’m condensing my studying to two months. This plan of mine will still require anywhere between two and three hours, every day.
So, here it is. There’s a myriad of resources available (I’m starting to think that the GRE is a cash cow. Money flows between Educational Testing Service and the institutions, I think) and I’ve made a conscious reduction of the material:
Working the normal nine to five job leaves little time for personal reading, which is why every morning, as soon as I situate myself on the bus, I immediately rip out a book from my backpack and read. I guard this meager time like a gambler and his poker chips. Without these short thirty minute rides to and from work, I wouldn’t have been able to finish 1984.
But I did.
Flipping to the final page, uttering the final line of 1984, left a gaping hole in my stomach. A profound sense of loss. It’s rare for a book, or anything for that matter, to leave me devastated. I just sat there, on the couch, with the book folded over my lap, staring into space. Contemplating.
OBrien’s systematic interrogation — broken down into three concrete phases — destroyed Winston mentally, emotionally, and physically. By the time Obrien had finished with Winston, he was only a “shell of a man”.
Big brother won.
On the plus side, though, the timing of reading the book could not have been more perfect. Had I been forced to read this in highschool (it’s not uncommon for this book to be compulsory reading), my unprepared mind would not have been able to process Orwell’s distopia . With the global surveillance programmes revealed (thank you Edward Snowden) is the idea of big brother that out of the question ? I think not.
You know when you are reading, mid paragraph, and you stumble across a unexpectingly beautiful sentence? Here’s one of my favorite quotes, when Winston has an empiphany, in the final scene, as he’s being painfully tortured:
Perhaps one did not want to be loved as much as to be understood
I’m returning 1984 back to Billy, my book shelf, with plans on re-reading the book. It’s definitely worth a second read.
My plan on completing Data Structures and Algorithms in Java by December 31st, 2016, requires changing my reading strategy. Reading technical books cover to cover, like a novel, is rewarding but inefficient and impractical. How about a different approach ?
I’m applying active reading principles from How to read a book[1] and A mind for numbers: active reading by questioning author’s intention, indentifying questions author is attempting to answer.
I skimmed the 15 chapters (although I had already read the chapters on maps) and below are my notes.
The skeleton
Before I skimmed each chapter, I paused and flipped to the page that maps each chapter/section to the ACM[2]. I bookedmarked this page because it helps frame the entire study session — constant questioning of what, and why, I am reading the material.
Mapping between book and ACM guidelines
Chapter 1
Introduction to java and basic programming principles. Conditionals, loops — basic stuff.
Chapter 2
Object oriented design. Introduction to design patterns such as the adapter pattern. The three criteria for good software: robustness (handling unexpected inputs), adaptiblity (adapting to changes and requirements), reusability (reusing code somewhere else).
Chapter 3
Fundamental data structures including arrays and linked lists — singlely, doubley and circular linked lists. Covers the advantage of implementing linked lists over arrays, and vice versa. Compares shallow and deep copies: shallow method copies pointers but deep instantiates another copy of the reference.
Chapter 4
Establishing nomenclature for comparing performacne: big-o. The question of what and why big-o notation, and its history. The three levels of performance: best, worst, and avergae. The 7 mathematical functions, described in ascending order, from best to worst:
Constant time
Logaritmic
Linear
N(Logarithmic)
Quadratic
Cubed
Exponential
Chapter 5
Recursion. Impleneting a recursive search algorithm: binary search. When is recursion a bad idea? What a tail recursion is and how to eliminate it.
Chapter 6
Additional data structures. Introducing additional abstract data types (ADT): stacks and queues. Two primary methods of implementing a stack: array and linked list. Leveraging modulus technique to maintain a circular queue. Dequeue, pronounced as “deck”, implements properties of both stack and queue: add to head or tail, and remove from head or tail.
Chapter 7
High level concept of object oriented programming. Instead of relying on the client to initially size the array, a more client-friendly solution is offered: dynamic arrays. The iterator interface is introduced, as well as positional lists.
Chapter 8
Generic trees and ordered trees – including binary and binary search trees, and techniques to traverse: preorder, postorder. Peek at breathe depth first — I thought this concept was reserved for graphs. The chapter ends use cases and trees can model and solve real problems.
Chapter 9
Additional ADT: priority queue, which can be implementing with a positional list or a sorted list. The positional list offers O(1) to insert, but is O(N) for retrieving the minimum. The sorted list can, instead, offer O(1) for minimum but O(N) for inserting. Is there a data structure that offers the best of both worlds, something in between? Yes. The Heap. The heap offers log(N) for both insert and retrieving the minimum value. Additional features, such as removing an entry (not minimum) from a priority queue, require adapting the ADT.
Chapter 10
The map ADT is introduced. A primitive data structure to implement a map, via an array, is introduced, by followed the hashtable. The chapter ends with sorted maps, skip lists and sets.
Chapter 11
Binary search trees, a special type of tree. To combat the worst case scenario (inserting sorted items produces, effectively, a linked list) another ADT is introduced: AVL trees. Two other balancing trees are introduced: splay and (2,4) trees. Chapter ends with Red-Black trees.
Chapter 12
Up until Chapter 12, only two elementary sorting algorithms have been introduced: insertion sort and select sort. Divide and conquer, an algorithm design pattern, is introduced with two concrete implementations: merge and quick sort — both with a runtime complexity of O(nlogn). Radix and bucket is an improvement in runtime complexity — O(N). The concept of stable sorting algorithms are introduced, and we face another type of issue: selecting the correct items.
Chapter 13
Pretty neat topic on tackling “string matching.” Discusses a primitive method for string matching — I think we can I guess how this brute force method works — followed by advanced techniques: The Boyer-Moore algorithm and Knute-Morris-Prath Algorithms. Covers compression algorithms, including the huffman code. Covers dynamic programming, a method for matching a sequence of strings but reduces the runtime complexity, from exponential, by implementing “a few loops”.
Chapter 14
Introduces another ADT – graphs and respective terms: edges, vertices, directed, undirected. Presents two different strategies for keeping track of neighbors: adjaceny matrix and adjancey list. Discusses (2) methods for searching for nodes: depth search first or breathe search first. Covers several methods for constructing a minimum spanning tree. Like OSPF, introduces Dijastreka’s algorithms for determining shortest paths.
Chapter 15
Dives into characteristics of JVM: garbage collection. Introduces the PC — not personal computer — to keep track of function/procedure calls. Compares the types of memory and the hiearchy in terms of performance. How data is stored on external disks, such as B-Tree.
Footnotes
[1] – How to read a book – http://pne.people.si.umich.edu/PDF/howtoread.pdf and a similar article: https://www.farnamstreetblog.com/how-to-read-a-book/
[2] – ACM – https://www.acm.org/education/CS2013-final-report.pdf
I’m an early bird. I find that I’m the most productive with a little extra time in the morning, which I devote to personal development — meditating, reading, and writing. I wake, usually, to the sound of the alarm; today, though, I woke up naturally. Or so I thought.
I glanced at my watch. 05:30AM. I gave an approving kudos to my body for blessing me with an extra 30 minutes to kick start the day. But it was not until I reviewed arlo that I uncovered Maxella, my sister’s German Shepherd, struggling to sneak into my bed — her lack of finesse and lion sized paws sent a small wave of vibrations through the bed, enough to wake me up.
I’m slowly working through “Computer Systems from a programmer’s perspective” [1] , struggling every bit of the way. I stopped beating myself up about it, though.
The code snippets below are in C. The first function, inplace_swap, swaps two integers. The code itself looks lacks intent but I promise you, it swaps two integers.
The second function, reverses an array. Coming from the Python world, I wondered why in the world we need to pass incount as an additional argument. I discovered the additional argument is absolutely necessary. C functions will always collapse array arguments into a pointer. The length of pointer, which is nothing more than a memory address, cannot be calculated [2].
The author reveals there is a bug and poses 3 questions:
For an array of odd length cnt = 2k + 1, what are the values of variables first and last in the final iteration of function reverse_array?
Why does this call to function xor_swap set the array element to 0?
What simple modification to the code for reverse_array would eliminate this problem?
In an odd length array, the variables first and last values are the same. This explains why the middle array element is set to 0. Any number XOR’d with itself will always produce 0. Here are a few examples of XOR’ing two binary values of the same value:
0001 ^ 0001 = 0000
0111 ^ 0111 = 0000
I grew frustrated with the last question. For ten minutes, I held back my impulse to flip to the back of the book and reveal the solution. Instead, I slapped a piece of a piece of paper and a pen onto my desk, and stepped through the each iteration. There’s something about putting the pen to paper, that activates a different part of the brain.
In an array with odd number of elements, the middle item is always in its final position. We should never call inplace_swapfor the middle item. Instead, we change the condition in the for loop from first <= last to first < last.
Last week, an e-mail was sent out to an internal mailing list [1], looking for volunteers to lecture on data structures & algorithms topics, but nobody replied. I jumped at the opportunity. I volunteered to lecture on binary search trees, without any previous knowledge on the topic. Why in the world would I volunteer to teach something that I know nothing about ? Well, one of the best ways to learn something is attempt to teach it. I love teaching as much as I love learning; teaching forces you to deeply understand the subject, internalize the material, and requires distilling the concepts into digestible bits and pieces. Here’s Ken Thompson’s advice [2].
But I love teaching: the hard work of the first class, the fun of the second class. Then the misery of the third.
—Ken Thompson
In the post, I’m covering what a binary search tree is, its structure, and the basic operations: find, insert, and delete. We also cover the three methods for traversing the tree. At the end of this post are practice problems to help drive the concepts home.
Next is an example problem that glues the concepts together.
Example: Badging in & out of the office
Picture an office requiring employees to badge in and out as they enter and exit the premise. We want to keep track of the employees in the building. We also want to be check if a specific employee is currently in the building. Let’s implement a binary search tree to maintain this dataset.
As employees badge in, we insert the Employee object (using the employee ID as the key) into the three. When employees badge out, we remove them from the tree. Occassionally, we search the database asking “Is Employee X currently in this building?”
Tree structure and performance
What do binary search trees offer over other data structures [3] ?
The binary tree data structure elegantly combines the flexibility and benefits of two existing data structures: linked lists and arrays. Linked lists efficiently add and delete nodes, by updating pointers, but inefficiently search. Linked lists require iterating over every node (i.e “from the head of the list”) until the desired node is found. Arrays, on the other hand, are perfect for searching – when taking advantage of the index – but are unsuitable for insertions/deletions. When inserting at a[i], all indexes greater than i must be shifted up; when an item is deleted at a[i], all indexes greater than i must be shifted down.
This table compares the average runtime complexity of the three data structures.
Data Structure
Search
Insert
Delete
Arrays
O(1)
O(N)
O(N)
Linked Lists
O(N)
O(1)
O(1)
BSTs
O(logn)
O(logn)
O(logn)
Binary search trees are suitable for specific problems. Binary search trees can be used to solve problems such as runway reservations [3]. Before we dive into the structure and implement the methods, let’s cover some terminology.
Tree Terminology
Here’s a visual representation of a binary search tree.
15
/ \7 21
/ \5 10
A tree consists of nodes that are connected by edges. Those lines above represent the edges.
Path – Walking node to node, along the edges, creates a sequence known as the path.
Root – The node at the very top of the tree. There is only one root in the tree.
Parent – Every node, except for the root, has an edge connecting to the node above it.
Traverse – checking or performing an operation on the node
Leaf – a node that contains no children
Level – The number of generations from the root node (level 0). For example, the root’s childrens are at level 1.
Structure & Operations
The structure of a tree is straight forward. It contains a reference to its root node, which is an instance of the Node class. TheNode class contains two references: leftChild, rightChild. The leftChild references a node whos key (i.e “used for comparing”) is less than the current node’s key, and rightChild references a node with a key greater than the current node’s key. This ordering restriction is a property of BSTs, but not all trees.
Searching for the node is quite easy. Our method, find, accepts a key parameter. We start at the root. If the key we are searcing for is less than the node’s key, continue walking along the edge connecting to the leftChild. If the key is greater than the node’s key, continue walking along the edge connecting to the rightChild. When the key we are searching for is equal to that of the node, return the node.
Inserting a node is a little more involved, but not by much. We apply an algorithm similar to find but we check our base condition is when the leftChild or rightChild is null.
There are three cases we must consider when deleting a node:
node with zero children
node with single child
node with two children
Let’s consider the first case whend deleting a node with zero children.
Before After
15 15
/ \ / \7217 21
/ \ \510 10
Delete with zero children
We maintain a reference to the deleted node’s parent. We “delete” the node by updating the parent’s pointer (leftChild or rightChild) to null. The only edge case we consider is if the deleted node is the root. In thtat case, we just update root to null.
publicbooleandelete(intkey){Node<E>currentNode=root;Node<E>parent=currentNode;booleanisLeftChild=false;while(currentNode.key!=key){parent=currentNode;if(key<currentNode.key){isLeftChild=true;currentNode=currentNode.leftChild;}else{currentNode=currentNode.rightChild;}// node not foundif(currentNode==null){returnfalse;}}// Case 1: No childrenif(currentNode.leftChild==null&¤tNode.rightChild==null){if(currentNode==root){root=null;returntrue;}elseif(isLeftChild){parent.leftChild=null;returntrue;}else{parent.rightChild=null;returntrue;}}returnfalse;}
Delete node with single child
We just covered how to update the tree when a node has no children. Deleting a node, with a single child, is more involved, but just a little more. There’s four cases for the deleted node:
it’s the leftChild of its parent and has a leftChild
it’s the leftChild of its parent and has a rightChild
it’s the rightChild of its parent and has a leftChild
it’s the rightChild of its parent and has a rightChild
In the first two diagrams, we are deleting node 7. In the last two, we are deleting node 21.
Left child with single left child
15 15
/ \ / \7215 21
/
5
Left Child with a single right child
15 15
/ \ / \7219 21
\
9
Right child with single left child
15 15
/ \ / \7217 18
/
18
Right child with single right child
15 15
/ \ / \7217 25
\
25
When deleting a node, we replace the node with its inorder successor. The successor is the minimum node, within the deleted node’s right child subtree. Take a moment and think about that. Why the right subtree, and not the left?
Would the next largest number ever be to the left of the current node? No. By definition, all nodes to the left are less thanand all node to the right are greater than. Therefore, the smallest number (greater than the current node’s key) will be the minimum node, to the right.
Once we identify the successor, we update the successor’s parent leftChild pointer with the successor’s rightChild pointer (this may be null). We finalize the connections by updating the successor’s rightChild pointer to the delete node’s rightChild.
The binary search tree sounds like the dream, so why use an alternative data structure?
My manager shared a story of an interview candidate who inserted a sequence of sorted items into a binary search tree. Pause for a moment and visualize the data structure. What do you get?
A linked list!
This increases the height of the tree and we lose advantage of the O(logn) performance. Binary Search tree is suited best forrandomized keys, not sorted.
Example
publicclassEmployee{privateintid;privateStringfirstname;privateStringlastname;publicEmployee(intemployeeid,Stringfirstname,Stringlastname){this.id=employeeid;this.firstname=firstname;this.lastname=lastname;}@OverridepublicStringtoString(){// < 05: Joe Schmoe >StringmyString="< "+this.id+" "+this.firstname+" >";returnmyString;}publicstaticvoidmain(String[]args){Employeejboyd=newEmployee(15,"jess","boyd");Employeemstreiter=newEmployee(7,"myles","streiter");Employeemdavis=newEmployee(21,"matt","davis");Employeemmadsen=newEmployee(5,"martin","madsen");Employeemchung=newEmployee(19,"matt","chung");BinaryTree<Employee>employees=newBinaryTree<Employee>();employees.insert(jboyd.id,jboyd);employees.insert(mstreiter.id,mstreiter);employees.insert(mdavis.id,mdavis);employees.insert(mmadsen.id,mmadsen);// Is myles in the building?// returns trueSystem.out.println(employees.find(mstreiter.id));// Jess clocks outemployes.delete(jboyd.id);// Is Matt in the building?// returns falseSystem.out.println(employees.find(mchung.id));}}
Exercises
Write a function that verifies that a binary search tree is valid.
15
/ \7 21
/ \5 17
Acknowledgements
Thanks to Jess Boyd for correcting my initial draft, Matt Davis for pointing out the drawbacks of BSTs, and Martin Madsen for techniques to make the post more comprehensible.
In a previous post, I shared how I am teaching myself data structures and algorithms. In the breakroom work, a colleague overheard a group forming to study together – the weekend bravehearts. I was lucky enough to catch the group at the head end. We meet Friday after work, and Saturday mornings. If you live in the greater Seattle area and wanted to join, e-mail me and I’ll bring you along.
This is a quote pulled from interview, from the book “Coders at work”, with Ken Thompson
[3]
(1, 2) MIT’s lecturer presents a scheduling problem and compare the advantages and disadvatages of previously discussed datastructures (e.g “linked lists”, “arrays”, “heaps”). I recommend watching it:https://www.youtube.com/watch?v=9Jry5-82I68
Look through my history, and you’ll find how infrequently I post on Facebook, however, I strongly encourage you to watch this short video clip, especially if you are approaching 30, like me, and plan on having children.
This video poignantly touches on the issues, revolving around teenage homosexuality and bullying, that our younger generation is battling. I tend to forget, and trivialize, how difficult the teenager years were. I forget how insecure I was. I forget, partially, because the problems I now face have changed, naturally, overtime, but having younger brothers and sisters in this age range serve as an important reminder of the role we play, as adults, to the younger, impressionable, generation.
I fought back tears watching this video and as a byproduct, I’m now questioning not only my beliefs, but the words I unconsciously elect to say day to day. For example, when referring to someone’s thoughts or actions during their teenage years: “It’s just a phase.” This seemingly innoculous selection of words bear no harm, right? But, what if the very thing they’re going through, whatever it may be, is actually NOT a phase?
Feelings of shame.
Through my own struggles, I’ve felt shameful I’ve learned the subtle difference between guilt, which is feeling bad about the things you do, and shame, which is feeling bad about who you are. Shame, if left unaddressed, can lead down a dark, confusing, path.
“It is no measure of health to be well adjusted to a profoundly sick society.” – Jiddu Krishnamurti
I studied Spanish in high school for four years and 10 years later, I’m embarrassed that I can’t form a comprehensible or grammatically correct sentence.
I traveled throughout Europe last Christmas and was impressed by the number of bilinguals. Most people fluently spoke a combination of English, French and German. My second language, Vietnamese, however, is barely conversational.
My Vietnamese stagnated 15 years ago. In elementary school, I was immersed in an after school program where I learned how to read, write, and speak Vietnamese. The majority of my friends spoke the language too, which was conducive to learning the language. But now, I rarely practice and have forgotten the majority of it.
I was motivated to improve my Vietnamese after traveling to Vietnam last year. I was disheartened by the inability to communicate with my 9 year old nephew; my weak vocabulary limited the dialoge. My cousins taught me new words but by the end of the trip, I couldn’t remember any of them.
Learning French
In order to improve my Vietnamese, I started learning French. I figured that if I could learn a lanuage from stratch, I could use the same principles and apply it to learning Vietnamese.
I searched online for the best methods to learn a new language. I purposely avoided any articles/books that promised short term success (e.g “Perfect French in 30 days”). After reading reviews on Amazon, I ordered Fluent Forever.
With the books help, I built my curriculum. It cosists of:
Reflecting back at the last 3 months, I’m proud of my progress. I’ve ritualized learning French into a daily habit. I failed in the past due to inconsistency – it was never a habit.
La salle à manger is petite. Il y a quatre chaises et une table dans la salle à manger. Sur la table est une nappe. Elle est vert. Il y a aussi des assiettes, des couteux, des cuillers et des fourchettes.
Est-ce qu’il y a une tasse sur la table? Oui, il y ya trois tasses et un verre. Les tasses sont petites.
Qu’est-ce qu’il y a dans les tasses? Il y ya du café dans les tasses. Qu’est-ce qu’il y a sont les verres? Il y ya du vin. Le café est noir et le lait est blanc. Il y ya aussi de la viande sur une plat, et il y ya légumes sur une plat.
Qu’est qu’il y ya des fleures? Oui, il y ya des fleures dans un vase. Comment est le vasse? Il est joli; il est vert et brun. De quelle couleur sont les fleures? Il y ya rouge et blanc.
Change in mindset
“You will never change your life until you change something you do daily. The secret of your success is found in your daily routine.”
—John Maxwell
I’ve reframed my expectations. Instead of expecting fluency – both Vietnamese and French – in a short period, I’m building up my vocabulary and grammar; I’m immersing myself with people, books, and videos.
I look forward to learning more about the people, new and existing, especially my nephew.
I’ve been very sick this past week … coughing phelgm, swallowing pain, and battling headaches. Two nights in a row, an uncontrollable cough prevented me from sleeping.
This morning, however, I awoke without a sore throat. It goes to show you how much I take you for granted when I’m healthy.
My elation at regaining my health won’t be short lived. This I promise you.
Ongoing health problems
Despite converting to a plant based diet in 2014, we’re struggling with intermittent stomach pains. Sometimes, the excruciating pain paralyzes me into the fetal position for more than two hours. It’s the same sensation that sent us to the emergency room in 2005.
Doctors can’t isolate the problem. Nutritionists suggest conflicting diets. It’s up to you and I to experiment and create a sustainable diet. I’ll continue to jot down foods that cause problems:
hummus (gas)
cold drinks (bladder incontinence)
honey / maple syrup (bladder incontinence)
raw lettuce (severe stomach pain)
I’m fixing more than our diet. I reintroduced mindful eating. This means deliberately counting 60 chews before swallowing. This should help with digestion.
All of this is going to take time. So thank you for being patient. Thank you for keeping me going. Thank you body.
