David Dantowitz's Resume
      Developing software for a while

David Dantowitz on

May 2018: A Fast Shuffle for Binary Search
      An O(n) algorithm is presented to shuffle a sorted array to breadth-first binary tree order. The shuffle preserves the sort property (and the use of binary search), provides implied bidirectional parent-child links, and enables a node in the tree to determine if it is a left or right child of its parent from its array index.

Code for an initial reference method is presented with a set of optimizations. The last set of optimizations achieves a speed up of 5 to 32, based on the array size.

Finally, results are presented using the shuffled array vs. the sorted array for binary search, with improved in performance from 1.06 to 2.11 times depending on the array size and CPU/Cache interactions. Side by side threads running Binary Search vs. Shuffled Search: Video and Source Code.
Fast Shuffle for Binary Search

July 2011: A Fast String Match Algorithm
      Developed a fuzzy string match algorithm with the same results as Damerau-Levenshtein, but faster. The graph below shows the results of searching the complete works of William Shakespeare (1, 5, 10, 50, and 100 copies) with 5 randomly selected words (from the work) of lengths 7 to 10 characters with a limit distance of 2.
Speed Up Fast Match vs Damerau-Levenshtein
         Designed and developed a self-contained full stack environment, front to back, from scratch in C. The project included a multi-threaded, MVCC, NoSQL Database with location-based components. Licensed by Apple 2001-2011 (used on their website and internally) and by other clients to create simple and complex REST apps. IP ownership maintained.

The Apache-Apple Event Bridge (
      Enables Apache to call AppleScripts and apps via the CGI Request Apple Event (2009)

Macworld, 2002: ZipBurst Press Release
      ZipBurst performs multi-threaded data and location-based searches of your flat or relational database files
      Consulting for Apple Products since 1989.
      One to One consumer consulting.

A Multi-threaded Simulation Engine for a Shared Memory Parallel Super Computer
         Developed an environment similar to MPI from scratch: a multi-threaded, multi-cpu, NUMA Aware, simulation engine for use on a Shared Memory Parallel Super Computer using event driven simulation and minimal synchronization barriers.

A Pinball game for MTV (1999)
      Wrote a pinball physics engine from scratch
      click to see full size


Shockwave Site Of The Week: AT&T's 1996 Olympic Games Website
      Developed for Modem Media

High Performance Code for CRCs (1986)
              A developer posted incorrect code for computing CRCs, so I correct their bug, cited reference material, included a mini-tutorial, and wrote a routine that ran 8 times faster. Uses inline assembler code.

Over the years this work was used by professors, developers, and researchers. One such credit was "The Virus Intervention & Control Experiment" by Molini & Ruhl, (13th National Computer Security Conference, 1990) dealing with reducing the impact of PC Viruses at NASA's Johnson Space Center. Great to know my contribution had plenty of uses and amusing to discover segments of my writing quoted from the source code and credited.

Assembler Language: Bresenham's algorithm for line drawing (1986)
      High Performance, Optimized and Commented