Abstract: We study the problem of comparing two circular chromosomes, evolved from a common ancestor by reversals, given the order of the corresponding genes and their orientations. Determining the minimum number of reversals between the chromosomes is equivalent to looking for the minimum number of reversals that transform a circular sequence of signed integer numbers, defined in an appropriate manner, into another; where a reversal acts on a subsequence, reversing its order and flipping the signs. We carefully formalize the concepts of circular chromosome and circular reversal, and show that this problem is essentially equivalent to the analogous problem on linear chromosomes. As a consequence we derive polynomial time algorithms based on this observation. We also compute the reversal diameter for signed chromosomes, both linear and circular.
Abstract: A covered matching graph is a connected graph each edge of which lies in some perfect matching. A cut of a matching covered graph is separate if each of its two contractions yields a matching covered graph. A cut is tight if each perfect matching of the graph contains just one edge in the cut. Every tight cut of a matching covered graph is separating. The characteristics of a nontight separating cut is the smallest number of edges greater than one that some perfect matching of the graph has in the cut. The characteristic of a tight cut is defined to be equal to
. We show that the characteristic of every separating cut
of a matching covered graph lies in
. Moreover, if
has characteristic equal to 5 then graph
has the Petersen graph as a minor, in a very strict sense. In particular, if
is free of nontrivial tight cuts then
is the Petersen graph, up to multiple edges.
Abstract: THIS REPORT IS NOW OBSOLETE - SEE UPDATED VERSION TR-IC-01-05.
We describe a program that builds contig scaffolds from contig assemblies, to be used in a whole-genome sequencing project. Our program builds scaffolds based on forward / reverse pair information (both from small clones, such as plasmids, and from large clones, such as cosmids). The program assumes that a DNA assembly, preferably with large repeats masked, is available. A scaffold is a path in a weighted graph, and the main novelty of our approach is a careful weighting scheme for arcs in this graph, such that heavier paths represent more reliable scaffolds. This weighting scheme takes into account the presence of repeats, possible clone duplication, existence of different clone libraries, and hybrid (small clones mixed with large clones) links between contigs. The program provides two different algorithms for scaffold building: one that uses a simple greedy strategy, and one that produces scaffolds that correspond to paths of maximum weight. If
is the number of contigs and
is the number of F / R pairs, the complexities are
(greedy) and
(maximum-weight path). This program has been successfully used in a bacterial genome project.
Abstract: A polynomial spherical is the restriction to the sphere
of a polynomial in the three coordinates
of
... Let
be an arbitrary triangulation on the sphere, and let
(answer
) be the space of all
-continuous functions
from
to
such that the restriction of
to each triangle of
is a spherical polynomial (resp. homogeneous). These are the polynomial spherical (answer homogeneous) Splines of degree
(resp. exactly
) and continuity
.
In a previous paper, we have shown that
. Alfeld, Neamtu and Schumaker have recently constructed explicit bases for the spaces
. Combining these two results, we obtain explicit constructions for bases of
.
We believe that the general spline spaces
provide better approximations than the homogeneous spaces
when used over the relatively large regions (radius
to
) that are likely to occur in pratice. In this paper we report numerical experiments at least squares approximation which offer some evidence for this claim.
Abstract: This article considers the overall crew management problem that arises from the daily operation of an urban transit bus company that serves the metropolitan area of the city of Belo Horizonte, in Brazil.
Due to its intrinsic complexity, the problem is divided into two distinct problems, namely: crew scheduling and crew rostering. We have tackled each one of these problems using Mathematical Programming (MP) and Constraint Logic Programming (CLP) approaches. Besides, we also developed hybrid column generation algorithms for solving these problems, combining MP and CLP. The hybrid algorithms always performed better, when obtaining optimal solutions, than the two previous isolated approaches. In particular, they provide much faster for the scheduling problem.
All the proposed algorithms have been implemented and tested over real world data obtained from the aforementioned company. The coefficient matrix of the linear program associated with some instances of the scheduling problem contains tens of millions of columns, and this number is even larger for the rostering problem.
The analysis of our experiments indicates that it was possible to find high quality, and many times optimal, solutions that were suitable for the company's needs. These solutions were obtained within reasonable computational times, on a typical desktop PC.
Summary: Most distance learning environments for the Web present information in textual format. The sequential interface used to view the texts, combined with the large volume of data generated in such environments, makes it difficult to retrieve this information. This article introduces the tool Interaction Map (InterMap), which through information visualization techniques represents the data of interaction tools of the TelEduc, a web-based distance education environment.
Keywords: Information visualization, interaction tools, interactive learning environments, web-based distance learning environments, tools for WWW.
Abstract: Most Web-based distance education environments present the information in a textual format. The use of sequential interfaces to view texts, and the enormous volume of data generated by those environments makes it difficult to retrieve information. This paper presents Interaction Map (InterMap), a tool to view information about interaction in TelEduc, the Web-based distance education environment.
Key words: Information visualization, interaction tools, learning interactive environments, Web-based distance education environments, WWW tools.
Abstract: One possible model to study genome evolution is to represent genomes as permutations of genes and compute distances based on the minimum number of certain operations (rearrangements) needed to transform one permutation into another. Under this model, the shorter the distance, the closer the genomes are. Two operations that have been extensively studied are the reversal and the transposition. A reversal is an operation that reverses the order of the genes on a certain portion of the permutation. A transposition is an operation that `` cuts '' a certain portion of the permutation and `` pastes '' it elsewhere in the same permutation. In this paper we show that the reversal and transposition distance of the signed permutation
with respect to the identity is
for All
. We conjecture that this value is the diameter of the permutation group under these operations.
Summary: Geographic Information Systems (GIS) are also used for the generation of maps. GIS users must interact with the system to obtain the final design of the map, in a dynamic that depends on the underlying architecture of the system, but mainly on its interface. In this work, we recover the process of building maps from traditional Cartography - the procedure adopted by the cartographer - representing it through a formalism that facilitates its transposition into the computational domain. This representation serves as a basis for studies on the dynamics of user interaction with GIS interfaces in the task of building maps.
Abstract: Geographic Information Systems (GIS) are also used to generate maps. Users of GIS must interact with the system to obtain the final design of a map, in a process that depends on the underlying system architecture, and mainly on its users' interface. In this paper we studied the process of map construction of the traditional Cartography - the procedure adopted by the cartographer - representing such procedure trough a formalism that facilitates to reach the computational domain. This representation is a basis for the study of the interaction with GIS interfaces.
Abstract: We present approximation algorithms for the following problems: the two-dimensional bin packing, the three-dimensional packing problem and the container packing problem. We consider the special case in which the items to be packed are small and must be packed online. We say an item is small if each of its dimension is at most
of the respective dimension of the recipient, where
is an integer greater than 1. To our knowledge, the asymptotic performance bound of these algorithms are the best so far obtained for this special case (parametric online). For the above problems, (in the respective order) the algorithms we describe have bounds 2.112, 2.112, and 3.112, for
; and bounds 1.73, 1.73 and 2.285, for
.
Abstract: A homogeneous spherical polynomial (HSP) is the restriction to the sphere
of a homogeneous polynomial on the cartesian coordinates
of
. homogeneous spherical spline is a function that is an HSP within each element of a geodesic triangulation of
.
There has been considerable interest recently in the use of such splines for approximation of functions defined on the sphere. In this paper we introduce the general (non-homogeneous) spherical splines and argue that they are a more natural approximating spaces for spherical functions than the homogeneous ones. It turns out that the space of general spherical polynomials of degree
is the direct sum of the homogeneous spherical polynomials of degrees
and
. We then generalize this decomposition result to polynomial splines defined on a geodesic triangulation (spherical simplicial decomposition)
of the sphere
, of arbitrary degree
and continuity order
.
For the particular case
, the homogeneous spline spaces were extensively studied by Alfeld, Neamtu, and Schumaker, who showed how to construct explicit local bases when
. Combining their construction with our decomposition theorem, we obtain an explicit construction for a local basis of the general polynomial splines when
.
Abstract: In this paper, we introduce an image processing operator called Image Foresting Transformation (IFT). The image foresting transformation maps an input image into a graph, computes a shortest-path forest in this graph, and outputs an annotated image, which is basically an image and its associated forest. We describe the application of IFT to region growing, edge detection, Euclidean distance transform, geodesic distance computation, and watershed transformation. All the operators are efficiently computed using the same IFT algorithm based on the same set of parameters by changing only their meaning and values. We also present a new interactive image segmentation paradigm based on the region growing operator and discuss other applications of the IFT for boundary-based object definition and shape-based interpolation.
Abstract: Color is a commonly used feature for realizing content-based image retrieval (CBIR). In this context, this paper presents a new approach for CBIR which is based on well known and widely used color histograms. Contrasting to previous approaches, such as using a single color histogram for the whole image, or local color histograms for a fixed number of image cells, the one we propose (named Color-Shape) uses a variable number of histograms, depending only on the actual number of colors present in the image, which our experiments have shown often to be low. Our experiments using a large set of heterogeneous images and pre-defined query / answer sets show that the Color-Shape approach offers good retrieval quality with relatively low space overhead, outperforming previous approaches. Furthermore, we also show that the proposed approach is very flexible in the sense that the user may easily tune it, in order to calibrate the trade-off between space overhead and retrieval effectiveness. For instance, when compared to using global color histograms, our approach can retrieve images 80% more effectively, requiring 29 times more space for metadata. Although large, this space overhead is 55% smaller than the overhead of more traditional partition-based approaches with equivalent parameters. On the other hand, it can be tuned to save 15% in space requirements, when compared to storing a single global color histogram, while still being capable of yielding a 30% more effective retrieval.
Abstract: Elliptic curve cryptography (ECC) was introduced by Victor Miller and Neal Koblitz in 1985. ECC, proposed as an alternative to established public-key systems such as DSA and RSA, has recently gained a lot attention in industry and academia. The main reason for the attractiveness of ECC is the fact that there is no sub-exponential algorithm known to solve the discrete logarithm problem on a properly chosen elliptic curve. This means that significantly smaller parameters can be used in ECC than in other competitive systems such as RSA and DSA, but with equivalent levels of security. Some benefits of having smaller key sizes include faster computations, and reductions in processing power, storage space and bandwidth. This makes ECC ideal for constrained environments such as pagers, PDAs, cellular phones and smart cards. The implementation of ECC, on the other hand, requires several choices such as the type of the underlying finite field, algorithms for implementing the finite field arithmetic, the type of elliptic curve, algorithms for implementing the elliptic group operation, and elliptic curve protocols. Many of these selections may have a major impact on the overall performance. In this paper we present a selective overview of the main methods and techniques used for practical implementations of elliptic curve cryptosystems. We also present a summary of the most recent reported software implementations of ECC.
Abstract: In this paper we describe an efficient algorithm for multiplication in
, where the field elements of
are represented in standard polynomial basis. The proposed algorithm can be used in practical software implementations of elliptic curve cryptography. Our timing results, on several platforms, show that the new method is significantly faster than the `` shift-and-add '' method.
Abstract: In recent years, several studies have been conducted on software implementation of elliptic curve cryptosystems (ECC). In this note we have collected several details of reported software implementations of these cryptosystems. For each implementation considered, we include, if available, the platform used, and running times for: finite field operations, scalar multiplications, and protocols such as the ECDSA. This compilation is organized in five sections: performance of ECC over
, performance of ECC over
, performance of ECC over
, implementations comparing
and
, and implementations comparing ECC with other public-key systems such as RSA and DL.
Summary: This article discusses the induction problem 2.17 of the book `` Introduction to Algorithms: A Creative Approach, '' by Udi Manber: Consider
straight, in general position, in the Euclidean plane. Prove that these lines form at least
triangles. It presents a bibliographic search that reveals a very interesting story about solving this problem. The main contribution of the article are three counterexamples to the most common approach, which help to explain the difficulty in obtaining simple inductive proof. A simplified version of a recent demonstration by counting arguments is also presented.
(This article was submitted to the journal University Mathematics.)
Abstract: This paper is about the induction exercise 2.17 from the book `` Introduction to Algorithms: A Creative Approach, '' by Udi Manber: consider
straight lines, in general position, on the Euclidean plane. Prove that these lines create, at least,
triangles. The paper includes a bibliographic research that tells a very interesting story about the solution of this exercise. The main contribution of the paper are three counter-examples to the most common approach, that help explain why it is so hard to obtain a simple inductive proof. We also present a simplified version of a recent proof by counting arguments.
(This article has been submitted to the Brazilian journal University Mathematics.).
Summary: The use of the WWW (World Wide Web) to support distance learning courses has increased a lot in recent years. Various environments have been proposed and developed with the objective of assisting and facilitating the work of teachers in these courses, which has been shown to be greater than in classroom courses. However, there is still much to be done to make the management of such courses less arduous, especially with regard to the interaction between the various actors (teachers and students) in the environment.
During the monitoring of a course via the Web in late 1998, interesting aspects were observed related to the teacher's difficulties in monitoring and evaluating students. In order to contrast the results of this observation with similar experiences, a series of interviews was conducted with teachers involved in distance education programs (EAD) from several Brazilian institutions. Thus, based on the information obtained, this article presents the teachers' experiences and suggestions for improving this process. In addition, this work points out the main difficulties identified and discusses possible solutions.
Abstract: Use of the World Wide Web (WWW) to support distance education has substantially increased in recent years. Several environments have been proposed and developed to help and lighten the teacher's work load in these courses, which turned out to be heavier than in traditional ones. However, there is still a lot to be done in order to make the management of such courses less of a burden, mainly with respect to interaction between the various actors (teachers and students) in the environment.
During a Web-based course at the end of 1998, several interesting aspects were observed relating to the teacher's difficulties in overseeing and evaluating the students. In order to contrast the results of this observation with similar experiments, we performed a series of interviews with teachers who work on distance education projects at several Brazilian institutions. Thus, based on the information we obtained, we describe here the teachers' experiences and suggestions for improving the process. In addition, we point out here the main difficulties we identified and we discuss possible solutions.
Summary: The aim of this work is to apply formal specification techniques to model distributed real-time systems from realistic applications. The target system is an Air Traffic Management System (ATM), using the Traffic Alert and Collision Avoidance System (TCAS) protocol. The formal models developed here are based on the hybrid automata approach. (Semi) automatic tools are used to verify the models, and some important system parameters are synthesized using parametric analysis. All results were obtained on a typical 350MHz PC, with 320MB of memory.
Abstract: The aim of this work is to apply formal specification techniques to model real-time distributed systems arising from real-world applications. The target system is an Air Traffic Management System (ATM), using the Traffic alert and Collision Avoidance System (TCAS) protocol. The formal models developed here are based on the notion of hybrid automata. Semi-automatic tools are used in the verification of the models, and some important system parameters are synthesized using a parametric analysis. All results were obtained on a 350MHz desktop PC, with 320MB of main memory.
Abstract: This article describes the crew rostering problem stemming from the operation of a Brazilian bus company that serves a major urban area in the city of Belo Horizonte. The problem is solved by means of Integer Programming (IP) and Constraint Logic Programming (CLP) approaches, whose models are discussed in detail. Lower bounds obtained with a Linear Programming relaxation of the problem are used in order to evaluate the quality of the solutions found. We also present a hybrid column generation approach for the problem, combining IP and CLP over a set partitioning formulation. Experiments are conducted upon real data sets and computational results are evaluated, comparing the performance of these three solution methods.
Summary: We consider Voronoi diagrams defined in the oriented projective plane. In this geometry, the nearest and farthest neighbor diagrams are antipodal. We present an incremental `` online '' algorithm for the construction of the point diagram with additive weight. This diagram, which can be disconnected on the Euclidean plane, is always connected on the oriented projective plane and has exactly
edges and
vertices where
is the number of sites.
Abstract: We consider Voronoi diagrams defined on the oriented projective plane. In this geometry, the closest and furthest site diagrams are antipodal. We give a simple online incremental algorithm for constructing the additively weighted diagram. This diagram, which may be disconnected in Euclidean plane, is always connected in the oriented projective plane and has exactly
edges and
vertices, where
is the number of sites.
Summary: We present a new semi-decision procedure to test the inclusion of non-deterministic temporal automata (NTA) language. We show that the language generated by a temporal automaton progressive can be tested for inclusion against language generated by any NTA. In practice, many models of temporal automata of real physical systems are progressive, so that all the expressiveness of NTA can be used to specify real-time properties. Among these are asynchronous digital circuit models. The semidecision procedure is also a reduction of the problem of inclusion of NTA language to the problem of inclusion of language for
-automatic non-deterministic, effective and infinite states.
Abstract: We give a new semi-decision procedure for testing language inclusion of nondeterministic timed automata (NTA). We show that the language generated by a progressive timed automaton can be tested for inclusion against the language generated by Any NTA. In practice, many timed automata models of actual physical systems are progressive, so that the full expressiveness of NTA can be used to specify real-time properties. These include models of asynchronous digital circuits. The semi-decision procedure is also a reduction of the language inclusion problem for NTA to the language inclusion problem for nondeterministic effective infinite-state
-automated.
Abstract: Reducing program size has become an important goal in the design of modern embedded systems target to mass production. This problem has driven a number of efforts aimed at designing processors with shorter instruction formats (eg ARM Thumb and MIPS16), or that are able to execute compressed code (eg IBM CodePack PowerPC). This paper proposes three code compression algorithms for embedded RISC architectures. In all algorithms, the encoded symbols are extracted from program expression trees. The algorithms differ on the granularity of the encoded symbol, which are selected from whole trees, parts of trees or single instructions. Dictionary based decompression engines are proposed for each compression algorithm. Experimental results, based on SPEC CINT95 programs running on the MIPS R4000 processor, reveal an average compression ratio of 53.6% (31.5%) if the area of the decompression engine is (not) considered.
Instituto de Computação :: State University of Campinas
PO Box 6176 • Av. Albert Einstein, 1251 - Cidade Universitária • CEP 13083-970 • Campinas / SP - Brazil • Phone: [19] 3521-5838 |