binary search, pearls, selection, double binary search

Pearl No.4 - Kth Smallest in the Union of 2 Sorted Collections

— Published 19 October 2017 —

Here is the Pearl No.4: Let A and B be two disjoint ordered collections with distinct elements inside. Their combined size is g…

visualisation, random

Visualise Randomness

— Published 22 November 2015 —

It has been almost half year since my last blog post on OCaml. Well, actually I haven't even touched OCaml for that long time. My…

Permutations

— Published 05 May 2015 —

In this post, we will talk about producing permuations using OCaml. Generating permutations was actually one of my first self-hom…

Pearl No.3 - Saddleback Search

— Published 31 March 2015 —

Happy Easter Our easter egg happens to be Pearl 3. A function $ f $ can have the following properties: $ f $ takes two …

heap, binomial heap

Binomial Heap

— Published 17 March 2015 —

As we described in the previous post, leftist tree is a binary tree based functional heap. It manipulates the tree structure so t…

heap, leftist tree

Heap - Leftist Tree

— Published 12 March 2015 —

Heap is one of most important data structure, where the minimum of all elements can always be easily and efficiently retrieved. …

merge, pearls, algorithm, max, divide and conquer, surpassers

Pearl No.2 - The Max Number of Surpassers

— Published 20 February 2015 —

In a list of unsorted numbers (not necessarily distinct), such as The surpassers of an element are all elements whose indices…

pearls, algorithm, min, selection, quickselect, min missing natural number

Pearl No.1 - The Min Missing Natural Number

— Published 02 February 2015 —

Prof. Richard Simpson Bird is a Supernumerary Fellow of Computation at Lincoln College, Oxford, England, and former director of t…

recursion, memoize, untying the recursive knot, memoize recursive

Recursive Memoize & Untying the Recursive Knot

— Published 25 January 2015 —

When I wrote the section of When we need later substitution in Mutable, I struggled. I found out that I didn't fully understand …

mutable, shuffle, imperative programming, binary search, memoize

Mutable

— Published 20 January 2015 —

While OCaml is a functional programming language and emphasises pure functional style, it allows mutable (variables and values) a…

functional programming style, quicksort , execution model , algorithm

Immutable

— Published 02 January 2015 —

In pure functional programming, everything is immutable. Strings, lists, values of customised types etc cannot be changed once be…

binary search tree, data structure, ninja, recursion

Become a BST Ninja - Genin Level

— Published 19 December 2014 —

Binary Search Tree (BST) is one of the most classic data structures. The definition for its structure is shown as below: It consi…

recursion, merge, mergesort, algorithm

Recursion Reloaded

— Published 04 December 2014 —

One essential of computer programming is repeating some operations. This repetition has two forms: for / while loop and recursion…

binary search tree, data structure

Height, Depth and Level of a Tree

— Published 26 November 2014 —

This is a post on the three important properties of trees: height, depth and level, together with edge and path. I bet that most …

The Magic of Thunk - Async

— Published 13 November 2014 —

Currently in post-production. Sorry, I still haven't finished this post. As this will be the last post in the magic of thunk ser…

The Magic of Thunk - Lazy

— Published 13 November 2014 —

The dark side of thunk As discussed previously, thunk is used to encapsulate computations for later uses. Although we may not eva…

thunk, stream

The Magic of Thunk - Stream_list

— Published 09 November 2014 —

list The built-in list is a fundamental type in OCaml. We can have a list of numbers such as [1;2;3;4] or functions e.g. [fun x -…

lazy, thunk, stream_list, async

The Magic of Thunk

— Published 06 November 2014 —

A thunk is simply a function with the unit parameter. For example: let f() = 1 + 2 * 3;; Features It is indeed a function and s…