An all-substrings common subsequence algorithm

Given two strings A and B of lengths n(a) and n(b), n(a) <= n(b), respectively, the all-substrings longest common subsequence (ALCS) problem obtains, for every substring B` of B, the length of the longest string that is a subsequence of both A and B. The ALCS problem has many applications, such as finding approximate tandem repeats in strings, solving the circular alignment of two strings and finding the alignment of one string with several others that have a common substring. We present an algorithm to prepare the basic data structure for ALCS queries that takes O(n(a)n(b)) time and O(n(a) + n(b)) space. After this preparation, it is possible to build that allows any LCS length to be retrieved in constant time. Some trade-offs between the space required and a matrix of size O(n(b)(2)) the querying time are discussed. To our knowledge, this is the first algorithm in the literature for the ALCS problem. (C) 2007 Elsevier B.V. All rights reserved.

Repetition-free longest common subsequence

We study the following problem. Given two sequences x and y over a finite alphabet, find a repetition-free longest common subsequence of x and y. We show several algorithmic results, a computational complexity result, and we describe a preliminary experimental study based on the proposed algorithms. We also show that this problem is APX-hard. (C) 2009 Elsevier B.V. All rights reserved.

Analysis and performance of a UPC implementation of a parallel longest common subsequence algorithm

An important problem in computational biology is finding the longest common subsequence (LCS) of two nucleotide sequences. This paper examines the correctness and performance of a recently proposed parallel LCS algorithm that uses successor tables and pruning rules to construct a list of sets from which an LCS can be easily reconstructed. Counterexamples are given for two pruning rules that were given with the original algorithm. Because of these errors, performance measurements originally reported cannot be validated. The work presented here shows that speedup can be reliably achieved by an implementation in Unified Parallel C that runs on an Infiniband cluster. This performance is partly facilitated by exploiting the software cache of the MuPC runtime system. In addition, this implementation achieved speedup without bulk memory copy operations and the associated programming complexity of message passing.

On the importance of an early correct education of children : embracing the mutual obligations and duties of parent and child ; and also the qualifications and discipline of teachers, with their emolument ; and a plan suggested whereby all our common schools can advantageously be made free ; the whole interspersed with several amusing, chaste anecdotes growing out of the domestic and scolastic circle ; to which is subjoined by way of appendix, the Declaration of Independence ... ; the Constitution of the United States ; with that of the state of New York as lately adopted /

Bound in green cloth; stamped in gold and blind.

An Introduction to the art of fortification, containing draughts of all the common works used in military architecture, and of the machines and utensils necessary either in attacks or defences : also a military dictionary, wherein the said works and machines are not only more fully described, but all other technical terms and phrases made use of in the science of war are distictly [sic] explained.

A separate issue of the title appended to The theatre of the present war in the Netherlands and upon the Rhine (London : J. Brindley, 1745).