Printer-friendly page - just print

Research, Software, and Papers

Andrew Shapira

PhD, MS, Computer Engineering, Rensselaer Polytechnic Institute
BS, Computer Science, College of Engineering, University of Illinois

Some of my research interests are random number generation and testing, maximum matching, vertex coloring, network topologies for supercomputers, the nonattacking queens problem, an NP-complete problem arising in optical character recognition, graph isomorphism, and some problems in computer graphics.

Below are some papers and software of mine. Some are in HTML; some are compressed with the gzip utility. Unless otherwise noted, I am the sole author.

The Option Pattern

February, 2007, online at The Code Project,

This paper is the first in a series of five papers about the option pattern, a ubiquitous coding pattern. Learn what the option pattern is, how to avoid null and other evils, and why.

The paper may be viewed here at The Code Project. The C# source code is available here.


FileDigest is a C# class for reading and writing entire files, and determining whether a file’s write successfully completed in the face of possible write interruptions such as program or system crashes.

FileDigest 1.0 (November 2003)
View source code
Download source code (save as filedigester.cs)

Cycle Parity Random Number Generators, and a General Random Number Library

PhD Thesis, ECSE Department, Rensselaer Polytechnic Institute, November 1997 (105 pages).

An Exact Performance Bound for an O(m+n) Time Greedy Matching Procedure

In The Electronic Journal of Combinatorics 4, R25 (1997).

Available here at the EJC web site.


Randpack is an unreleased software library for generating pseudo-random sequences, and for testing for random-like properties. It contains all of Knuth’s tests for random number generation, and some other tests, including the spectral test. The tests operate in a unified framework using Chi-Square and Kolmogorov-Smirnov tests.

The Discrete Runs Test and the Discrete Maximum of t Test

Technical Report No. CS 96-15, CS Department, Rensselaer Polytechnic Institute, June 1996 (16 pages).

Abstract / Postscript / compressed Postscript

N-Tuple Features for OCR revisited

By D. Jung, M. Krishnamoorthy, G. Nagy, A. Shapira. In IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 18, Number 7, p734-745, July 1996.

The abstract is available here at IEEE PAMI’s site. The full version is available here at PAMI’s site for a fee.


Ntuplib is software for finding n-tuple features for optical character recognition.

Introduction / C source code and manual (tar file) / compressed tar file

Experiments on the Generation of Distinguishing N-Tuples for Selected Character Dichotomies

Technical Report No. ECSE-OCR-18DEC95, ECSE Department, Rensselaer Polytechnic Institute, December 1995 (44 pages).

Postscript / compressed Postscript

Visibility and Terrain Labeling

Master’s Thesis, ECSE Department, Rensselaer Polytechnic Institute, 1990 (168 pages).

Table of contents, abstract, and introduction

Fast Line-Edge Intersections on a Uniform Grid

In Graphics Gems, Andew Glassner Ed., Academic Press, p29-36, 1990.

Summary / Source code for Graphics Gems book series