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 matching covered graph is a connected graph each edge of which lies in some perfect matching. A cut of a matching covered graph is separating 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 characteristic 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 spherical polynomial is the restriction to the sphere of a polynomial in the three coordinates of . Let be an arbitrary triangulation on the sphere, and let (resp ) 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 spherical polynomial (resp 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 in 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 in 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 proved 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.

Resumo: Os ambientes de educação a distância para a Web, em sua maioria, apresentam as informações em formato textual. A interface em forma seqüencial utilizada para visualizar os textos, aliada ao grande volume de dados gerados em tais ambientes, dificulta a recuperação dessas informações. Este artigo apresenta a ferramenta Interaction Map (InterMap), que através de técnicas de visualização de informação representa os dados de ferramentas de interação do TelEduc, um ambiente de educação a distância baseado na Web.

Palavras-chave: Visualização de informação, ferramentas de interação, ambientes interativos de aprendizagem, ambientes de ensino a distância baseados na Web, ferramentas para WWW.

Abstract: Most Web-based distance education environments present the information in a textual format. The use of sequential interfaces to visualize 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 visualize information about interaction in TelEduc, a 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.

Resumo: Sistemas de Informação Geográficas (SIG) são também usados para a geração de mapas. Usuários de SIG devem interagir com o sistema para a obtenção do design final do mapa, numa dinâmica que depende da arquitetura subjacente do sistema, mas principalmente da sua interface. Neste trabalho recuperamos o processo de construção de mapas da Cartografia tradicional - o procedimento adotado pelo cartógrafo - representando-o através de um formalismo que facilita sua transposição para o domínio computacional. Esta representação serve de base para estudos sobre a dinâmica de interação do usuário com interfaces de SIG na tarefa de construção de mapas.

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 on-line. 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 on-line). 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 .

Non-homogeneous polynomial splines on the sphere .

Abstract: A homogeneous spherical polynomial (HSP) is the restriction to the sphere of a homogeneous polynomial on the cartesian coordinates of . A 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 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.

High-speed software multiplication in .

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.

Resumo: Este artigo discute o problema de indução 2.17 do livro ``Introduction to Algorithms: A Creative Approach,'' de Udi Manber: Considere retas, em posição geral, no plano Euclideano. Prove que estas retas formam, pelo menos, triângulos. Ele apresenta uma pesquisa bibliográfica que revela uma história bem interessante sobre a resolução deste problema. A contribuição principal do artigo são três contra-exemplos para a abordagem mais comum, que ajudam a explicar a dificuldade em se obter uma prova indutiva simples. Também é apresentada uma versão simplificada de uma recente demonstração por argumentos de contagem.

(Este artigo foi submetido para a revista Matemática Universitária.)

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 Matemática Universitária.).

Resumo: O uso da WWW (World Wide Web) como suporte a cursos a distância tem aumentado muito nos últimos anos. Vários ambientes têm sido propostos e desenvolvidos com o objetivo de auxiliar e facilitar o trabalho dos professores desses cursos, que tem se mostrado maior do que em cursos presenciais. No entanto, ainda há muito a fazer para tornar o gerenciamento de tais cursos menos árduos, principalmente, no que se refere a interação entre os vários atores (professores e alunos) do ambiente.

Durante o acompanhamento de um curso via Web no final de 1998, foram observados aspectos interessantes relacionados às dificuldades do professor no acompanhamento e avaliação dos alunos. Com o objetivo de contrastar os resultados desta observação com experiências similares, foi realizada uma série de entrevistas com professores envolvidos em programas de educação a distância (EAD) de várias instituições brasileiras. Assim, baseado nas informações obtidas, este artigo apresenta as experiências e sugestões dos professores para a melhoria deste processo. Além disso, este trabalho aponta as principais dificuldades identificadas e discute possíveis soluções.

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.

Resumo: O objetivo deste trabalho é aplicar técnicas de especificação formal para modelar sistemas distribuídos de tempo real provenientes de aplicações realistas. O sistemas alvo é um Sistema de Gerenciamento de Tráfego Aéreo (Air Traffic Management System - ATM), usando o protocolo do Sistema de alerta de Tráfego e Prevenção de Colisão (Traffic alert and Collision Avoidance System - TCAS). Os modelos formais desenvolvidos aqui são baseados na abordagem de autômatos híbridos. Ferramentas (semi) automáticas são usadas na verificação dos modelos, e alguns parâmetros importantes do sistema são sintetizados usando uma análise paramétrica. Todos os resultados foram obtidos sobre um PC de 350MHz típico, com 320MB de memória.

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.

Resumo: Nós consideramos diagramas de Voronoi definidos no plano projetivo orientado. Nesta geometria, os diagramas de vizinho mais próximo e vizinho mais distante são antipodais. Nós apresentamos um algoritmo incremental ``on-line'' para a construção do diagrama de pontos com peso aditivo. Este diagrama, que pode ser desconexo no plano Euclidiano, é sempre conexo no plano projetivo orientado e tem exatamente arestas e vértices, onde é o número de sítios.

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 on-line 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.

Resumo: Nós apresentamos um novo procedimento de semidecisão para testar inclusão de linguagem de autômatos temporais não determinísticos (NTA). Mostramos que a linguagem gerada por um autômato temporal progressivo pode ser testada para inclusão contra a linguagem gerada por qualquer NTA. Na prática, muitos modelos de autômatos temporais de sistemas físicos reais são progressivos, de modo que toda a expressividade de NTA pode ser usada para especificar propriedades de tempo-real. Entre esses, estão modelos de circuitos digitais assíncronos. O procedimento de semidecisão é, também, uma redução do problema de inclusão de linguagem de NTA para o problema de inclusão de linguagem para -autômatos não determinísticos, efetivos e de estados infinitos.

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 -automata.

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 (e.g. ARM Thumb and MIPS16), or that are able to execute compressed code (e.g. 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.