Summary: This technical report contains the abstracts of 07 papers authorized to be published from a total of 34 papers presented at the XII Workshop on Theses, Dissertations and Scientific Initiation Papers (WTD) of the Instituto de Computação (IC) of the State University of Campinas (Unicamp ) from the year 2017. The Workshop took place between the 31st of July and the 2nd of August 2017 and had about 210 participants, including listeners, presenters and organizers. On the occasion there were 28 oral presentations and a poster session with 06 works. Students were given the opportunity to choose the form of presentation (oral, poster), as well as choose whether to publish their work in the event proceedings. The publication of the abstracts, in the form of a technical report, aims to disseminate the work in progress and record, in a succinct manner, the state of the art of the Instituto de Computação research in the year 2017.
Abstract: Model based testing is a well-established approach to test reactive systems. One of the challenges stemming from model based testing is the generation of test suites, especially when completeness is a required property these test suites. In order to check whether an implementation under test is in compliance with its respective specification model one resorts to some form of a conformance relation that guarantees some expected behavior of the implementations, given the behavior of the specification. The ioco conformance relation is an example of such a relation, specially suited for reactive and asynchronous models. In this work we study a more general conformance relation for such models. We also describe a method to generate finite and complete test suites which are complete in general, and we also discuss the complexity of the generation mechanism, as well as the complexity of testing implementations under this more general conformance relation. We show that loco conformance is a special case of this new conformance relation, for two classes of fault models, and we also investigate the complexity of generating complete test suites for these fault models, and also the complexity of running verification experiments using the test suites so generated.
Abstract: This work is a partial report related to the development and assessment of a Concept Inventory to Introductory Programming Courses. A Concept Inventory is a set of multiple-choice questions that address specific misunderstandings and misconceptions of the students. In previous works, through instructor interviews, exam analysis, an online pilot test and interviews with students, we identified a list of 33 misconceptions related to 7 programming topics in C language. On this report we describe each one of these misconceptions, following an antipattern template composed by: code (a label to identify the misconception); name; description; rationale (the reason why we hypothesise the misconception happens); consequences; detection (where and how the misconception appears); and improvement (how to prevent the misconception).
-labellings of lobsters and trees with a perfect matching.
Abstract: A graceful labeling of a tree
is an injective function
such that
. An
with the additional property that there exists an integer
such that, for each edge
either
or
. In this work, we prove that the following families of trees with maximum degree three have
-legs and with at most one forbidden ending; trees
such that the contraction
has a balanced bipartition and an
Abstract: A graceful labeling of a tree
is an injective function
such that
. A tree
, there exists a graceful labeling
of
. In this work, it is proved that if
and, for every non-leaf vertex
is at least
, then
-rotatable. This result reinforces the conjecture that every caterpillar with diameter at least five is 0-rotatable.
Abstract: A graceful labeling of a tree
is an injective function
such that
. A tree
, there exists a graceful labeling
of
. In this work, it is proved that the following families of caterpillars are 0-rotatable: caterpillars with a perfect matching; caterpillars obtained by identifying a central vertex of a path
with a vertex of
; caterpillars obtained by linking one leaf of the star
to a leaf of a path
and
; and caterpillars with diameter five or six. These results reinforce the conjecture that all caterpillars with diameter at least five are 0-rotatable.
Summary: We began restructuring these notes in 2016, when Meidanis was on sabbatical at the University of Ottawa, in David Sankoff's laboratory. We use the term “restructuring” because the main results shown here, on minimax genomes under rank distance, first appeared in the text presented by Biller in his doctoral qualification exam, written in 2014. The content is divided into six chapters, as follows. In Chapter 1 we introduce the first definitions, including genomic matrices, distance, and orbits. We also derive an important formula for distance based on orbits. In Chapter 2 we defined operations on genomes, with a focus on those with a small rank. The chapter ends with the definition of basic operations, namely, cuts, joins, and double exchanges. In Chapter 3 we studied sorting scenarios going from one genome to another through basic operations. We show that from each genome we can reach any other with such scenarios. This also provides an alternative way to calculate the distance. Intermediate genomes are the topic of Chapter 4. They can be characterized as members of optimal scenarios, or as genomes for which equality in triangular inequality is found. They are also the medians of two genomes. A related notion is the notion of minimax genomes, explored in Chapter 5. We have established a lower limit for the minimax score, and we show exactly the cases where this limit can be reached. In any case, it is always possible to find a genome less than one unit from the lower limit. Finally, Chapter 6 deals with an interesting parity property of rank distance.
Abstract: We started the work of reshaping these notes in 2016, when Meidanis was on sabbatical at the University of Ottawa, in David Sankoff's lab. We use the term “reshaping” because the main results shown here, on minimax genomes under the rank distance, were first presented in Biller's text for her PhD qualifying exam, written in 2014. The contents are divided into six chapters, as follows. In Chapter 1 we introduce the first definitions, including genome matrices, distance, and orbits. We also derive an important formula for the distance based on orbits. In Chapter 2 we define operations on genomes, with focus on those with small rank. The chapter closes with the definition of basic operations, namely, cuts, joins, and double swaps. In Chapter 3 we study sorting scenarios going from a genome to another by basic operations. We show that from every genome we can reach any other with such scenarios. This also provides an alternative way of computing the distance. Intermediate genomes are the topic of Chapter 4. They can be both as optimal scenario members, and as genomes for which the triangle inequality becomes an equality. They are also the medians of two genomes. A related notion is that of a minimax genome, explored in Chapter 5. We establish a lower bound for the minimax score, and show exactly the cases where it is possible to achieve such a score. In any case, it is always possible to find a genome within 1 unit of the lower bound. Finally, Chapter 6 deals with an interesting parity property of the rank distance.
Abstract: Model based testing is a well-established approach to test reactive systems described by formal models. In this paper we look at the problem of generating complete test suite for reactive systems formally described as Input Output Labeled Transition Systems (IOLTSs). In this work we propose a new notion of conformance relation for IOLTS models based on formal languages and automata. We show that this new conformance relation is more general than the well-studied loco conformance relation. We then describe how to generate test suites that are sound and exhaustive for a given specification model, according to the new conformance relation. We impose no restrictions on the structure of the specification model, a distinct advantage when compared to other recent works.
Summary: This technical report proposes a Routing, Core and Spectrum Assignment (RCSA) algorithm based on image processing Inscribed rectangle algorithm. The solution aims at discovering portions of spectrum capable of accommodating requests with low computational complexity. Advanced fitting policies are proposed to chose which portion of the spectrum to reduce of blocking and crosstalk. Results show that the proposed algorithm can reduce the blocking ratio under low loads and crosstalk under all loads, when compared to other RCSA algorithms in the literature.
Summary: This technical report introduces a novel Routing, Core and Spectrum Assignment (RCSA) algorithm based on the Connected Component Labeling (CCL) algorithm. The RCSA algorithm represents the spectrum of multicore fibers as matrices and the CCL algorithm discovers with low computational complexity the available spectrum to allocate to a connection request. Spectrum fitting policies are also proposed to be jointly employed with the CCL algorithm. Results show the feasibility of using image processing algorithms such as the CCL in RCSA algorithms, given that they demand low computational complexity and yet produce low blocking ratio.
Summary: Information and Communication Technology activities consumed 4% of the world energy in 2009, and such consumption will continue to increase due to the traffic growth of the Internet predicted for the next years. Techniques to make the core of the network more energy efficient has been proposed, among them, green routing has been considered a promising technique. This technical report proposes a novel Routing, Modulation Level and Spectrum Assignment (RMLSA) algorithm for elastic optical networks that considers the energy consumption of potential routes. Results indicate that this algorithm can save up to 34% energy and produce bandwidth blocking ratio two orders of magnitude lower than existing energy aware RMLSA algorithms.
Summary: This technical report introduces a novel traffic grooming algorithm for the connection establishment of deadline-driven requests in elastic optical networks, named Elastic Batch Grooming Algorithm. The algorithm grooms batches of requests to establish lightpaths with diverse bandwidth demands with deadline requirements. Results show that the algorithm significantly reduces the blocking ratio and the number of demanded transponder when compared to traditional non-batch algorithms.
Abstract: Modern systems need to able to self-adapt to changing user needs and system environments. Examples of systems that demand self-adaptive capabilities include mobile devices applications that should deal with environmental changes and service-oriented systems that should replace unreliable services on-the-fly. In this context, dynamic software product line (DSPL) is an engineering approach for developing adaptive systems based on commonalities and variabilities for a family of similar systems. However, researchers have reported that many DSPL solutions fail to meet all the system's adaptability requirements, and in many cases, they are developed in ad hoc manner. This paper surveys various DSPL solutions, evaluates and compares their different design strategies. A two-dimension taxonomy is specified to address basic technical issues for a given DSPL proposal. The DSPL dimension classifies the different design choices for implementing variability schemes, and for creating different kinds of feature models. The Self-adaptation dimension classifies the different design choices for the adaptation requirements and for the MAPE-K control loop implementation. Practical issues and difficulties are summarized, major trends in actual DSPL proposals are identified, and directions for future work are suggested.
Abstract: In optical networks, failures can imply in great loss of data due to high transmission rates, leading to the need of employment of protection mechanisms. This paper introduces a novel algorithm to provide Failure-independent path protecting p-cycle with minimum interference for path protection in elastic optical networks using space division multiplexing. The proposed protection algorithm reduces rejections of future requests and make no assumption about specific patterns of arrival of requests. The algorithm is compared to FIPPMC algorithm and a algorithm based on methods of []. Results indicate that the 100% protection for single failures can be provided by the proposed algorithm.
Abstract: In recent years, elastic optical networks have emerged as a solution for dealing with the diversity of the bandwidth demands of network applications. The use of only two multiplexing dimensions has limited the network capacity. To ameliorate this problem, a third dimension has been added in space-division multiplexing (SDM). The transmission rates increase so does the need for protection against network failures. Among the protection schemes, those protecting paths are of great interest due to their end-to-end solutions. This paper introduces a novel algorithm based on p-cycle to provide failure-independent path protection in elastic optical networks with SDM.
Abstract: Informally, total order broadcast protocols allow processes to send messages with the guarantee that all processes eventually deliver the messages in the same order. In this paper, we investigate the efficiency and performance of On-Time Fast Paxos a synchronous total order broadcast protocol for the crash-recover failure model that is built atop a broadcast-based asynchronous distributed system. On-Time Fast Paxos combines an asynchronous consensus protocol, Fast Paxos, with a synchronous communication protocol while guaranteeing the original safety and liveness properties of Fast Paxos. The synchronous communication protocol relies on virtual global time to create the synchronicity necessary to make Fast Paxos work at its theoretical optimum, two communication steps. Experimental results allow us to conclude that On-Time Fast Paxos performs very well both in terms of throughput and latency, reaches 960mbps in a 1Gbps network with an average latency of 2ms. Finally, its novel hybrid design, asynchronous layer driven by a synchronous layer, shows that, time and synchrony be used to improve the performance of total order broadcast protocols.
Summary: We apply the general top-down algorithm for multilevel adaptive approximation HAPP, described in Part I of this article, for a specific type of approximation function bases that we call regular multilevel bases. The algorithm guarantees a maximum approximation error specified at each sampling point. Although the resulting adaptive base is not necessarily minimal, it can be much smaller than the complete base, for the functions to be approximated with local details at various scales of spatial resolution. The base elements are tensor splines with compact support. These bases are similar to standard wavelet bases, except that they provide analytical formulas for the approximation function; that can be used, for example, for differentiation and interpolation between sampling points. In this part of the article, we assume a regular grid of sampling points and a box-type domain with toroidal topology. These choices allow considerable savings in computing time. We also use a modified least squares operator with Bayesian outlier rejection at each level.
|
Instituto de Computação :: State University of Campinas
Av. Albert Einstein, 1251 - Cidade Universitária Zeferino Vaz • 13083-852 Campinas, SP - Brazil • Phone: [19] 3521-5838 |