Chasing state of the art
Exploring best practices in problem solving
Parallel partition phase for quick sort
A while ago I was wrapping my head around parallel merge sort. Since it requires additional O(n)...
Author: Dzmitry Huba Date: 03/04/2012
Load-balancing partitioner with work stealing, part two
In part one work stealing range was introduced that allows stealing of work items in contiguous...
Author: Dzmitry Huba Date: 08/10/2011
Load-balancing partitioner with work stealing, part one
Data parallelism is a computing parallelization technique where data can be separated into...
Author: Dzmitry Huba Date: 08/08/2011
Infernal dinner synchronization problem
Imagine group of hungry people with spoons sitting around pot of stew. Spoon’s handle long...
Author: Dzmitry Huba Date: 07/19/2011
Shared rooms synchronization problem
Recently I came across another interesting synchronization problem. Assume there are n rooms....
Author: Dzmitry Huba Date: 06/29/2011
Single Responsibility Principle – discovering violations
Single Responsibility Principle states: A class should have only one reason to change....
Author: Dzmitry Huba Date: 06/15/2011
Inject or locate dependencies?
Inversion of Control pattern allows to decouple components (consumers) from their dependencies and...
Author: Dzmitry Huba Date: 06/13/2011
Sleeping barber synchronization problem
Sleeping barber problem is a classic synchronization problem proposed by Dijkstra that goes as...
Author: Dzmitry Huba Date: 06/12/2011
Concurrent Object Pool
Object pool is a set of initialized objects that are kept ready to use, rather than allocated and...
Author: Dzmitry Huba Date: 05/01/2011
Concurrent set based on sorted singly linked list
Set is an abstract data structure that can store certain values, without any particular order, and...
Author: Dzmitry Huba Date: 04/06/2011
Merge binary search trees in place
Binary search tree is a fundamental data structure that is used for searching and sorting. It also...
Author: Dzmitry Huba Date: 03/27/2011
Merge sequences in parallel
In practice you may find yourself in a situation when you have several sequences of data that you...
Author: Dzmitry Huba Date: 02/25/2011
Longest consecutive elements sequence
A tiny detail that can be uncovered by looking at a problem on a different angle usually is the key...
Author: Dzmitry Huba Date: 02/12/2011
Parallel string matching
String matching is about searching for occurrence (first or all occurrences – it makes...
Author: Dzmitry Huba Date: 01/05/2011
Parallel graph search
Graph is a concept used to describe relationships between things where vertices (or nodes) represent...
Author: Dzmitry Huba Date: 12/26/2010
Joining Microsoft
Find a job you like and you add five days to every week. - H. Jackson Brown, Jr. I decided to join...
Author: Dzmitry Huba Date: 11/11/2010
Parallel merge sort
Divide and conquer algorithm solves the problem by: dividing problem into two or more smaller...
Author: Dzmitry Huba Date: 10/17/2010
Traverse binary tree in level order by spiral
Another puzzle is at stake, folks. This time it is binary tree related (not necessarily binary...
Author: Dzmitry Huba Date: 09/19/2010
External merge sort
If data to be sorted doesn’t fit into main memory external sorting is applicable. External...
Author: Dzmitry Huba Date: 08/24/2010
Print numbers by spiral
Recently I came across simple yet interesting coding problem. So here is the deal. You are given...
Author: Dzmitry Huba Date: 08/17/2010
Suffix array
Find all occurrences of a pattern (of length m) in a text (of length n) is quite commonly...
Author: Dzmitry Huba Date: 04/04/2010
Selecting k smallest or largest elements
There are cases when you need to select a number of best (according to some definition) elements out...
Author: Dzmitry Huba Date: 03/17/2010
K-way merge
The classic merge (the one used in Merge Sort) takes as input some sorted lists and at each step...
Author: Dzmitry Huba Date: 03/04/2010
Right-hand side Enumerable.Zip
With Reactive Extensions for .NET (Rx) and .NET Framework 4 a new LINQ operator was introduced...
Author: Dzmitry Huba Date: 02/22/2010
Binary heap based priority queue
Design of container that supports items ordering raises lots of interesting design questions to...
Author: Dzmitry Huba Date: 02/08/2010
Queue based on a single stack
Looking at things from different perspectives allows to understand them better. On the other hand...
Author: Dzmitry Huba Date: 01/17/2010
Disposing sequence of resources with Reactive Extensions
Recall my previous post on Disposing sequence of resources where we were solving imperatively the...
Author: Dzmitry Huba Date: 12/29/2009
Chaining responsibilities
The idea behind Chain of Responsibility pattern is quite simple and powerful: Avoid coupling the...
Author: Dzmitry Huba Date: 12/22/2009
Making callbacks more explicit
Recall my previous post Events and Callbacks vs. Explicit Calls that outlined pros and cons of both...
Author: Dzmitry Huba Date: 12/21/2009
Disposing sequence of resources
C# “using” statement has several advantages over its expanded equivalent: Shortcut is...
Author: Dzmitry Huba Date: 11/04/2009