Blogs

Why ignore 50% of what we know about the data1 Everyone learnt binary search in Algo 101. It is the fastest way (among comparison based searches) to find an element in a sorted array. All you need to carry out the algorithms is the comparison between the target element and the element at the current position. It is widely applicable because it assumes so little from the data. But for many real life problems, we do often know something apart from merely the comparison between the two numbers....

Ladder of abstraction Well the title is obviously a tweak of the “ladder of abstraction”. For those who does not know, “ladder of abstraction” refers to the classic essay by Bret Victor. I am kind of stealing this terminilogy for the reader to visualize climbing up and down on the ladder of abstraction to make it easier to explain the nature of different jobs. The main question this blog post deals with is:...

Relaxation as a result of mastery, instead of a prerequisites In many sports/ crafts that I have experienced, relaxation is considered by many the prerequisites of mastery: In playing piano, your fingers, wrists, arms and shoulders have to be relax or you will find it extremely hard to press the right keys fluently; In online games that require fast reactions, rookies hands are stiff and they press buttons with unnecessary strength and range of motion, which stops them from pressing right buttons at the right time smoothly; In jiujitsu, being reasonably relax helps you to perform efficient moves, saving your energy and gives you more choices in different situations in which you have to adapt and react quickly....

Counting binary trees I was thinking about of the problem of balancing a binary tree, and my mind stumbled across to the question “How many different binary trees with labelled nodes can you make without changing the traversal order?”. After figuring out the answer myself I realized that the numbers of such binary trees are just Catalan numebrs (I was not really into combinatorics - now I am). For example, the following has traversal order 1->2->3->4->5->6->7...

Defining the machine by describing it In Sipser’s Introduction to the theory of computation, a alternative way of defining a Turing machine (other than defining the formal 7-tuple, which is a PITA) - by its “description”. Example (from the proof of $A_{TM}$ is deciable): M = “On input <B, w>, where B is a DFA and w is a string: 1. Simulate B on input w. 2. If the simulation ends in an accept state, accept ....