Ryan's Repository of Random Reflections

In my last blog post , I introduced interpolation search, a searching algorithm that can beat binary search asymptotically. To introduce the concept of interpolation search, I made a simplifying assumption that the underlying data came from a uniform distribution. It is still possible to use interpolation search on non-uniform distributions, as long as you have the CDF for that distribution. Background Info A cumulative distribution function is a function that tells you the probability that a random item from the distribution is less than or equal to a specified value. $$ F(k) = P(X \leq k) $$ Thus, $F(k)$ can take on values in the range $[0,1]$ and it is non-descending. For a discrete uniform distribution of integers in the range $[1,10]$, the CDF looks like: And for a continuous normal distribution, the CDF looks like: How to get the CDF There are a number of options to get a handle on the CDF. You can find information online about your distribution, do a one-pass...

If you have taken an introductory computer science course, you've probably seen the binary search algorithm - an algorithm to efficiently find the index of an item in a sorted array, if it exists. You might not have heard of interpolation search, however. Interpolation search is an alternative to binary search that utilizes information about the underlying distribution of data to be searched. By using this additional information, interpolation search can be as fast as $O(log(log(n)))$, where $n$ is the size of the array. In this post I am going to talk about two implementations of interpolation search. First, I will discuss the algorithm as described on Wikepedia, then I will describe my own version of the algorithm that has a better worst case time complexity than the first and performs better in practice than the traditional binary search and interpolation search algorithms. The Basic Idea Interpolation search models how humans search a dictionary better than a binary search, ...

Processors speeds are no longer growing at the rate we've grown accustomed to. Moore's law states that computers double in speed every 18 months. Moore's law is still alive and well, but we just need to find alternate ways to speed up computers. That's where multi-core programming comes into play. The idea behind it is that 2 heads are better than one and in the right situation 2 processors can work on the same problem to solve it twice as fast. Parallel programming is becoming increasingly important these days and there are many different flavors of it including distributed computing, shared memory computing, and GPU computing. Today I am going to focus on shared memory computing, or using multi-core computers rather than many single core computers. This blog post is intended to serve as a beginners guide to parallel programming with Java. It is recommended that the reader have some java experience and is familiar with some of the features of Java 8 (namely lambda expr...

The 2 biggest programming paradigms are functional and imperative, but they share very little in common. In this blog post, I will discuss the differences between the two as I understand them and talk about my experience with each. Functional programming languages are very mathematical - functions can be defined piece-wise, recursively, or in terms of other functions. They can also easily be combined forming composition of functions. Imperative languages use a slightly different approach - rather than telling the computer what something is, you must specify how to get it. The first functional programming language I learned was Racket, which is a similar to another functional programming language: Common Lisp. I always thought of Racket as a neat language with some nice abstractions but I always felt like it lacked some core functionality. Recently, however, my friend introduced me to Haskell, and I've been trying to pick it up.  Haskell is much more powerful than Racket, and it...