Combinatorial Algorithms in Scala

Combinatorics is a branch of mathematics that mostly focuses on problems of counting the structures of given size and kind. The most famous and well-known examples of such problems might be often asked as job interview questions. This blog post presents four generational problems (combinations, subsets, permutations and variations) along with their purely functional implementations in Scala.

Dual-Pivot Binary Search

In 2009, Vladimir Yaroslavski introduced a Dual-Pivot QuickSort algorithm, which is currently the default sorting algorithm for primitive types in Java 8. The idea behind this algorithm is both simple and awesome. Instead of using single pivot element, it uses two pivots that divide an input array into three intervals (against two intervals in original QuickSort). This allowed to decrease the height of recursion tree as well as reduce the number of comparisons. The post describes a similar dual-pivot approach but for a BinarySearch algorithm. Thus, our modified binary search algorithm has prefix Dual-Pivot.

Finagle Your Fibonacci Calculation

Finagle is an RPC library for JVM that allows you to develop service-based applications in a protocol-agnostic way. Formally, the Finagle library provides both asynchronous runtime via futures and protocol-independence via codecs. In this post I will try to build a Finagle-powered distributed Fibonacci Numbers calculator that scales up to thousands of nodes.

In The Beginning

This is my first post on this blog. Needless to say, I'm really excited about this. This is my first attempt in writing blog posts in English. I was previously posting in Russian at LJ and Tumbler, but it wasn't about technical things. Here, I will try to post only about CS. I have huge plans on posting about Scala and it's application for research of purely functional data structures. I should probably post about algorithms and data structures that I've already implemented in Scalacaster. There are loads of awesome pieces of Scala code that I want to tell about. One of my favorites - QuickSelect in a purely functional setting.