Algorithms

185 KiB

Open AccessArticle

by Shmuel T. Klein and Dana Shapira

Algorithms 2011, 4(1), 61-74; https://0-doi-org.brum.beds.ac.uk/10.3390/a4010061 - 22 Mar 2011

Cited by 14 | Viewed by 6472

The problem of compressed pattern matching, which has recently been treated in many papers dealing with free text, is extended to structured files, specifically to dictionaries, which appear in any full-text retrieval system. The prefix-omission method is combined with Huffman coding and a [...] Read more.

The problem of compressed pattern matching, which has recently been treated in many papers dealing with free text, is extended to structured files, specifically to dictionaries, which appear in any full-text retrieval system. The prefix-omission method is combined with Huffman coding and a new variant based on Fibonacci codes is presented. Experimental results suggest that the new methods are often preferable to earlier ones, in particular for small files which are typical for dictionaries, since these are usually kept in small chunks. Full article

440 KiB

Open AccessArticle

Edit Distance with Block Deletions

by Dana Shapira and James A. Storer

Algorithms 2011, 4(1), 40-60; https://0-doi-org.brum.beds.ac.uk/10.3390/a4010040 - 07 Mar 2011

Cited by 8 | Viewed by 7317

Abstract

Several variants of the edit distance problem with block deletions are considered. Polynomial time optimal algorithms are presented for the edit distance with block deletions allowing character insertions and character moves, but without block moves. We show that the edit distance with block [...] Read more.

Several variants of the edit distance problem with block deletions are considered. Polynomial time optimal algorithms are presented for the edit distance with block deletions allowing character insertions and character moves, but without block moves. We show that the edit distance with block moves and block deletions is NP-complete (Nondeterministic Polynomial time problems in which any given solution to such problem can be verified in polynomial time, and any NP problem can be converted into it in polynomial time), and that it can be reduced to the problem of non-recursive block moves and block deletions within a constant factor. Full article

► Show Figures

123 KiB

Open AccessArticle

Defense of the Least Squares Solution to Peelle’s Pertinent Puzzle

by Tom Burr, Toshihiko Kawano, Patrick Talou, Feng Pan and Nicolas Hengartner

Algorithms 2011, 4(1), 28-39; https://0-doi-org.brum.beds.ac.uk/10.3390/a4010028 - 15 Feb 2011

Cited by 8 | Viewed by 7222

Abstract

Generalized least squares (GLS) for model parameter estimation has a long and successful history dating to its development by Gauss in 1795. Alternatives can outperform GLS in some settings, and alternatives to GLS are sometimes sought when GLS exhibits curious behavior, such as [...] Read more.

Generalized least squares (GLS) for model parameter estimation has a long and successful history dating to its development by Gauss in 1795. Alternatives can outperform GLS in some settings, and alternatives to GLS are sometimes sought when GLS exhibits curious behavior, such as in Peelle’s Pertinent Puzzle (PPP). PPP was described in 1987 in the context of estimating fundamental parameters that arise in nuclear interaction experiments. In PPP, GLS estimates fell outside the range of the data, eliciting concerns that GLS was somehow flawed. These concerns have led to suggested alternatives to GLS estimators. This paper defends GLS in the PPP context, investigates when PPP can occur, illustrates when PPP can be beneficial for parameter estimation, reviews optimality properties of GLS estimators, and gives an example in which PPP does occur. Full article

► Show Figures

335 KiB

Open AccessArticle

Quantification of the Variability of Continuous Glucose Monitoring Data

by Edward Aboufadel, Robert Castellano and Derek Olson

Algorithms 2011, 4(1), 16-27; https://0-doi-org.brum.beds.ac.uk/10.3390/a4010016 - 15 Feb 2011

Cited by 6 | Viewed by 8249

Abstract

Several measurements are used to describe the behavior of a diabetic patient’s blood glucose. We describe a new, wavelet-based algorithm that indicates a new measurement called a PLA index could be used to quantify the variability or predictability of blood glucose. This wavelet-based [...] Read more.

Several measurements are used to describe the behavior of a diabetic patient’s blood glucose. We describe a new, wavelet-based algorithm that indicates a new measurement called a PLA index could be used to quantify the variability or predictability of blood glucose. This wavelet-based approach emphasizes the shape of a blood glucose graph. Using continuous glucose monitors (CGMs), this measurement could become a new tool to classify patients based on their blood glucose behavior and may become a new method in the management of diabetes. Full article

► Show Figures

1019 KiB

Open AccessArticle

Recognizing the Repeatable Configurations of Time-Reversible Generalized Langton’s Ant Is PSPACE-Hard

by Tatsuie Tsukiji and Takeo Hagiwara

Algorithms 2011, 4(1), 1-15; https://0-doi-org.brum.beds.ac.uk/10.3390/a4010001 - 28 Jan 2011

Cited by 4 | Viewed by 6768

Abstract

Chris Langton proposed a model of an artificial life that he named “ant”: an agent- called ant- that is over a square of a grid moves by turning to the left (or right) accordingly to black (or white) color of the square where [...] Read more.

Chris Langton proposed a model of an artificial life that he named “ant”: an agent- called ant- that is over a square of a grid moves by turning to the left (or right) accordingly to black (or white) color of the square where it is heading, and the square then reverses its color. Bunimovich and Troubetzkoy proved that an ant’s trajectory is always unbounded, or equivalently, there exists no repeatable configuration of the ant’s system. On the other hand, by introducing a new type of color where the ant goes straight ahead and the color never changes, repeatable configurations are known to exist. In this paper, we prove that determining whether a given finite configuration of generalized Langton’s ant is repeatable or not is PSPACE-hard. We also prove the PSPACE-hardness of the ant’s problem on a hexagonal grid. Full article

► Show Figures

Journal Menu

Journal Browser

Algorithms, Volume 4, Issue 1 (March 2011) – 5 articles , Pages 1-74

Further Information

Guidelines

MDPI Initiatives

Follow MDPI