12 papers · ranked by Valyu relevance
Étienne Grandjean, Louis Jachiet
| 1 | | Introduction and discussion of the RAM model | 2 | | --- | --- | --- | --- | | 2 | | Instruction sets for the RAM model | 6 | | | 2.1 | The RAM model with minimal instruction set | 6 | | | 2.2 | Two more instruction sets | 9 | | | 2.3 | Equivalence of our three instruction sets | 10 | | | 2.4 | Richer…
Nicola Rizzo, Manuel Cáceres, Veli Mäkinen
Background We study the problem of finding maximal exact matches (MEMs) between a query string Q and a labeled graph G. MEMs are an important class of seeds, often used in seed-chain-extend type of practical alignment methods because of their strong connections to classical metrics. A principled way to speed up…
Jatin Batra, Naveen Garg, Amit Kumar
In the weighted flow-time problem on a single machine, we are given a set of n jobs, where each job has a processing requirement pj , release date rj and weight wj . The goal is to find a preemptive schedule which minimizes the sum of weighted flow-time of jobs, where the flow-time of a job is the difference between…
Ahsan Sanaullah, Nathaniel K. Brown, Pramesh Shakya, Arun Deegutla + 4 more
Lossless full text indexes are utilized in a myriad of applications in bioinformatics. The continuously decreasing cost of generating biological data has resulted in the need to build full text indexes on biological datasets of increasing size. Many compressed full text indexes have been developed to address this…
Tamar Pinhas, Shay Zakov, Dekel Tsur, Michal Ziv-Ukelson
We propose three algorithms for string edit distance with duplications and contractions. These include an efficient general algorithm and two improvements which apply under certain constraints on the cost function. The new algorithms solve a more general problem variant and obtain better time complexities with respect…
Mohammad Abdur Rob, Md. Zakir Hossen, Md. Kamal Hossen, Md. Mithun Ali + 2 more
Sorting algorithms play a crucial role in computing, but most are designed with rigid structure that are only efficient under certain conditions. Although some sorting algorithms perform well in some circumstances, they do not perform well on some resistant platforms. This study introduces Wall-L Merge Sort, which…
L. Kozma, Tan, Junqi
For many hard computational problems, simple algorithms that run in time 2 n · n O (1) arise, say, from enumerating all subsets of a size-n set. Finding (exponentially) faster algorithms is a natural goal that has driven much of the field of exact exponential algorithms (e.g., see Fomin and Kratsch, 2010). In this…
Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann
Let G be a weighted (directed) graph with n vertices and m edges. Given a source vertex s, Dijkstra's algorithm computes the shortest path lengths from s to all other vertices in O(m + n log n) time. This bound is known to be worst-case optimal via a reduction to sorting. Theoretical computer science has developed…
Ricardo Villanueva-Polanco
In this paper, we will study the key enumeration problem, which is connected to the key recovery problem posed in the cold boot attack setting. In this setting, an attacker with physical access to a computer may obtain noisy data of a cryptographic secret key of a cryptographic scheme from main memory via this data…
Chunchun Zhao, Sartaj Sahni
Background In the string correction problem, we are to transform one string into another using a set of prescribed edit operations. In string correction using the Damerau-Levenshtein (DL) distance, the permissible edit operations are: substitution, insertion, deletion and transposition. Several algorithms for string…
Qizheng He
The integer complexity f(n) of a positive integer n is a simple-looking problem in number theory with a long history. It is defined as the minimum number of 1's needed to represent n, using basic arithmetic expressions that only include 1, additions, multiplications and parentheses. For example, f(6) = 5, since 6 = (1…
Shantanu Chhabra
We define an n-gon to be any convex polygon with n vertices. Let V represent the set of vertices of the polygon. A "proper" k-coloring refers to a function, f: V → {1, 2, 3, . . . k}, such that for any two vertices u and v, if f(u) = f(v), u is not adjacent to v. The purpose of this paper is to develop a recursive…