Home » Tag Archives: Algorithms

# Tag Archives: Algorithms

## Resolve coreference using Stanford CoreNLP

Coreference resolution is the task of finding all expressions that refer to the same entity in a text. Stanford CoreNLP coreference resolution system is the state-of-the-art system to resolve coreference in the text. To use the system, we usually create a pipeline, which requires tokenization, sentence splitting, part-of-speech tagging, lemmarization, named entity recoginition, and parsing. However sometimes, we use others ...

## The Knapsack problem

I found the Knapsack problem tricky and interesting at the same time. I am sure if you are visiting this page, you already know the problem statement but just for the sake of completion : Problem: Given a Knapsack of a maximum capacity of W and N items each with its own value and weight, throw in items inside the ...

## Fibonacci and Lucas Sequences

This posts touches on three of my favorite topics – math, transferring knowledge through experience (tutorial unit tests) and the importance of research. Most developers are aware of the Fibonacci sequence, mostly through job interviews. To briefly recap the series is defined a: F(n) = F(n-1) + F(n-2), n > 2 F(1) = F(2) = 1   There’s a variant ...

## Java implementation of Optimal String Alignment

For a while, I’ve used the Apache Commons lang StringUtils implementation of Levenshtein distance.  It implements a few well known tricks to use less memory by only hanging on to two arrays instead of allocating a huge n x m table for the memoisation table.  It also only checks a “stripe” of width 2 * k +1 where k is the ...

## Creating a price model using k-Nearest Neighbours + Genetic Algorithm

Chapter 8 of Programming Collective Intelligence (PCI) explains the usage and implementation of the k-Nearest Neighbours algorithm. (k-NN). Simply put: k-NN is a classification algorithm that uses (k) for the number of neighbours to determine what class an item will belong to.  To determine the neighbours to be used the algorithm uses a distance / similarity score function, in this example (Euclidian Distance). ...

## Quicksorting – 3-way and Dual Pivot

It’s no news that Quicksort is considered one of the most important algorithms of the century and that it is the defacto system sort for many languages, including the Arrays.sort in Java. So, what’s new about quicksort? Well, nothing except that I figured just now (after 2 damn years of release of Java 7) that the Quicksort implementation of the ...

## Java: Mergesort using Fork/Join Framework

The objective of this entry is to show a simple example of a Fork/Join RecursiveAction, not to delve too much into the possible optimizations to merge sort or the relative advantages of using Fork/Join Pool over the existing Java 6 based implementations like ExecutorService. The following is a typical implementation of a Top Down Merge sort algorithm using Java: import ...

## All you need to know about QuickSort

It would be true to say that Quicksort is one of the most popular sorting algorithms. You can find it implemented on the most of the languages and it is present in almost any core library. In Java and Go Quicksort is default sorting algorithm for some data types and it is used in in C++ STL ( Introsoft which ...

## The simple Big-O Notation Post

Our JCG partner Brian Du Preez has posted an explanatory article on his blog, Zen in the art of IT, concerning the Big-O notation. The Big-O notation is used for describing algorithm performance, scalability, execution and complexity factors. Understanding what the Big-O notation stands for is essential for every developer who wants to write performant, robust and scalable code. Lets see what he has to say … ...

Want to take your Java skills to the next level?