This paper considers GraphChi, a system for processing large graphs on single modern PCs, as a case study. GraphChi uses a "parallel sliding window" method. This requires that vertices and edges be assigned into similarly sized shards whose contents are sorted to allow for sliding, maintaining locality of access to nodes. GraphChi uses an expensive onetime pre-processing step. For example, the twitter-2010 graph with 42M nodes and 1.5B edges takes ten minutes to pre-process and just under three minutes for a single-pass of the PageRank algorithm.

An extremal self-dual doubly-even binary (n,k,d) code has a minimum weight d=4/spl lfloor/n/24/spl rfloor/+4. Of such codes with length divisible by 24, the Golay code is the only (24,12,8) code, the extended quadratic residue code is the only known (48,24,12) code, and there is no known (72,36,16) code. One may partition the search for a (48,24,12) self-dual doubly-even code into three cases. A previous search assuming one of the cases found only the extended quadratic residue code. We examine the remaining two cases. Separate searches assuming each of the remaining cases found no codes and thus the extended quadratic residue code is the only doubly-even self-dual (48,24,12) code.

The BLASTP program is a search tool for databases of protein sequences that is widely used by biologists as a first step in investigating new genome sequences. BLASTP finds high-scoring local alignments (q/sub i/q/sub i+1/...q/sub i+k//spl par/s/sub j/s/sub j+1/...s/sub j+k/) without gaps between a query sequence q and sequences s in the database. The score of an alignment is the sum of the scores of individual alignments q/sub i+t//spl par/s/sub j+t/ between amino acids that make up the protein. These individual scores come from a scoring matrix modeling the rate of evolutionary mutation. Here we provide a detailed description of the original program and three separate optimisations to it. BLASTP consists of three steps, that we call neighbourhood construction, hit detection, and hit extension. The three optimisations target hit extension since it accounts for 93% of the execution time. The first optimisation alters the data representation of the query sequence and the related code for indexing the scoring matrix. The second optimisation performs extensions in step-sizes of two rather than one. The third optimisation forstalls the calling of the hit extension step in cases that are unlikely to lead to a high-scoring alignment. Individually the three optimisations show speed ups of 15%, 48%, and 63% respectively.

Exact and approximate algorithms for detecting lines in a two-dimensional image space are discussed. For the case of uniformly distributed noise within an image space, transform methods and different notions of probability measures governing the parameters of the transforms are described. It is shown that different quantization schemes of the transformed space are desirable for different probabilistic assumptions. The quantization schemes are evaluated and compared. For one of the procedures that uses a generalized Duda-Hart procedure and a mixed quantization scheme, the time complexity to find all m-flats in n-space is shown to be bounded by O(ptm(n-m)2), where p is the number of points and t is a user parameter. For this procedure more true flats in a given orientation have been found and the number of spurious flats is small.