COMPUTER ENGINEERING DIARIES

We know that the fastest sorting algorithms that is based on comparing the elements (compareTo method) have a complexity of O(n logn) But, is there a faster way for certain conditions? Yes. Let's say we have an array of 11 letters with values from a to f {e, e, f, a, b, a, a, c, d, a, a} To sort these letters, we'll create an array that stores the frequencies of the letters. The index will be the letter itself. For example, for letter a, the index will be 0. For letter c, the index will be 2 and so on.. Frequency array for {a, b, c, d, e, f} is {5, 1, 1, 1, 2, 1} The second step is calculating the cumulative counts which is {5, 6, 7, 8, 10, 11} We need to use this cumulative counts to learn the position of each letter. We know that the position of letter a will be zero. So the array will start with 0 as the first position for a: indexes:            {a, b, c, d, e, f , - } cumulative array:   {0, 5, 6, 7, 8, 10, 11} This cumulati...

Lets assume we have a set of points and we want to find all of the points that are contained in a query rectangle. And we also want to find the closest point to a query point. These are called "range search" and "nearest-neighbour search". I'll show the usage of a 2d-tree for this problem. Kd-trees have many applications including computer animation and image retrieval. Lets start with a brute-force approach and look at all the points in the input without any efficient data structure for the specific problem: public class PointSET {     private TreeSet set = new TreeSet<>();     public void insert(Point2D point) {         if (point == null) {             throw new IllegalArgumentException();         }         set.add(point);     }     public boolean contains(Point2D point) {          if (point == ...